이전에 단일 연결 리스트에 대해서 포스팅을 한 적이 있습니다.
https://keykat7.blogspot.com/2022/02/data-structure-singly-linked-list.html
그렇다면 이중 연결 리스트는 무엇이고, 어떻게 구현하면 될까요? 연결 리스트에 대한 기본적인 설명은 위의 포스팅에서 얼추 정리했으니 이번 포스팅에서는 바로 구조와 구현 방법에 대해서 이야기해 보겠습니다.
이중 연결 리스트 구조
이중 연결 리스트의 기본적인 구조
단일 연결 리스트는 노드가 한 방향으로만 연결된 구조였다면, 이중 연결 리스트는 앞, 뒤로 연결이 되는 구조입니다.
일단 맨 앞에 단일 연결 리스트와 똑같이 헤더 노드가 있으며, 그 뒤로 여러 노드가 줄줄이 달려옵니다. 이 때 헤더 노드는 그 다음 노드와 연결되어 있고, 헤더의 다음 노드 또한 헤더 노드와 연결이 되어 있습니다. 이중 연결 리스트는 이렇게 하나의 노드가 앞, 뒤의 노드와 연결이 되는 형태로 만들어지게 됩니다.
맨 뒤에 새로운 타입의 노드가 생겼는데, 맨 앞의 노드를 헤더 노드라고 부르는 것처럼 맨 뒤의 노드는 꼬리 노드라고 부릅니다. (사실 뭐라 부르든 상관 없는데, 저는 보통 이렇게 부릅니다.) 즉, 꼬리 노드는 말 그대로 리스트의 끝을 표시하기 위한 노드입니다. 꼬리 노드는 굳이 필요한 것일까요? 정말 엄밀히 따지자면 굳이 없어도 되긴 합니다만, 없으면 이중 연결 리스트의 장점이 사라집니다. 왜 그럴까요?
이중 연결 리스트 : 꼬리 노드를 사용하는 이유
단일 연결 리스트에서 맨 뒤의 노드를 찾으려면 어떻게 해야할까요? 앞에서부터 차근차근 탐색하면서 다음 노드가 null인 노드를 찾는 방법으로 찾습니다.
못 찾을 것은 없지만, O(n) 의 시간 복잡도가 소요되죠. 그렇게 바람직한 방법은 아닙니다. 그렇다면 단일 연결 리스트에 꼬리 노드를 사용하면 어떨까요? 의미가 없죠. 단일 연결 리스트에서는 꼬리 노드의 이전 노드를 알 수 있는 방법이 없으니까요. 그러나 이중 연결 리스트는 위에서 말했던 것처럼 앞, 뒤로 연결되어 있는 구조이므로 이전 노드를 찾을 수 있습니다.
헤더 노드가 있을 때, 우리는 헤더 노드의 다음 노드에 새로운 노드를 추가할 수 있습니다. 즉, 연결 리스트의 맨 앞에 새로운 노드를 추가한다는 것이죠. 꼬리 노드가 있다는 뜻은 역시 리스트의 맨 뒤에 새로운 노드를 추가할 수 있다는 말이 됩니다.
즉, 단일 리스트는 맨 앞에 새로운 노드를 추가하기 용이하지만, 맨 뒤에는 추가하기 위해서 O(n)을 탐색해야 합니다. 반면 이중 리스트는 맨 앞과 맨 뒤에 새로운 노드를 추가하기 용이하죠. 물론 둘 다 중간에 삽입하는 것은 O(1)로 만들 수 없습니다... 사실 HashMap 등을 이용하면 O(1)로도 만들 수 있는데, 그건 기초를 벗어났으니 넘어갑시다.
어쨌든 이중 연결 리스트는 앞 뒤로 새로운 노드를 추가하기 좋다는 것!
이중 연결 리스트 구현
구현 자체는 단일 연결 리스트와 크게 다르지 않습니다. 다만 헤더 노드와 꼬리 노드를 처음에 만들어주고, 노드를 앞 뒤로 연결해 주어야 한다는 것만 좀 다릅니다.
1. Node 클래스 생성
class Node {
String data; // 데이터는 원하는 것을 넣어주시면 됩니다.
Node next, prev;
public Node(String data) { this.data = data; }
}
단일 연결 리스트와 거의 똑같은데, prev라는 노드가 생겼습니다. 현재 노드의 이전 노드를 가리키는 것이죠.
2. Header와 Tail 노드 생성과 초기화
Node header = new Node("header");
Node tail = new Node("tail");
public void init() {
header.next = tail;
tail.prev = header;
}
위에서 이야기 했듯이 두 노드를 만들어야 합니다. 이 때 중요한 것은, header와 tail의 앞 뒤를 각각 초기화해야 한다는 것입니다. 즉 header의 다음 노드는 tail로, tail의 이전 노드는 header로 설정하고 시작해야 합니다. 그래야 header와 tail이 연결되어 하나의 리스트를 이루고, 새로운 노드가 생길 때마다 header와 tail 사이에 집어넣을 수 있으니까요.
3. DoublyLinkedList 클래스 생성
class DoublyLinkedList {
Node header = new Node("header");
Node tail = new Node("tail");
int size; // 연결 리스트에 들어있는 노드의 개수를 따로 저장합니다. (순회하기 편하려고)
public void init() {
header.next = tail;
tail.prev = header;
}
}
그래서 클래스를 만들면 위와 같은 코드가 될 것입니다. header, tail 노드를 생성하고 그 둘을 잇는 초기화 메서드까지!
4. addFirst
// 맨 앞에 노드 붙이기 (즉, 헤더 바로 다음에 붙이기)
public void addFirst(Node node) {
node.next = header.next;
node.prev = header;
header.next.prev = node;
header.next = node;
size++;
}
단일 연결 리스트와 달리 header -> 삽입 위치 -> 그 다음 노드 의 구조에서 "삽입 위치"에 삽입하기 위해선 삽입할 노드의 뒷노드를 header로, 앞노드를 "그 다음 노드" 로 잡고, header의 다음 노드를 삽입할 노드로, "그 다음 노드"의 뒷노드를 삽입할 노드로 잡아줍니다.
5. add
// idx번째 노드 앞에 붙이기
public void add(Node node, int idx) {
if (idx > size) return;
if (idx == 0) { addFirst(node); return; }
// 헤더부터 시작해서 idx번째 노드 찾기
int cnt = -1;
Node curr = header;
while (curr.next != null) {
// 다음 노드 탐색
curr = curr.next;
// 찾고자 하는 위치에 도달하면 탐색 종료
if (++cnt == idx - 1) break;
}
node.next = curr.next;
node.prev = curr;
curr.next.prev = node;
curr.next = node;
size++;
}
역시 마찬가지 입니다.
6. addLast
public void addLast(Node node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
size++;
}
단일 연결 리스트에서는 맨 뒤의 노드를 먼저 찾은 다음에 추가해 줬는데, 이젠 tail 노드 뒤쪽에 바로 추가할 수 있으니 훨씬 편하게 추가할 수 있습니다.
7. removeFirst
public void removeFirst() {
header.next.next.prev = header;
header.next = header.next.next;
size--;
}
제거할 때는 반대로 header 및 header.next.next에서 header.next와의 연결을 각각 끊어준 다음, header와 header.next.next를 연결해주면 됩니다.
8. remove
public void remove(int idx) {
if (idx > size) return;
if (idx == 0) { removeFirst(); return; }
int cnt = -1;
// 헤더부터 시작해서 idx번째 노드 찾기
Node curr = header;
while (curr != null) {
// 다음 노드 탐색
curr = curr.next;
// 찾고자 하는 위치에 도달하면 탐색 종료
if (++cnt == idx - 1) break;
}
curr.next.next.prev = curr;
curr.next = curr.next.next;
size--;
}
9.removeLast
public void removeLast() {
tail.prev.prev.next = tail;
tail.prev = tail.prev.prev;
size--;
}
마치며..
그렇게 어렵지 않은 내용입니다. 처음 볼 때만 잠깐 헷갈리고 익숙해지면 금방 구현할 수 있을 겁니다. 그림으로 그려보면서 하나씩 따라가보세요.
역시 큰 의미 없는 전체 코드 남기고 마치겠습니다. 그럼 즐거운 코딩하세요!!
class Node {
String data; // 데이터는 원하는 것을 넣어주시면 됩니다.
Node next, prev;
public Node(String data) { this.data = data; }
}
class DoublyLinkedList {
Node header = new Node("header");
Node tail = new Node("tail");
int size; // 연결 리스트에 들어있는 노드의 개수를 따로 저장합니다. (순회하기 편하려고)
public void init() {
header.next = tail;
tail.prev = header;
}
// 맨 앞에 노드 붙이기 (즉, 헤더 바로 다음에 붙이기)
public void addFirst(Node node) {
node.next = header.next;
node.prev = header;
header.next.prev = node;
header.next = node;
size++;
}
// idx번째 노드 앞에 붙이기
public void add(Node node, int idx) {
if (idx > size) return;
if (idx == 0) { addFirst(node); return; }
// 헤더부터 시작해서 idx번째 노드 찾기
int cnt = -1;
Node curr = header;
while (curr.next != null) {
// 다음 노드 탐색
curr = curr.next;
// 찾고자 하는 위치에 도달하면 탐색 종료
if (++cnt == idx - 1) break;
}
node.next = curr.next;
node.prev = curr;
curr.next.prev = node;
curr.next = node;
size++;
}
public void addLast(Node node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
size++;
}
public void removeFirst() {
header.next.next.prev = header;
header.next = header.next.next;
size--;
}
public void remove(int idx) {
if (idx > size) return;
if (idx == 0) { removeFirst(); return; }
int cnt = -1;
// 헤더부터 시작해서 idx번째 노드 찾기
Node curr = header;
while (curr != null) {
// 다음 노드 탐색
curr = curr.next;
// 찾고자 하는 위치에 도달하면 탐색 종료
if (++cnt == idx - 1) break;
}
curr.next.next.prev = curr;
curr.next = curr.next.next;
size--;
}
public void removeLast() {
tail.prev.prev.next = tail;
tail.prev = tail.prev.prev;
size--;
}
public void print() {
Node curr = header;
while (curr != null) {
System.out.printf(curr.data + " ");
curr = curr.next;
}
System.out.println("");
}
public static void main(String[] args) {
DoublyLinkedList linkedList = new DoublyLinkedList();
linkedList.init();
linkedList.print();
linkedList.addFirst(new Node("1"));
linkedList.print();
linkedList.addFirst(new Node("2"));
linkedList.print();
linkedList.addFirst(new Node("3"));
linkedList.print();
linkedList.addFirst(new Node("4"));
linkedList.print();
linkedList.addFirst(new Node("5"));
linkedList.print();
linkedList.add(new Node("6"), 2);
linkedList.print();
linkedList.add(new Node("7"), 0);
linkedList.print();
linkedList.add(new Node("10"), 6);
linkedList.print();
linkedList.add(new Node("71"), 8);
linkedList.print();
linkedList.add(new Node("22"), 1);
linkedList.print();
linkedList.removeFirst();
linkedList.print();
linkedList.removeLast();
linkedList.print();
linkedList.remove(0);
linkedList.print();
linkedList.remove(3);
linkedList.print();
linkedList.remove(5);
linkedList.print();
linkedList.remove(2);
linkedList.print();
}
}
댓글
댓글 쓰기