[자료구조] 배열(Array) 연결리스트(Linked List) 비교

배열과 연결리스트는 순차적으로 데이터를 저장한다는 점에서 비슷하다. 두 자료구조에 대해서 알아보자.

 

배열(Array)

 

배열은 논리적 저장순서와 물리적 저장순서가 일치하는 자료구조이다. 즉 인덱스(index)로 해당 원소에 접근 할 수 있다. 따라서 원소의 인덱스값을 이용하면 O(1)에 해당 원소에 접근 할 수 있다. 

 

그러나 삭제 또는 삽입의 과정에서 추가적인 시간이 소요될 수 있다. 예를 들어 아래와 같은 상황에서 배열의 첫번째 자리(Arr[0])에 새로운 원소를 추가한다고 하자. 

 

 

위와 같은 상황에서 Arr[0] 에 데이터 10을 추가하기 위해서는, Arr[0] 부터 Arr[4] 까지 모든 원소가 한 칸 씩 오른쪽으로 이동하게 된다.

 

즉, 원소를 삽입할 때 최악의 경우 모든 원소들을 1씩 옮기는 작업이 필요할 수 있다. 따라서 배열의 삽입은 O(n) 의 시간을 요구하게 된다. 마찬가지로 삭제의 경우도 O(n)의 시간을 요구하게 된다.

 

또한 배열은 배열이 꽉 차 있을 경우 메모리를 재할당해야 하거나 최악의 경우에는 삽입이 불가능 할 수 있다.

 

 

연결리스트(Linked List)

연결리스트의 노드는 논리적 저장순서와 물리적 저장순서가 다르다. 배열이 인덱스를 통해 원소에 접근한다면, 연결리스트는 포인터를 이용해 원소에 접근하다. 이 때 처음부터 끝까지 순차적으로 탐색하여 원소를 찾기 때문에 배열보다 접근 속도가 느릴 수 있다. 이 때 최악의 경우 모든 원소를 탐색할 수도 있으므로 탐색은 O(n) 의 시간이 걸린다.

 

삽입/삭제 시에는 노드의 포인터만 재설정 해주면 되므로 그 속도가 배열보다 빠를 수 있다. 그러나 삽입/삭제를 할 위치를 찾기 위해 탐색이 필요해 여전히 시간은 O(n) 이 걸린다.

 

 

정리

위 내용을 표로 정리하면 아래와 같다.

 

 

 

 

---