[F-Lab 모각코 챌린지] 5일차 - 제네릭, List

제네릭

• 제네릭은 타입 안정성을 위해 만들어짐
• 코드의 재사용성을 높인다

공변성과 반공변성

제네릭에서 알아두면 유용한 키워드

공변성: 자식 타입이 부모 타입으로 대체될 수 있음 <? extends Number>

반공변성: 부모 타입이 자식 타입으로 대체될 수 있음 <? super Integer>

와일드 카드: <?>

• 제네릭의 하위 개념
• 타입의 유연성과 다형성을 활용하는 것을 목적으로 함

자바 컬렉션 - List

• 순서가 보장되는 자바의 컬렉션 프레임워크
• 구현체로는 ArrayList 와 LinkedList 가 존재

ArrayList<T>

• Iterable, Collection, List 인터페이스에서 구현체로 사용 가능
• 내부에 제네릭 타입의 배열이 존재하며 배열 내부에 값을 조정하거나 배열을 조작하여 동작

add(E element)

add(E element) 동작 시 다음 두 경우로 나뉨

• 배열이 모두 찼을 때 삽입
  배열의 사이즈를 늘리고(시프트 연산으로 배열의 사이즈 늘림) 현재 배열을 새로운 배열에 복사 후 맨 끝에 삽입: O(n)
• 배열의 공간이 남아있을 때 삽입
  배열의 맨 뒤에 삽입: O(1)

add(int index, E element)

지정된 index 에 element 를 추가.

• 맨 뒤에 요소를 추가하는 경우: O(1)
• 맨 앞이나 중간에 요소를 추가하는 경우:
  추가 위치 포함 이후 배열을 한 칸씩 뒤로 이동O(n).
  이 때, 배열의 사이즈가 늘어나야 한다면 O(2n) 이지만, 빅오 표기법 에서는 상수인 2를 고려하지 않기 때문에 O(n)

get(int index)

내부의 배열 요소에서 값을 읽음

• 배열에서 index 조회를 수행하기 때문에 매우 빠름: O(1)

set(int index, E element)

값의 변경은 항상 빠름: O(1)

remove(int index)

내부의 데이터를 삭제
이 때는 위치에 따라 성능 저하가 나타날 수 있음

• 맨 뒤의 요소를 삭제 하는 경우: O(1)
• 맨 앞이나 중간의 요소를 삭제:
  삭제된 위치 이후 모든 요소를 한 칸씩 앞으로 이동: O(n)

LinkedList<T>

• Collection, Deque, Queue, List 인터페이스에서 구현체로 사용 가능
• Node 를 통해 요소끼리 Link 된 형태의 자료구조

add(E element)

• 맨 마지막에 add 를 하기 때문에 항상 O(1)

add(int index, E element)

• 맨 앞이나 뒤에 삽입하는 경우: LinkedList 에서는 First node 와 Last node 를 내부에 요소로 선언 해 놓았기 때문에 상수시간으로 접근 가능. O(1)
• 중간에 삽입하는 경우: 해당 요소의 위치를 n 만큼 돌며 찾아야 하기 때문에 O(n)

get(int index)

• 항상 n 만큼 순회하며 값을 가져오기 때문에 O(n)

set(int index, E element)

• 맨 앞이나 뒤에 변경 하는 경우: O(1)
• 중간에 변경 하는 경우: index 만큼 순회하며 찾아야 하기 때문에 O(n)

remove(int index)

• 인접한 Node 의 다음, 이전 노드를 바꿔주기만 하면 되서 O(1)