단방향 연결리스트와 양방향 연결리스트의 차이점 - 연결리스트는 데이터의 연결이 한 방향으로 되어 있다. 그러나, 양방향연결리스트는 이름 그대로, 데이터끼리 양방향으로 연결되어 있다.
단방향 연결리스트와 비교한 양방향 연결리스트의 장단점
장점 - 각 노드의 앞과 뒤에 있는 노드들의 정보를 저장하기 때문에, 리스트의 앞, 뒤에서 모두 접근이 가능하다.
단점 - 단방향 연결리스트보다, 메모리의 사용이 좀 더 많다.
사용처 본인의 경우, 큐 자료구조를 만들기 위해서 사용했다. 큐는 FIFO 특성을 가진 자료구조이다. 즉 먼저 들어온 것이 먼저 나가야한다. 단방향 연결리스트를 사용해서 큐를 구현하게되면, "데이터의 삽입"은 편하지만, "데이터의 제거"가 필요할 경우, head에서 tail까지의 이동한 후, 데이터를 삭제해야한다. 이는 O(n)의 성능을 가진다.
양방향 연결리스트를 사용하여 큐를 구현하게 되면, "데이터의 삽입"은 편하지만, "데이터의 제거"가 필요할 경우, tail을 이용하여, 데이터를 즉시 삭제할 수 있다. 이는 O(1)의 성능을 가진다. 또한 기존 tail을 제거한 후, 새로운 tail을 지정할 때, tail 노드의 prev를 이용하여, 즉시 새로운 tail을 지정할 수 있다.
어떻게 사용하는가
자바스크립트 코드로 연결리스트 만들어보기
class Node {
constructor(data, next = null, prev = null) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.count = 0;
}
printAll() {
let currentNode = this.head;
let text = '[';
while (currentNode != null) {
text += currentNode.data;
currentNode = currentNode.next;
if (currentNode != null) {
text += ',';
}
}
text += ']';
console.log(text);
}
clear() {
this.head = null;
this.tail = null;
this.count = 0;
}
insertAt(index, data) {
if (index > this.count || index < 0) {
throw new Error('범위를 넘어갔습니다.');
}
let newNode = new Node(data);
// 삽입할 노드의 앞뒤를 전부 고려한다.
if (index === 0) {
// 첫 인덱스에 삽입할 예정이므로, 앞을 고려할 필요가 없다.
newNode.next = this.head;
if (this.head != null) {
this.head.prev = newNode;
}
this.head = newNode;
} else if (index === this.count) {
// 마지막 인덱스에 삽입할 것이므로, 뒤의 노드를 고려할 필요가 없다.
newNode.prev = this.tail;
this.tail.next = newNode;
} else {
let currentNode = this.head;
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
// 중간인덱스에 삽입하므로, 앞 노드를 고려한다.
newNode.prev = currentNode;
currentNode.next = newNode;
// 중간인덱스에 삽입하므로, 뒤 노드를 고려한다.
newNode.next = currentNode.next;
newNode.next.prev = newNode;
}
this.count++;
}
insertLast(data) {
this.insertAt(this.count, data);
}
deleteAt(index) {
if (index > this.count || index < 0) {
throw new Error('제거할 수 없습니다.');
}
let currentNode = this.head;
// 첫 노드를 제거하기 때문에, 제거할 노드의 이전 노드를 고려할 필요가 없다.
if (index === 0) {
let deletedNode = this.head;
// 존재하는 데이터가 1개였을 경우,
if (this.head.next === null) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null
}
this.count--;
return deletedNode;
} else if (index === this.count) {
let deletedNode = this.tail;
this.tail.prev.next = null;
this.tail = this.tail.prev;
this.count--;
return deletedNode;
}else {
for (let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
let deletedNode = currentNode.next;
currentNode.next = currentNode.next.next;
currentNode.next.prev = currentNode;
this.count--;
return deletedNode;
}
}
deleteLast() {
return this.deleteAt(this.count - 1);
}
getNodeAt(index) {
if (index > this.count || index < 0) {
throw new Error('범위를 넘어갔습니다.');
}
let currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
}
export { Node, DoublyLinkedList };
