List 자료구조의 특징

• 중복: 중복 가능, index가 순차적 key로 유일성을 가짐
• 순서: 순서 보장
• 정렬: 정렬 가능, Collections.sort()를 통해 제공됨
• 동기화: (Thread-Safe): 동기화 불가능, 불안전

주요 메소드

• add(Object): 마지막에 데이터 추가
• add(int index, Object): index에 데이터 추가
• set(int index, Object): index에 데이터 변경
• remove(Object): 객체 삭제
• remove(int index): index에 해당하는 값을 삭제
• clear(): 데이터 모두 삭제
• size(): 크기
• get(int Index): 해당 index의 데이터 출력
• contains(Object): 값이 있는지 여부(boolean)
• indexOf(Object): 값의 위치 index (없다면 -1)
• Iterator< E >iterator(): 반복자(iterator) 반환

ArrayList

• 단방향 포인터 구조로 인덱스를 활용해 조회(검색)이 빠름
• 데이터 삽입/삭제시 느림(복사하기 때문)
• thread-safe 보장 안함

시간 복잡도

add(Object) : O(1)
add(int index, Object) :O(n)
remove(Object) : O(n)
remove(int index) : O(n)
get() : O(1)
contains : O(n)
iterator.remove : O(n)

리스트를 수정하여 index를 옮겨야 한다면 시간 복잡도는 배열의 원소의 갯수 n에 비례한다.

LinkedList

• 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 유용
• 데이터 삽입 / 삭제시 빠름
• 데이터 검색성능이 나쁘다. 처음부터 순차적으로 노드를 순화해야 되기 때문에 느림

시간 복잡도

add : O(1)
remove : O(1)
get : O(n)
contains : O(n)
iterator.remove : O(1)