[바킹독의 실전 알고리즘] 0x04강 - 연결 리스트

 

정의와 성질

연결 리스트는 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다.

원소는 배열의 원소들처럼 연속하게 저장되는 것이 보장되지 않고, 흩어져 있다.

 

연결 리스트의 성질

• K번째 원소를 확인/변경하기 위해 O(K)가 필요하다.
• 임의의 위치에 원소를 추가 / 임의 위치의 원소 제거는 O(1)이다.
• 원소들이 메모리 상에 연속해 있지 않아 Cache hit rate가 낮지만, 할당이 쉽다.

연결 리스트의 종류

단일 연결 리스트(Singly Linked List)

- 각 원소가 자신의 다음 원소의 주소를 가지고 있는 연결리스트이다.

 

이중 연결 리스트(Doubly Linked List)

- 각 원소가 자신의 이전 원소와 다음 원소의 주소를 가지고 있는 연결 리스트이다.

- 원소가 가지고 있어야 하는 정보가 추가되어 메모리를 더 사용한다는 단점이 있다.

- STL에 연결 리스트가 있는데, 컨테이너의 이름은 list이고 구조는 이중 연결 리스트이다.

 

원형 연결 리스트(Circular Linked List)

- 끝이 처음과 연결되어 있다.

- 각 원소가 이전 원소와 다음 원소의 주소를 모두 들고 있어도 상관이 없다.

 

배열 vs 연결 리스트

배열과 연결 리스트는 원소들 사이의 선후 관계가 일대일로 정의된다.

즉, 원소들 사이에서 첫 번째 원소, 두 번째 원소, ... 와 같은 개념이 존재한다.

그래서 배열과 연결 리스트는 선형 자료구조라고 불린다.

트리, 그래프, 해쉬 등은 비선형 자료구조의 대표적인 예시이다.

 

 

기능과 구현

연결 리스트는 배열과 다르게 임의의 위치에 있는 원소로 가기 위해서는 그 위치에 도달할 때까지 첫 번째부터 순차적으로 방문해야 한다. 원소는 메모리 어딘가에 저장되어 있을 것이지만, 우리는 첫 번째 원소의 주소만을 알고 있기 때문이다.

K번째 원소를 보기 위해서는 O(K)의 시간이 필요하다.

전체에 N개의 원소가 있다고 하면 평균적으로 N/2의 시간이 걸릴 것이므로 O(N)이라고 생각하면 된다.

 

임의의 위치에 원소를 추가하는 연산은 O(1)에 가능하다.

원소를 추가할 때, 배열처럼 뒤의 원소들을 전부 옮기는 작업을 할 필요가 없고 다음 원소의 주소만 변경을 해주면 되기 때문이다.

단, 추가하고 싶은 위치의 주소를 알고 있을 경우에만 O(1)이다.

주소를 모른다면 해당 위치의 원소까지 찾아가는 시간이 추가로 걸려서 O(1)이라고 말할 수 없다.

 

임의 위치의 원소를 제거하는 연산도 O(1)에 가능하다.

원소 삽입과 마찬가지로 다음 원소의 주소를 변경만 해주면 되기 때문이다.

그리고 삭제할 원소는 메모리 누수를 막기 위해 메모리에서 삭제해야 한다.

 

✔️정리

• 임의의 위치에 있는 원소를 확인 / 변경 = O(N)
• 임의의 위치에 있는 원소를 추가 / 임의 위치의 원소 제거 = O(1)

임의의 위치에서 원소를 추가하거나 임의 위치의 원소를 제거하는 연산을 많이 해야 할 경우에는 연결리스트의 사용을 고려해보는 것이 좋다.

 

연결 리스트의 insert와 erase를 구현해 보았다!

 

STL list

STL list에서 push_back, pop_back, push_front, pop_front는 모두 O(1)이다.

 

 

출처: 바킹독님 블로그