자료구조 | 연결 리스트(Linked List)

연결 리스트는 그 유연성과 동적인 특성 때문에 매우 중요한 자료구조로 간주된다. 

 

연결 리스트는 여러개의 노드가 이어지는 형태로 구성되어 있다. '각 노드 = 데이터(data) + 포인터(next)' 이다.

해당 자료구조의 특징에 대해서는 배열(Array)과의 비교를 통해 이해하는 것이 가장 효율적일 것 같다. 

 

그 이후에 단순 연결 리스트의 변형인 이중 연결 리스트, 원형 연결 리스트에 대해 비교해보자. 

 

---

 

연결 리스트(Linked List) vs 배열 (Array)

 

https://open4tech.com/array-vs-linked-list-vs-hash-table/

 

1. 개념적 차이

배열

: 데이터가 메모리 상 연속된 공간에 할당된다. 즉, '논리적 저장 순서'와 '물리적 저장 순서'가 일치한다.

 

연결 리스트

: 연결 리스트의 노드들은 메모리 상 불연속적인 공간에 존재한다. 즉, '논리적 저장 순서'와 '물리적 저장 순서'가 일치하지 않는다.

 

 

2. 정적 자료구조 vs 동적 자료구조

배열

: 정적 자료구조. 처음 선언 시에 정해진 만큼의 메모리가 할당되고, 크기를 늘리거나 줄일 수 없다. 때문에 데이터의 추가, 삭제에 비교적 추가 작업이 필요하다. (참고로 파이썬의 list는 이를 보완한 동적 배열이다.)

 

동적 배열(Dynamic Array)

• 배열 내 데이터의 크기가 할당된 메모리를 넘어가거나, 크키가 많이 작아질 경우 언어 내부적으로 배열 재할당 및 데이터 복사를 자동 수행함.
• 배열 크기가 바뀔 때 재할당 및 데이터 복사 비용이 들어가지만, 평상시에는 배열에 쓰이는 메모리를 최적화할 수 있다는 장점.

 

연결리스트

: 동적 자료구조. 애초에 구조 자체가 다음 노드를 가리키기만 하면 되기 때문에, 새로운 노드를 연결하는 것이 자유롭다. 따라서 크기의 제약이 없다. 

 

 

3. 데이터 탐색 시간 복잡도

배열에서의 탐색:

메모리 상 연속된 공간에 있기 때문에, index를 통해 바로 접근이 가능하다. 즉, 랜덤 액세스가 가능하며 O(1)의 시간 복잡도를 가진다. 

 

연결 리스트에서의 탐색:

노드의 포인터를 순차적으로 따라가야 하기 때문에, O(n)의 시간 복잡도를 가진다.

 

 

4. 데이터 삽입, 삭제 시간 복잡도

배열에서의 삽입, 삭제:

맨 끝 index에 삽입, 삭제할 경우 O(1). 그 외엔 O(n)의 시간복잡도.

• 원하는 위치에 접근하는 것은 O(1)만에 가능하지만, 그 뒤 데이터의 index를 당겨오거나 밀어주는 시간이 O(n) 소요

 

연결 리스트에서의 삽입, 삭제:

맨 앞 node에 삽입, 삭제할 경우 O(1). 그 외엔 O(n)의 시간복잡도.

• 원하는 위치에 삽입, 삭제는 O(1)만에 가능하지만, 해당 위치를 찾는 것이 O(n) 소요

 

3번과 4번을 정리하면,
- 배열은 데이터의 추가, 삭제가 어렵지만 탐색에서 유리
- 연결 리스트는 데이터의 추가, 삭제에서 유리하지만, 탐색은 비교적 비효율적