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

배열과 연결 리스트는 둘 다 데이터를 저장하는 선형 자료구조이다. 그러나 어떠한 상황에 있어서 배열을 사용할 때가 있고 연결 리스트를 사용할 때가 존재한다. 어떤 점에서 그 기준이 나뉘는지 각 자료구조의 특징에 대해 알아보자.

 

배열(Array)

 

배열은 정적(static)인 자료구조이다. 정적인 이유는 배열을 만들기 위해서는 미리 그 크기를 정해놓기 때문에 나중에 데이터의 크기에 변동사항이 생겼을 때 크기를 유동적으로 수정하는 것이 불가능하다. 이러한 특성 때문에 배열은 데이터들이 빈번하게 추가 및 삭제 연산이 이루어지는 곳에서는 쓰기 힘들다.

 

그러나 배열은 연속된 메모리 주소를 할당 받기 때문에 임의 접근(random access)이 가능하다. 즉, 첫 번째 요소의 주소만 알게 된다면 다른 요소의 위치도 쉽게 찾을 수 있으며 랜덤으로 각 요소에 접근하는 것이 가능하다. 이는 데이터를 탐색 및 조회하는 작업에 있어서 좋은 특성이라 볼 수 있다.

 

• 정적(static)인 자료구조
• 크기를 사전에 정해놓기 때문에 수정 불가능 -> 데이터 추가 및 삭제 작업이 힘듬
• 연속된 메모리 주소를 할당받음 -> 임의 접근(random access)이 가능해 데이터 탐색 및 조회 작업이 용이함

 

연결 리스트(Linked List)

 

연결 리스트는 동적(dynamic)인 자료구조이다. 배열과 달리 생성 시 크기를 미리 정하지 않는다. 그렇기 때문에 데이터의 크기에 변동사항이 생겼을 때 유동적으로 가변 할 수 있는 능력을 가진다. 이러한 특성으로 인해 연결 리스트는 데이터의 추가 및 삭제 연산이 빈번하게 이루어지는 곳에서 선호한다. 배열이 요소들로 이루어져 있다면, 연결 리스트는 노드들로 이루어져 있다. 배열은 연속된 메모리 주소를 할당받기 때문에 각 요소들을 탐색할 때 첫 번째 요소의 주소만 알고 있다면 쉽게 탐색 및 조회가 가능하다.

 

그러나 연결 리스트는 연속된 메모리 주소를 할당받지 않는다. 각 노드의 위치는 각 노드의 앞, 뒤 노드만이 알 수 있다. 그렇기 때문에 특정 노드를 탐색 및 조회를 하기 위해서는 첫번째 노드에서부터 각 노드의 포인터가 가리키는 주소를 따라가야한다. 이러한 특성 때문에 데이터를 탐색 및 조회하는 작업이 빈번한 곳에서는 선호하지 않는다.

 

• 동적(dynamic)인 자료구조
• 크기를 사전에 정해놓지 않기 때문에 유연한 크기 변경이 가능 -> 데이터 추가 및 삭제 작업에 용이
• 연속된 메모리 주소를 할당 받지 않음 -> 특정 데이터의 탐색 및 조회 작업이 힘듦

 

차이점

 

두 자료구조의 차이점은 데이터 추가, 삭제, 탐색과 같이 크게 3가지의 작업을 통해서 설명이 가능하다. 이를 시간 복잡도와 연관 지어 설명해 보자.

 

1. 데이터 추가

 

연결 리스트 : 데이터 추가 시 위치에 따라 가지는 시간 복잡도가 다르다. 추가되는 위치가 맨 앞이라면 위치가 특정되기 때문에 O(1)의 시간 복잡도를 가지나 추가되는 위치가 맨 앞이 아니라면 그 위치를 찾기 위해서는 맨 앞에서부터 순차적으로 탐색해야 하기 때문에 O(n)의 시간 복잡도를 가진다.

 

• 추가되는 위치가 맨 앞이라면 O(1)의 시간 복잡도를 가진다.
• 추가되는 위치가 맨 앞이 아니라면 O(n)의 시간복잡도를 가진다.

 

배열 : 배열은 각 위치가 연속된 메모리 주소로 구성되어 있기 때문에 데이터 추가 시 추가되는 위치에 있는 데이터가 한 칸씩 뒤로 밀려나게 된다. 이때 O(n)의 시간 복잡도를 가진다. 그러나 추가되는 위치가 맨 뒤일 경우에는 O(1)의 시간 복잡도를 가진다.

 

• 추가되는 위치가 맨 뒤가 아니라면 O(n)의 시간 복잡도를 가진다. 
• 추가되는 위치가 맨 뒤라면 O(1)의 시간 복잡도를 가진다.

 

2. 데이터 삭제

 

데이터 추가 작업과 같은 양상을 보인다.

 

연결 리스트 : 

 

• 추가되는 위치가 맨 앞이라면 O(1)의 시간 복잡도를 가진다.
• 추가되는 위치가 맨 앞이 아니라면 O(n)의 시간복잡도를 가진다.

 

배열 :

 

• 추가되는 위치가 맨 뒤가 아니라면 O(n)의 시간 복잡도를 가진다. 
• 추가되는 위치가 맨 뒤라면 O(1)의 시간 복잡도를 가진다.

 

3. 데이터 탐색 및 조회

 

연결 리스트 : 메모리 주소가 연속적이지 않고 각 노드의 위치는 각 노드의 앞, 뒤 노드만이 알고 있기 때문에 맨 앞에서부터 순차적인 접근이 필요하다. 그렇기 때문에 O(n)의 시간 복잡도를 가진다.

 

• 순차 접근 방식으로 데이터 탐색은 O(n)의 시간 복잡도를 가진다.

 

배열 : 메모리 주소가 연속적이기 때문에 배열의 첫 번째 요소의 주소만 알게 된다면 특정 위치에 있는 데이터를 쉽게 찾아낼 수 있다. 그렇기 때문에 O(1)의 시간 복잡도를 가진다.

 

• 임의 접근 방식으로 데이터 탐색은 O(1)의 시간 복잡도를 가진다.

 

결론

 

• 데이터 추가 및 삭제의 작업이 빈번하게 혹은 중요하다면 연결 리스트를!
• 데이터 탐색 및 조회 작업이 빈번하게 혹은 중요하다면 배열을!