[Java] Collection Framework - List의 구현체(기본)

0. List 인터페이스 특징

• Collection 인터페이스를 상속받는다.
• 요소의 중복을 허용한다.
• 인덱스 순서로 저장된다. (sequence)
• null 요소를 허용한다.

Unmodifiable List

• List.of 혹은 List.copyOf 정적 팩토리 메소드를 통해 수정 불가능한 List를 사용할 수 있다. 
  • 삽입, 삭제, 변경 불가 → 수행하는 경우 UnsupportedOperationException이 발생한다.
• null 요소를 허용하지 않는다.

 

---

 

 

1. List 인터페이스의 구현

• ArrayList
• LinkedList
• Vector

배열과 List 인터페이스의 차이

배열	List 인터페이스
배열의 크기를 처음 선언 이후로 변경할 수 없음	List의 길이가 가변적
메모리에 연속적으로 할당	메모리에 연속적으로 할당 ❌ 각 데이터가 주소로 연결되어 있음
특정 index의 요소를 삭제하면 해당 index에는 빈공간이 남음	데이터 사이에 빈공간이 없음(허용하지 않음)

• 처음에 몇개의 요소가 추가될지 알 수 있는 경우 배열을 사용하는 것이 좋다.
• 요소의 삽입, 삭제가 빈번한 경우에는 List를 사용하는 것이 좋다.

---

 

 

2. List의 기본 메소드

return value	method	description
int	size()	List의 요소 개수를 반환한다.  요소 수가 Integer.MAX_VALUE 이상이면 Integer.MAX_VALUE 반환한다.
boolean	isEmpty()	List에 요소가 포함되어 있지 않다면 true를 반환한다.
boolean	contains(Object o)	List에 지정된 요소가 포함되어 있다면 true를 반환한다.
Iterator<E>	iterator()	List를 순회할 수 있는 Iterator를 반환한다.
Object[]	toArray()	List의 모든 요소를 포함하는 배열을 반환한다.  반대: Arrays.asList(Object[])
boolean	add(E e)	List의 끝에 새로운 요소를 추가한다.  일부 List의 구현체는 null 요소 추가가 제한되어 있다.
boolean	remove(Object o)	지정한 요소가 있는 경우 List에서 지정한 요소의 첫번째를(가장 낮은 인덱스) 제거한다. List에 지정한 요소가 포함되어 있지 않다면 아무런 작업을 하지 않는다.  List에 지정한 요소가 있는 경우 true를 반환한다.
boolean	containsAll(Collection<?> c)	List에 지정된 Collection의 모든 요소가 포함되어 있으면 true를 반환한다.
boolean	addAll(Collection<? extends E> c)	지정된 Collection의 Iterator가 반환하는 순서대로 모든 요소를 List의 끝에 추가한다. List가 변경되면 true를 반환한다.
boolean	addAll(int index, Collection<? extends E> c)	지정된 index에 지정된 Collection의 Iterator가 반환하는 순서대로 모든 요소를 추가한다.
boolean	removeAll(Collection<?> c)	지정된 Collection에 포함된 모든 요소를 List에서 제거한다.
boolean	retainAll(Collection<?> c)	지정된 Collection에 포함된 List의 요소만 유지한다. 즉, List에서 지정된 Collection에 포함되지 않은 모든 요소를 제거한다.
void	sort(Comparator<? super E> c)	Comparator에서 정의한대로 List를 정렬한다. Comparator가 null인 경우 요소에 Comparable 인터페이스가 구현되어 있어야 하며 자연 순서를 사용해야 한다.
void	clear()	List에서 모든 요소를 제거한다.
E	get(int index)	특정 index에 있는 List의 요소를 반환한다.
E	set(int index, E element)	특정 index에 있는 List의 요소를 지정된 요소로 변경한다.
void	add(int index, E element)	특정 index에 지정된 요소를 삽입한다. 이후 요소들은 오른쪽으로 이동한다.
E	remove(int index)	특정 index의 요소를 제거한다. 이후 요소들은 왼쪽으로 이동한다. 제거된 요소를 반환한다.
int	indexOf(Object o)	List에서 지정된 요소가 처음으로 나타나는 인덱스를 반환한다.  List에 요소가 없으면 -1 반환한다.
int	lastIndexOf(Object o)	List에서 지정된 요소가 마지막으로 발생한 인덱스를 반환한다.

 

---

 

 

3. ArrayList

• 내부적으로 배열로 구현

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

• null 요소 허용
• 시간복잡도
  • 삽입, 삭제 - O(N)
  • 조회 - O(1)
• ArrayList의 인스턴스에는 capacity가 정해져 있다. 요소가 추각될 때 자동으로 capacity가 증가된다.
  • 초기 capacity

private static final int DEFAULT_CAPACITY = 10;

• 동기화를 보장하지 않는다.
  • 동기화를 보장하기 위해 다음과 같이 Wrapping하여 사용할 수 있다. 

List list = Collections.synchronizedList(new ArrayList(...));

• 이 구현체의 iterator와 listIterator는 fail-fast하다. → List가 동시에 구조적으로 수정되면 ConcurrentModificationException 예외를 던진다.

---

 

 

4. LinkedList

• List와 Deque 인터페이의 이중연결리스트 구현

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last;

• null 요소 허용
• 시간복잡도
  • 삽입, 삭제 - O(1)
  • 조회 - O(N)
• 동기화를 보장하지 않는다.
  • 동기화를 보장하기 위해 다음과 같이 Wrapping하여 사용할 수 있다.

List list = Collections.synchronizedList(new LinkedList(...));

• 이 구현체의 iterator와 listIterator는 fail-fast하다. → List가 동시에 구조적으로 수정되면 ConcurrentModificationException 예외를 던진다.