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

단일 연결 리스트는 오로지 한 방향으로만 탐색할 수 있었는데요, 탐색 중에 다시 이전 데이터를 탐색하고 싶을 경우에는 어떻게 해야 할까요? 오늘은 단일 연결 리스트의 단점을 보완하여 양뱡향 탐색이 가능하게 된 이중 연결 리스트에 대해 알아보도록 하겠습니다.

 

📄 이중 연결 리스트

이중 연결 리스트는 이름과 같이 이중으로 앞과 뒤를 연결해주는 리스트입니다.  저번 포스트에서 사용한 노드는 data와 next를 가지고 있었는데요, 여기서 앞 노드를 참조하는 prev이라는 값을 추가해보도록 하겠습니다.

prev 값이 앞 노드이기 때문에 화살표를 1) 처럼 표시해도 되지만 2) 처럼 양방향 화살표로 표시하는것이 편리합니다. 참고로 Head의 prev 값은 null입니다.

 

크게 달라진 점은 없지만 이로 인해 양방향으로 탐색이 가능하게 되었습니다. 이 경우에도 탐색은 일일히 확인해야 하기 때문에 시간복잡도는 $O(n)$이며, 삽입 및 삭제의 경우에도 서로 연결하거나 연결을 끊는 작업만 해주면 되기 때문에 $O(1)$으로 표현됩니다.

 

자바스크립트로 구현할 때의 Node 클래스 에도 다음과 같이 prev 가 추가됩니다.

class Node() {
    constructor(data) {
    	this.data = data;
       	this.prev = null;
        this.next = null;
    }
}

 

🧮 이중 연결 리스트의 연산

연산에 대한 내용도 크게 달라지지는 않습니다. 한가지 주의해야 할 점은, 앞 노드와 뒷 노드를 참조하고 있기 때문에 노드의 참조를 신경써서 바꾸어주어야 한다는 것입니다.

 

🔎 탐색

이중 연결 리스트에서도 탐색은 Head 부터 Tail 까지 하나씩 확인해야만 합니다. 따라서 $O(n)$의 시간복잡도로 표현됩니다.

 

➕ 삽입

삽입을 할 때에는 인접한 노드들의 연결을 끊고 그 사이에 새로운 노드를 넣게 됩니다. 연결 작업만 이루어지기 때문에 $O(1)$의 시간복잡도로 표현됩니다.

Node와 Tail 사이에 새로운 노드 Node2를 넣는 경우입니다.

Node의 next 값을 Node2로, Node2의 next값은 Tail로 바꾸어 줍니다.

 

단일연결리스트와 다르게 prev가 생겼기 때문에 해당 데이터도 바꾸어 주어야 합니다. Node2의 prev를 Node로, Tail의 prev를 Node2로 넣어줍시다. 이와 같은 과정을 자바스크립트 코드로 표현하게 되면 다음과 같습니다.

//node와 this.tail이 있다고 가정
const node2 = new Node(newData); //node2 생성
node.next = node2; //node의 next에 node2 연결
node2.prev = node; //node2의 prev에 node 연결
node2.next = this.tail; //node2의 next에 tail 연결
this.tail.prev = node2 //tail의 prev에 node2 연결

 

 

➖ 삭제

삭제하고 싶은 노드의 연결을 끊고, 앞뒤 노드를 연결해주면 됩니다. 삭제 또한 연결 작업만 이루어지기 때문에 $O(1)$의 시간복잡도로 표현됩니다.

Node2를 다시 삭제하는 과정을 보겠습니다.

Node의 next를 Tail 노드로 바꾸어 주고, Tail의 prev를 Node로 바꾸어 줍니다. 이 때 Node2 는 prev과 next 모두 null로 바꾸어 연결을 끊어줍니다. 역시 자바스크립트로 구현하면 다음과 같습니다.

//node와 this.tail이 있다고 가정
node.next = this.tail; //node의 next에 tail 연결
this.tail.prev = node; //tail의 prev에 node 연결
node2.prev = null; //node2의 prev을 null로 변경
node2.tail = null; //node2의 tail을 null로 변경

 

prev가 추가되면서 약간 더 복잡해졌기 때문에, 삽입/삭제를 하는 경우 prev 값과 next 값이 잘 들어갔는지 확인해주는 것이 좋습니다.