ArrayList vs LinkedList

 

	ArrayList		LinkedList
데이터 저장소	Object array[ ]		노드 Node<E> - E item;
조회
처음	O(1)		O(1)
중간	O(1)		O(n)
끝	O(1)		O(1)
데이터 조작
추가/제거
처음	O(n)		O(1)
중간	접근+ 추가제거 + 밀기 O(1) O(1) + O(n) -> O(n)		접근 + 추가/제거 O(n) + O(1)  -> O(n)
끝	O(1)		O(1)
수정
처음	O(1)		O(1)
중간	O(1)		O(n)
끝	O(1)		O(1)

 

ArrayList 는 List 내의 배열을 사용한다.

따라서, 배열 중간에 데이터를 추가/제거 하지 않는다면 배열 조작만으로 대부분의 작업이 가능하다.

반면, LinkedList 는 E item 을 품는 Node 인스턴스를 Item 갯수만큼 생성(사용)하고, 이동해야 작업 가능하다.

계속해서 인스턴스를 이동해가며 작업해야 하므로, 비효율이 발생한다.

 

또한, 작업에 있어서 가장 많이 발생할, '조회' 작업의 성능은 비교할 바가 못 된다.

O(1) vs O(n)

 

더불어, 데이터 수가 엄~청 많은 게 아니라면, 앞에 추가하던, 중간에 추가하던 큰 성능 차이가 발생하지 않는다.

(하드웨어와 소프트웨어 발전 속도가 으마으마하긴 한가보다. 그래도 데이터량이 많아질수록 차이가 발생하니 이 점은 기억해두자.)

 

따라서, 어지간한 상황이 아니면 LinkedList 보다 ArrayList가 조금 더 낫다.