[알고리즘] ArrayList vs LinkedList

알고리즘을 풀다보면 종종 ArrayList와 LinkedList를 어떻게 적재적소에 사용해야하는 지 고민하게 된다.

 

	ArrayList	LinkedList
특징	배열	노드
	삽입/삭제 시 Shift 연산	다음 노드의 위치를 저장
메모리 공간	연속적	비연속적
저장 순서	논리적 저장 순서 = 물리적 저장 순서	논리적 저장 순서 != 물리적 저장 순서
메모리 할당	정적 메모리 할당	동적 메모리 할당
Search	O(1)	O(n)
	Random Access
Insert	O(n)	맨 앞/뒤: O(1) 중간: O(n) > ArrayList
Delete	O(n)	O(n) > ArrayList

 

ArrayList

- 삽입/삭제가 일어날 때는 Shift 연산으로 인해 시간이 더 걸리게 된다.

- 데이터 삽입 시, 모든 공간이 꽉 차면 새로운 메모리 공간을 할당받아 옮겨야 한다.

- Array선언 시 Complie time에 할당된다.

- index로 접근이 가능하므로 Search 연산이 많을 때 사용하기에 적합하다.

 

LinkedList

- 검색 시, 처음 노드부터 모두 탐색해야 한다.

- 삽입/삭제 시 원소의 위치를 찾는 시간만 발생한다.

- 새로운 노드가 추가될 때 runtime에 할당된다.

- 삽입/삭제가 많을 때 사용하기에 적합하다.