안녕하세요. 이번 시간에는 자료구조 링크드 리스트 에 대해 알아보고자 해요. 리스트 시리즈 역시 4편으로 구성이 되겠습니다.
- 자료구조 링크드 리스트 에 대해 알아봅시다. [현재글]
- c++ stl을 이용해서 더블 링크드 리스트를 구현해 봅시다.
- 배열과 리스트의 차이를 알아봅시다.
- 리스트를 이용해서 lru cache를 구현해 봅시다.
이 글에서는 implements는 다루지 않습니다. 전반적으로 알아두면 좋은 것들에 대해서 간략하게 언급하고 넘어가도록 하겠습니다. 참고로 제가 출제한 모의 코딩 테스트에서 해당 자료구조를 사용하는 문제를 낸 적은 없습니다. 아마 6회에 낼 수도 있을 거 같습니다.
Linked List
링크드 리스트는 노드들로 이루어져 있어요. 많이 쓰이는 double linked list는 각각의 노드에 있는 2개의 필드가 각각 이전 원소와 다음 원소를 가리킨다는 특징이 있어요. 구조를 그려 보면 아래와 같아요.
- prev
- 이전 노드를 가리킵니다.
- next
- 다음 노드를 가리킵니다.
- item
- 실제 노드에 들어 있는 원소입니다.
prev와 next가 각각 이전과 다음 노드를 가리키는 역할을 합니다. single linked list는 prev, next 중 하나가 빠집니다. 보통 링크드 리스트의 내부 구조를 보면 double linked list로 많이 구현이 되어 있습니다. 그 이유는 밑에 후술하도록 하겠습니다.
리스트는 시작과 끝이 있습니다. 이를 각각 head와 tail이라고 합니다.
구현을 편하기 하기 위해 head와 tail에 더미 데이터를 넣는 방법이 있어요. 그러면, 중간 원소를 삭제하는 경우만 고려하면 되기 때문이에요.
List의 insert 연산
List는 왜? 언제 쓸까요? insert, delete가 빠르기 때문이에요. 물론, 위치를 빠르게 찾아가야 한다는 전제 조건이 있습니다. 그래서, insert와 delete 연산을 먼저 학습합니다.
더블 링크드 리스트에서 2와 3 사이에 4를 추가하려고 합니다. 2가 있는 쪽을 prev, 3이 있는 노드를 next가 가리키고 있습니다. 새로 할당한 노드를 new가 가르켜요. 자. 이제 prev와 new가 어떻게 이어야 하나요?
아래 그림을 볼까요?
그림을 보면
- 2가 있는 노드의 next가 4가 있는 노드를 가리켜야 합니다.
- 4가 있는 노드의 next가 3이 있는 노드를 가리켜야 합니다.
이러면 다음 원소를 가리키게 하는 것은 끝났습니다. 이전 원소는 어떻게 가리켜야 할까요? 아래 그림을 보고 이해해 봅시다.
그림을 보면
- 3이 있는 노드의 prev는 4가 있는 노드를 가리키게 했지요.
- 4가 있는 노드의 prev가 2가 있는 노드를 가리키게 했습니다.
그랬더니, 1이 있는 노드, 2가 있는 노드 다음에, 4, 3이 있는 노드가 차례대로 연결되었음을 볼 수 있습니다. 단 4번의 연결 연산으로 끝난 셈입니다. 이렇게 insert 해야 할 위치를 알고 있으면 상수 시간, 진짜 빠르게 insert를 할 수 있습니다.
List의 삭제 연산
삭제는 더 쉽습니다.
1과 3 사이에 있는 2를 지운다고 해 보겠습니다. 지워야 할 원소의 위치를 알고 있다면, 이전 위치와 다음 위치를 빠르게 찾을 수 있지요. 이를 각각 rm.prev, rm.next라 합시다. 자. 이제 다시 1 다음에 원래 2가 연결되어 있었습니다. 그런데, 2가 제거되었다면서요. 그러면 1 다음에 무엇이 연결 되어야 하나요?
1 다음에 3이 연결되어야 합니다. 따라서
- rm.prev, 즉 1을 가지고 있는 노드의 next가
- rm.next, 즉 3을 가지고 있는 노드를 가리켜야 합니다.
그런데, 양방향 리스트는 next만 채웠다고 끝이 아닙니다. 이전 원소도 채워야 하지요. 3의 이전 원소는 어떻게 되어야 하나요?
3의 prev는 1이 되어야 합니다. 즉
- rm.next, 즉 3을 가지고 있는 노드의 prev가
- rm.prev, 즉 1을 가지고 있는 노드를 가리켜야 합니다.
삭제 연산 또한 삭제 위치를 알고 있다면 상수 시간에 처리할 수 있습니다.
single list
single list는 prev, next 중 하나가 빠진다고 했어요. prev가 빠졌다고 해 봅시다.
insert의 경우 별 문제는 안 됩니다. 문제는 delete인데요. 2가 들어있는 노드 삭제한다고 해 보겠습니다. 이미 2의 위치를 아는 경우, double linked list는 prev가 있었기 때문에 이전 원소인 1이 들어있는 노드로 갈 방법이 있습니다.
그런데 next만 있는 single linked list는 그런 게 없네요? 이전 원소로 갈 방법이 없고, 1을 찾아가기 위해서 처음부터 탐색해야 합니다. 따라서, 이전 원소와 다음 원소를 빠르게 찾는 연산을 지원했다면, 삭제 연산도 상당히 빠르게 진행할 수 있었을 겁니다.
즉, single list는 기능이 제한됩니다. 삭제할 위치를 알고 있는 remove 연산에서는, 필드 하나 더 추가하는 손해보다, 이전 원소를 찾는 연산을 빠르게 수행하게 하는 이득이 더 큽니다. 따라서, 공간을 더 쓰더라도 double link list를 쓰는 게 이득이라 할 수 있겠습니다.