[자료구조] Array와 Linked List의 차이는 무엇일까?

Array와 Linked List가 무엇인지 안다면 그 차이는 쉽게 알 수 있을 것이다.

 

Array

배열은 특정 크기만큼 연속된 메모리 공간에 데이터를 저장하는 자료구조이다. 만약 int형 데이터 3개를 저장할 수 있는 배열을 생각해보자. 그렇다면 아래의 그림처럼 연속된 공간에 메모리를 확보하여 데이터를 이곳에 저장할 수 있게 된다.

위의 그림에서 볼 수 있듯이 연속된 공간에 데이터들이 나열되어 있기 때문에 처음 주소만 알면 다른 위치도 쉽게 알 수 있을 것이다. 따라서 배열은 랜덤으로 접근하는 것이 가능하다. 그렇다면 어떻게 랜덤으로 접근하는 것이 가능할까?

 

C언어로 예를 들어보면 배열을 선언했을 때 배열의 주소는 배열에 저장되어 있는 첫 번째 원소의 주소와 같다. 이때 4번째 데이터를 조회한다고 하면 첫 번째 데이터의 주소에서 3개의 데이터 크기만큼 점프를 한다면 4번째 데이터를 조회할 수 있게 된다. 이를 통해 배열은 특정 데이터를 O(1)로 조회할 수 있다.

 

하지만 데이터를 빈번하게 데이터를 추가하거나 삭제할 때는 효율적이지 못하다. 만약 데이터를 중간에 추가하려고 한다. 그렇다면 추가하려고 하는 자리를 비우고 뒤에 있는 데이터를 한 칸씩 뒤로 밀어 야하기 때문이다. 따라서 데이터를 추가하거나 삭제할 때 배열은 좋은 선택이 되지 못한다.

 

Linked List

연결 리스트는 배열과 다르게 연속된 메모리 공간에 저장되어 있지 않다. 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재한다. 그리고 이 노드는 자신의 앞에 있는 데이터와 뒤에 있는 데이터에 대한 주소를 기억하고 있다.

 

만약에 연결 리스트에 저장되어 있는 특정 데이터를 조사하려고 한다면 처음부터 순차적으로 탐색해야 한다. 왜냐하면 노드는 연속된 메모리 공간에 존재하지 않고 모두가 떨어져 있기 때문이다. 탐색을 위해서는 각 노드가 기억하고 있는 앞의 데이터와 뒤의 데이터 주소에 의지할 수 밖에 없다. 따라서 연결 리스트는 특정 데이터를 O(N)으로 조회한다.

 

하지만 데이터를 추가하거나 삭제할 때는 O(1)로 가능하다. 만약 A - B - C 와 같이 연결 리스트에 저장되어 있다고 해보자. B와 C 사이에 Z를 추가한다고 하면 B에서 C를 가리키는 주소를 Z로 변경하고 C에서 B를 가리키는 주소를 Z로 변경하면 되기 때문이다. 또한 Z를 다시 삭제한다고 해도 B가 C를, C가 B를 가리키도록 하면 된다. 따라서 데이터 추가 및 삭제는 O(1)로 가능하다.

---

Array vs Linked List

• Array는 연속된 메모리 공간에 존재하고 Linked List는 메모리 상에서 떨어져 있는 데이터들이 앞의 데이터와 뒤의 데이터를 기억하는 형태로 존재한다.
• Array에 저장되어 있는 데이터를 조회할 때는 O(1)로 가능하지만 Linked List는 O(N)이 소요된다.
• Array에 데이터 추가 및 삭제할 때는 O(N)이 소요되지만 Linked List는 O(1)로 가능하다.
• 추가적으로 Array는 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당인 반면 Linked List는 런타임 환경에서 메모리가 할당되는 동적 메모리 할당이다.
• 또한 배열은 Stack 영역에 메모리 할당이 되고, Linked List는 Heap 영역에 할당이 된다.