LRU에 대해 공부하던 도중 양방향 연결리스트 (Doubly Linked List) 관련 내용을 다시 접하게 되었다.
LRU Cache는 내부에서 양방향 연결리스트를 사용한다.
최근 참조되거나 쓰여진 데이터를 head 쪽에 위치시키고, 오랜동안 사용되지 않은 데이터는 tail 쪽으로 이동하는 방식으로 관리된다.
(구현하기에 따라 head와 tail이 반대인 케이스도 가능하다.)
이 과정에서 노드간 리와이어링이 발생하고, 그 과정에서 이전 노드에 대한 참조를 필요로 하게된다.
이번 글에서는 양방향 연결리스트(Doubly Linked List) 에 대한 전반적인 내용을 정리 해보고자 한다.
단방향 연결리스트의 한계
단방향 연결리스트(Single Linked List)는 다음 노드에 대한 참조 값을 저장하고 있지만, 이전 노드는 참조하지 않는다. 따라서 head에서 tail의 방향으로만 포인터를 이동시킬 수 있다.
이처럼 단방향 연결리스트에서는 tail의 이전 노드는 참조가 불가능한데, 만약 tail의 이전 노드를 찾는 경우, 두번의 연산을 거쳐야 한다.
그림에서의 4번 노드를 찾는 과정은 다음과 같다.
- head에서 시작하여 tail 이전 노드의 이전 노드까지 이동한다.
- 이전 노드의
next로 대상을 참조한다.
이처럼 단방향 연결리스트는 구현이 비교적 간단하다는 장점은 있지만, 데이터의 탐색 뿐만 아니라 삽입, 삭제에서 비효율적인 추가 연산을 발생시킨다.
반면 양방향 연결리스트는 각 노드마다 이전 노드에 대한 참조를 저장하고, 이를 통해 tail에서 head 방향으로의 탐색이 가능해진다.
이와 같은 특징은 새로운 노드 삽입, 삭제 연산에서 단방향 연결 리스트와의 차이점을 발생시킨다.
구체적으로 어떤 차이점을 가지는지 살펴보자.
양방향 연결리스트 (Doubly Linked List)
양방향 연결 리스트의 노드는 데이터, 이전 노드 참조(prev), 다음 노드에 대한 참조(next)로 구성된다.
노드 내부에서 앞 뒤 노드의 참조 값을 모두 저장하여, 필요에 따라 이전 노드의 방향으로도 탐색, 삽입, 삭제 오퍼레이션이 가능해진다.
노드의 삽입
1 ~ 5 데이터가 저장된 5개의 노드가 있다. 여기에 데이터 6을 저장하는 시나리오는 다음과 같다.
- 리스트 첫 인덱스(head)에 삽입
- 리스트의 마지막 인덱스(tail)에 삽입
- 중간에 삽입
첫 인덱스(head)에 삽입
첫 인덱스인 기존 head가 가리키던 위치에 저장하는 경우, 다음의 절차로 수행된다.
- 새로운 노드의 다음 노드 참조 값으로 기존 head가 가리키던 1번 노드를 저장한다.
- 1번 노드의 이전 노드로 새로운 노드를 가리킨다.
- head의 위치를 새로운 노드로 이동시킨다.
마지막 인덱스(tail)에 삽입
마지막 위치(tail)에 저장하는 경우도 head에 저장하는 케이스와 유사하다. 다음의 순서로 수행된다.
- 새로운 노드의 이전(prev) 노드로 tail이 가리키고 있는 노드의 참조 값을 저장한다.
- tail이 가리키고 있는 노드의 다음 노드(next)에 새로운 노드(6)의 참조 값을 저장한다.
- tail이 가리키는 위치를 추가된 새로운 노드로 이동시킨다.
중간에 삽입
리스트 중간 위치에 삽입하는 경우, 앞 뒤 노드의 참조 값을 모두 변경해줘야 한다. 뿐만 아니라 새로 삽입되는 노드의 이전 노드, 다음 노드 또한 연결이 필요하다.
각 과정은 다음의 순서로 수행된다.
- 새로운 노드가 저장될 인덱스의 이전 노드까지 이동한다.
current라는 포인터를 선언하고 사용하였다.
- 새로운 노드의 다음 노드(next)에 current의 다음 노드 참조 값을 저장한다. (
newNode.next = current.next)
- 새로운 노드의 이전 노드(prev)로 current의 다음 노드 참조 값을 저장한다. (
newNode.prev = current)
- current 노드의 다음 노드(next) 값으로 새로운 노드 참조 값을 저장한다.
(
current.next = newNode)
- 새 노드의 다음 노드(next)의 이전 노드(next.prev)로 새 노드를 저장한다.
(
newNode.next.prev = newNode)
노드의 삭제
삭제 또한 삽입 연산과 동일하게 다음의 세 가지 케이스가 가능하다.
- 첫 인덱스 노드(head) 삭제
- 마지막 인덱스 노드(tail) 삭제
- 중간 노드 삭제
첫 인덱스 노드(head) 삭제
첫 노드를 삭제하는 경우, 첫 노드 삽입 연산보다 간단하다.
그림과 같이 head가 1번 노드를 가리키고 있는 경우, 어떤 과정으로 삭제 연산이 발생하는지 살펴보자.
- head의 위치를 삭제 할 첫 인덱스 노드의 다음 노드로 이동시킨다.
- head가 가리키는 노드의 이전 노드 참조를 끊어낸다.
마지막 인덱스 노드(tail) 삭제
마지막 노드의 삭제도 head와 동일한 연산을 한다.
과정은 다음과 같다.
- tail의 위치를 마지막 노드의 이전 노드(prev)로 이동시킨다.
- tail이 가리키는 노드의 다음 노드(next)에 대한 참조를 끊어낸다.
중간 노드 삭제
중간 노드가 삭제되는 경우, head, tail의 케이스보다 약간의 연산이 더 추가되는데, 삭제 될 노드의 이전과 다음 노드에 대한 참조를 서로 연결해줘야 한다.
3번 노드가 삭제되는 예시를 통해 이해해보자. 중간 노드 삭제는 다음의 순서로 수행된다.
- 삭제 될 노드의 이전 노드까지 이동한다.
탐색을 수행하기 위해current라는 포인터를 선언하고 사용하였다.
- current가 가리키는 노드의 다음 노드로 삭제 될 노드(3)의 다음 노드를 할당한다.
(current.next = current.next.next)
- current가 가리키는 노드의 다음 노드(4)의 이전 노드로 현재 노드(current)를 참조한다.
(current.next.previous = current)