List

List 자료 구조

순서가 있고, 중복을 허용하는 자료 구조

List 인터페이스의 주요 메서드

메서드	설명
add(E e)	리스트의 끝에 지정된 요소를 추가한다.
add(int index, E element)	리스트의 지정된 위치에 요소를 삽입한다.
addAll(Collection<? extends E> c)	지정된 컬렉션의 모든 요소를 리스트의 끝에 추가한다.
addAll(int index, Collection<? extends E> c)	지정된 컬렉션의 모든 요소를 리스트의 지정된 위치에 추가한다.
get(int index)	리스트에서 지정된 위치의 요소를 반환한다.
set(int index, E element)	지정한 위치의 요소를 변경하고, 이전 요소를 반환한다.
remove(int index)	리스트에서 지정된 위치의 요소를 제거하고 그 요소를 반환한다.
remove(Object o)	리스트에서 지정된 첫 번째 요소를 제거한다.
clear()	리스트에서 모든 요소를 제거한다.
indexOf(Object o)	리스트에서 지정된 요소의 첫 번째 인덱스를 반환한다.
lastIndexOf(Object o)	리스트에서 지정된 요소의 마지막 인덱스를 반환한다.
contains(Object o)	리스트가 지정된 요소를 포함하고 있는지 여부를 반환한다.
sort(Comparator<? super E> c)	리스트의 요소를 지정된 비교자에 따라 정렬한다.
subList(int fromIndex, int toIndex)	리스트의 일부분의 뷰를 반환한다.
size()	리스트의 요소 수를 반환한다.
isEmpty()	리스트가 비어있는지 여부를 반환한다.
iterator()	리스트의 요소에 대한 반복자를 반환한다.
toArray()	리스트의 모든 요소를 배열로 반환한다.
toArray(T[] a)	리스트의 모든 요소를 지정된 배열로 반환한다.

ArrayList

자바의 ArrayList 특징
1. 배열을 사용해서 데이터를 관리한다.
2. 기본 CAPACITY 는 10이다.( DEFAULT_CAPACITY = 10 )
- CAPACITY 를 넘어가면 배열을 50% 증가한다.
- 10 15 22 33 49로 증가한다. (최적화는 자바 버전에 따라 달라질 수 있다.)
3. 메모리 고속 복사 연산을 사용한다.
- ArrayList 의 중간 위치에 데이터를 추가하면, 추가할 위치 이후의 모든 요소를 한 칸씩 뒤로 이동시켜야한다.
- 자바가 제공하는 ArrayList 는 이 부분을 최적화 하는데, 배열의 요소 이동은 시스템 레벨에서 최적화된 메모리 고속 복사 연산을 사용해서 비교적 빠르게 수행된다. 참고로 System.arraycopy() 를 사용한다.

LinkedList

자바의 LinkedList 특징
1. 이중 연결 리스트 구조
2. 첫 번째 노드와 마지막 노드 둘다 참조

자바 리스트의 성능 비교

기능	배열 리스트	연결 리스트
앞에 추가(삭제)	O(n) - 106ms	O(1) - 2ms
평균 추가(삭제)	O(n) - 49ms	O(n) - 1116ms
뒤에 추가(삭제)	O(1) - 1ms	O(1) - 2ms
인덱스 조회	O(1) - 1ms	O(n) - 평균 439ms
검색	O(n) - 평균 104ms	O(n) - 평균 473ms

추가, 삭제

• 배열 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(1)로 빠르게 찾지만, 추가나 삭제 이후에 데이터를 한칸씩밀어야 한다. 이 부분이 O(n)으로 오래 걸린다.
• 연결 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(n)으로 느리게 찾지만, 실제 데이터의 추가는 간단한 참조 변경으로 O(1)로 빠르게 수행된다.

앞에 추가(삭제)

• 배열 리스트: 추가나 삭제할 위치는 찾는데 O(1), 데이터를 한칸씩 이동 O(n) O(n)
• 연결 리스트: 추가나 삭제할 위치는 찾는데 O(1), 노드를 변경하는데 O(1) O(1)

평균 추가(삭제)

• 배열 리스트: 추가나 삭제할 위치는 찾는데 O(1), 인덱스 이후의 데이터를 한칸씩 이동 O(n/2) => O(n)
• 연결 리스트: 추가나 삭제할 위치는 찾는데 O(n/2), 노드를 변경하는데 O(1) => O(n)

뒤에 추가(삭제)

• 배열 리스트: 추가나 삭제할 위치는 찾는데 O(1), 이동할 데이터 없음 O(1)
• 연결 리스트: 추가나 삭제할 위치는 찾는데 O(1), 노드를 변경하는데 O(1) O(1)
  - 참고로 자바가 제공하는 연결 리스트( LinkedList )는 마지막 위치를 가지고 있다.

인덱스 조회

• 배열 리스트: 배열에 인덱스를 사용해서 값을 O(1)로 찾을 수 있음
• 연결 리스트: 노드를 인덱스 수 만큼 이동해야함 O(n)

검색

• 배열 리스트: 데이터를 찾을 때 까지 배열을 순회 O(n)
• 연결 리스트: 데이터를 찾을 때 까지 노드를 순회 O(n)

데이터를 추가할 때 자바 ArrayList가 직접 구현한 MyArrayList보다 빠른 이유

• 자바의 배열 리스트는 이때 메모리 고속 복사를 사용하기 때문에 성능이 최적화된다.
• 메모리 고속 복사는 시스템에 따라 성능이 다르기 때문에 정확한 계산은 어렵지만 대략 O(n/10) 정도로 추정하자. 상수를 제거하면 O(n)이 된다. 하지만 메모리 고속 복사라도 데이터가 아주 많으면 느려진다.

시간 복잡도와 실제 성능

• 이론적으로 LinkedList의 중간 삽입 연산은 ArrayList보다 빠를 수 있다. 그러나 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 의해 영향을 받는다.
  - 추가로 ArrayList는 데이터를 한 칸씩 직접 이동하지 않고, 대신에 메모리 고속 복사를 사용한다.
• ArrayList는 요소들이 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠르
  다.
• 반면, LinkedList는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느려질 수 있다
• ArrayList의 경우 CAPACITY 를 넘어서면 배열을 다시 만들고 복사하는 과정이 추가된다. 하지만 한번에50%씩 늘어나기 때문에 이 과정은 가끔 발생하므로, 전체 성능에 큰 영향을 주지는 않는다.
  정리하면 이론적으로 LinkedList가 중간 삽입에 있어 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화, 메모리 고속 복사 등을 고려할 때 ArrayList가 실제 사용 환경에서 더 나은 성능을 보여주는경우가 많다.

배열 리스트 vs 연결 리스트

대부분의 경우 배열 리스트가 성능상 유리하다. 이런 이유로 실무에서는 주로 배열 리스트를 기본으로 사용한다.
만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.