JAVA Collection - List 시간 복잡도

List 상속도

List는 ArrayList, LinkedList, Vector와 Vector를 상속받는 Stack이 있다

Stack은 따로 다루도록 한다.

ArrayList 시간 복잡도

기능	시간복잡도	설명
add	O(1)	마지막 배열 공간을 찾아 삽입해주면 된다.(get이 O(1)이기 때문)
set	O(n)	배열 중간에 공간을 만들기 위해 뒤에 있는 데이터들은 전부 뒤로 한칸씩 이동해야한다.
remove	O(n)	배열 중간에 요소를 삭제할 경우 삭제한 공간을 채우기 위해 뒤에 데이터를 앞으로 한칸씩 이동한다.
get	O(1)	배열 인덱스로 RAM에서 random access가 가능하기 때문에 성능이 좋다. (random access의 원리에 대해서는 잘 모른다... 아시는분 댓글좀 달아주세요)
contains	O(n)	특정 데이터를 찾기 위해서는 배열 전체를 순회해야한다.

 

ArrayList는 메모리 영역에서 배열과 같이 연속된 메모리 공간을 사용한다.

다만 배열은 고정길이이고 ArrayList는 동적으로 버퍼를 할당하여 길이를 늘리거나 줄일 수 있다. (내부적으로 배열을 생성하여 해당 배열이 꽉 찰 경우, 해당 배열보다 더 큰 배열을 생성하여 기존 배열에 있던 데이터를 새로운 배열에 복사하는 형태로 구현되어 있다.)

 

LinkedList 시간 복잡도

기능	시간복잡도	설명
add	O(1)	addFirst이든 addLast이든 자바의 LinkedList에서 head값과 tail값을 참조하고 있기 때문에 순회하지 않고 바로 새로운 노드를 연결해주면 된다.
set	O(n)	중간에 데이터를 삽입하기 위해 첫번째 요소부터 삽입할 요소가 나올때까지 순회해야한다. (get이 O(n)이기 때문) 하지만 데이터를 찾은 경우 노드를 연결해주기만 하면 되기때문에 ArrayList처럼 데이터를 이동해야하는 비용이 없어 보통 ArrayList보다 성능이 좋다고 본다.
remove	O(n)	중간에 데이터를 삭제하기 위해 첫번째 요소부터 삭제할 요소가 나올때까지 순회해야한다. (get이 O(n)이기 때문) 하지만 데이터를 찾은 경우 노드를 연결해주기만 하면 되기때문에 ArrayList처럼 데이터를 이동해야하는 비용이 없어 보통 ArrayList보다 성능이 좋다고 본다.
get	O(n)	중간에 데이터를 조회하기 위해 첫번째 요소부터 조회할 요소가 나올때까지 순회해야한다.
contains	O(n)	특정 데이터를 찾기 위해서는 리스트 전체를 순회해야한다.

자바의 LinkedList 구현 소스를 확인해보니 이중연결리스트(앞의 요소와 뒤의 요소를 모두 참조하는 형태)로 되어 있고 가장 첫번째 요소와 가장 마지막 요소를 참조하는 형태로 구현되어 있었다.

 

어떤 사람들은 LinkedList의 삽입, 삭제를 O(1)로 보기도 한다. 조회에 필요하는 시간복잡도를 제외하고 삽입, 삭제에만 집중하여 본것이다.. 그렇게 따지만 ArrayList도 삽입과 삭제에만 집중한다면 사실 O(1)이다.

시간복잡도는 전체 연산중 가장 큰 것만 고려되기 때문에 삽입, 삭제 그 자체에만 집중하는것이 아니라 전체 연산중 가장 큰것을 보고 판단해야한다.(내 생각)

Vector 시간 복잡도

ArrayList와 구조가 같음으로 생략.

 

Vector와 ArrayList의 차이점은

Vector는 내부적으로 메서드에 synchronized 키워드를 사용하여 Thread Safety하다.

따라서 동기화를 지원하기 때문에, Lock, Unlock의 작업을 반복하여 성능이 좋지 않다.

멀티 스레드 환경에서 리스트를 사용해야한다면 Vector를 사용하고 싱글 스레드이면 ArrayList를 사용하자.