[자료구조] Array vs LinkedList

Array

• 논리/물리적 저장 순서가 일치 (연속적인 메모리 공간에 저장)
• index를 통한 배열 원소 접근 가능하며, 접근의 시간복잡도는 O(1)
• 원소 삽입/삭제 시 기존 원소들을 shift해야 하므로 O(n)의 시간복잡도를 가진다.
• 제약적 공간을 가진다.

LinkedList

• 논리/물리적 저장 순서 불일치 (다음 노드의 주소값을 가짐)
• index 사용 불가. 접근 시 리스트를 순회해야 하므로 시간복잡도는 O(n)
• 원소의 삽입/삭제가 Array에 비해 빠름.

LinkedList의 원소 삽입/삭제 자체는 빠르지만, 해당 원소를 찾는데 O(n)의 시간이 걸린다. (Bottle neck)

(맨 앞/뒤에만 원소를 삽입한다고 가정하면 O(1)의 시간복잡도를 가진다.)

 

하지만, 원소를 삽입/삭제할 때마다 메모리의 할당/해제가 일어나기 때문에 사실은 O(n)보다는 크다.

사용할 크기를 미리 안다면, 미리 공간을 확보하는 Array가 더 효율적일 수 있다.(항상 상황에 따라 다르다)

 

 

Array vs LinkedList

	Array	LinkedList
접근	O(1)	O(n)
삽입, 삭제	O(n)	O(n) (앞뒤만 하면 O(1))
메모리 할당	정적 메모리 할당(compile time, stack)	동적 메모리 할당(runtime, heap)
크기	선언 시점에 정한 크기	runtime에서 동적으로 변화

 

원소 접근이 중요하다면 Array를, 삽입/삭제가 빈번하다면 LinkedList사용 하는것이 좋을 것 같다.

 

ArrayList

c++의 vector, java의 ArrayList 등이 이에 해당한다.

• 내부적으로 데이터를 배열에서 관리하지만, 보다 편리한 인터페이스를 제공한다. 초기에 크기를 지정하지 않고 runtime에서 늘이거나 줄일 수 있다.(LinkedList의 특성)
• 원소의 추가/삭제는 임시 배열을 생성, 복사하는 방법을 사용하므로 대량의 자료를 추가/삭제한다면 성능이 저하된다.
• index접근이 가능하다.(Array의 특성)