\(@^0^@)/
[알고리즘] 이중 연결 리스트(Double LinkedList)와 구현 메서드 본문
728x90
- 이중 연결 리스트 (Double Linked List)
- 각 노드가 데이터와 포인터를 가지며, 두 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
- 구현 메서드 (method)
- 노드 개수 / 비어 있는지 확인 : DoubleLinkedList.size(), DoubleLinkedList.isEmpty()
- 순차 출력 / 역 출력 : DoubleLinkedList.printNode(), DoubleLinkedList.printNodeInverse()
- 노드 추가 : DoubleLinkedList.append(), DoubleLinkedList.insert()
- 노드 삭제 : DoubleLinkedList.remove(), DoubleLinkedList.removeAt()
- 데이터 위치 확인 : DoubleLinkedList.indexOf()
- Double Linked List - 1
- Node() : data와 point인 next, prev를 가지고 있는 객체
DoubleLinkedList() : head, tail과 length를 가지고 있는 객체
size() : 연결 리스트 내 노드 개수 확인
isEmpty() : 객체 내 노드 존재 여부 파악
- Node() : data와 point인 next, prev를 가지고 있는 객체
// Node() : data와 point인 next, prev를 가지고 있는 객체
function Node(data) {
this.data = data;
this.next = null;
this.prev = null;
}
// LinkedList() : head, tail과 length를 가지고 있는 객체
function DoubleLinkedList() {
this.head = null;
this.tail = null;
this.length = 0;
}
// size() : 연결 리스트 내 노드 개수 확인
DoubleLinkedList.prototype.size = function () {
return this.lenghth;
};
// isEmpty() : 객체 내 노드 존재 여부 파악
DoubleLinkedList.prototype.isEmpty = function () {
return this.length === 0;
};
let dll = new DoubleLinkedList();
let node;
console.log(dll); // DoubleLinkedList { head: null, tail: null, length: 0 }
node = new Node(123);
dll.head = node;
dll.tail = node;
dll.length++;
console.log(dll);
/*
DoubleLinkedList {
head: Node { data: 123, next: null, prev: null },
tail: Node { data: 123, next: null, prev: null },
length: 1
} */
node = new Node(456);
dll.head.next = node;
node.prev = dll.tail;
dll.tail = node;
dll.length++;
console.log(dll);
/*
DoubleLinkedList {
head: <ref *1> Node {
data: 123,
next: Node { data: 456, next: null, prev: [Circular *1] },
prev: null
},
tail: <ref *2> Node {
data: 456,
next: null,
prev: <ref *1> Node { data: 123, next: [Circular *2], prev: null }
},
length: 2
} */- 기존의 연결 리스트와 다르게 Node 메서드에 prev, DoubleLinkedList 메서드에 tail이 추가되어,
좀 더 다양한 리스트들이 구현 가능하다.
- Double Linked List - 2
- printNode() : 노드 정방향 출력
printNodeInverse() : 노드 역방향 출력
append() : 연결 리스트 가장 끝에 노드 추가
- printNode() : 노드 정방향 출력
// printNode() : 노드 정방향 출력
DoubleLinkedList.prototype.printNode = function () {
process.stdout.write("head -> ");
for (let node = this.head; node != null; node = node.next) {
process.stdout.write(`${node.data} -> `);
}
console.log("null");
};
// printNodeInverse() : 노드 역방향 출력
DoubleLinkedList.prototype.printNodeInverse = function () {
let temp = [];
process.stdout.write("null <- ");
for (let node = this.tail; node != null; node = node.prev) {
temp.push(node.data);
}
for (let i = temp.length - 1; i >= 0; i--) {
process.stdout.write(`${temp[i]} <- `);
}
console.log("tail");
};
// append() : 연결 리스트 가장 끝에 노드 추가
DoubleLinkedList.prototype.append = function (value) {
let node = new Node(value);
if (this.head === null) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
this.length++;
};
let dll = new DoubleLinkedList();
dll.append(1);
dll.append(10);
dll.append(100);
dll.printNode(); // head -> 1 -> 10 -> 100 -> null
dll.printNodeInverse(); // null <- 1 <- 10 <- 100 <- tail- printNodeInverse() : 대부분의 코드가 printNode메서드와 비슷하지만 약간 다른 점이 있다.
- inverse 출력하기 위해 temp라는 배열에 데이터들을 tail부터 임시 저장한다.
temp에 저장된 배열 순서 : [100, 10, 1] - temp를 반복문 돌릴 때, 맨 끝에 있는 인덱스의 데이터부터 출력하는 조건을 설정해준다.
그렇게 해준다면, 1부터 출력되어, null <- 1 <- 10 <- 100 <- tail로 리턴됨.
- inverse 출력하기 위해 temp라는 배열에 데이터들을 tail부터 임시 저장한다.
- append() : 기존의 연결 리스트는 while문으로 추가를 했었지만, 이중 연결 리스트는 tail을 통해서 바로 추가 가능.
위의 이중 연결 리스트에서 append(5)를 하게 될 경우 메서드 로직에 따라서,
1. this.head가 null이 아니기 때문에, else문으로 들어간다.
2. this.tail.next가 node으로, 꼬리 부분을 5에 연결하고 (파란색 화살표)
node.prev는 this.tail에 할당하기에 기존의 tail 끝부분에 대입한다. (초록 화살표)
마지막으로 this.tail은 node이므로, tail을 5에 붙여준다. (빨간 화살표)
node의 끝부분에 null이 붙어있으므로, 마지막에 null이 표시된다.
3. 따라서, head -> 1 -> 10 -> 5 -> null / null <- 1 <- 10 <- 5 <- tail로 나타난다.
- Double Linked List - 3
- insert() : position 위치에 노드 추가
// insert() : position 위치에 노드 추가
DoubleLinkedList.prototype.insert = function (value, position = 0) {
if (position < 0 || position > this.length) {
return false;
}
let node = new Node(value),
current = this.head,
index = 0,
prev;
if (position === 0) {
if (this.head === null) {
this.head = node;
this.tail = node;
} else {
node.next = current;
current.prev = node;
this.head = node;
}
} else if (position === this.length) {
current = this.tail;
current.next = node;
node.prev = current;
this.tail = node;
} else {
while (index++ < position) {
prev = current;
current = current.next;
}
node.next = current;
prev.next = node;
current.prev = node;
node.prev = prev;
}
this.length++;
return true;
};
let dll = new DoubleLinkedList();
dll.insert(1);
dll.insert(10);
dll.insert(100);
dll.printNode(); // head -> 100 -> 10 -> 1 -> null
dll.printNodeInverse(); // null <- 100 <- 10 <- 1 <- tail
dll.insert(2, 1);
dll.insert(3, 3);
dll.printNode(); // head -> 100 -> 2 -> 10 -> 3 -> 1 -> null
dll.printNodeInverse(); // null <- 100 <- 2 <- 10 <- 3 <- 1 <- tail- position이 0일 경우, 만약 this.head가 null이라면 head와 tail을 node로 할당.
position이 0이지만 this.head가 null이 아닐 경우, 헤드가 가리키는 것을 신규 node로 설정하여 앞 뒤 연결. - position이 연결 리스트의 끝(tail 바로 앞부분) 일 경우, 1번과 반대로 tail부분에 신규 node를 업데이트하여 연결.
- 그 외 나머지 position은 index가 position보다 커질 때까지 반복문을 돈다.
예시로 insert(2, 1)이라면 position 1에서 value값 2를 추가한다.(position 위치 앞에 추가하며 0부터 시작)
- Double Linked List - 4
- remove() : value 데이터를 찾아 노드 삭제
// remove() : value 데이터를 찾아 노드 삭제
DoubleLinkedList.prototype.remove = function (value) {
let current = this.head,
prev = current;
while (current.data != value && current.next != null) {
prev = current;
current = current.next;
}
if (current.data != value) {
return null;
}
if (current === this.head) {
this.head = current.next;
if (this.length === 1) this.tail = null;
else this.head.prev = null;
} else if (current === this.tail) {
this.tail = current.prev;
this.tail.next = null;
} else {
prev.next = current.next;
current.next.prev = prev;
}
this.length--;
return current.data;
};
let dll = new DoubleLinkedList();
dll.insert(1);
dll.insert(10);
dll.insert(100);
dll.insert(2, 1);
dll.insert(3, 3);
dll.printNode(); // head -> 100 -> 2 -> 10 -> 3 -> 1 -> null
dll.printNodeInverse(); // null <- 100 <- 2 <- 10 <- 3 <- 1 <- tail
console.log(dll.remove(1000)); // null
dll.printNode(); // head -> 100 -> 2 -> 10 -> 3 -> 1 -> null
dll.printNodeInverse(); // null <- 100 <- 2 <- 10 <- 3 <- 1 <- tail
console.log(dll.remove(1)); // 1
dll.printNode(); // head -> 100 -> 2 -> 10 -> 3 -> null
dll.printNodeInverse(); // null <- 100 <- 2 <- 10 <- 3 <- tail
console.log(dll.remove(2)); // 2
dll.printNode(); // head -> 100 -> 10 -> 3 -> null
dll.printNodeInverse(); // null <- 100 <- 10 <- 3 <- tail
console.log(dll.remove(10)); // 10
dll.printNode(); // head -> 100 -> 3 -> null
dll.printNodeInverse(); // null <- 100 <- 3 <- tail- Double Linked List - 5
- removeAt() : position 위치 노드 삭제
// removeAt() : position 위치 노드 삭제
DoubleLinkedList.prototype.removeAt = function (position = 0) {
if (position < 0 || position >= this.length) {
return null;
}
let current = this.head,
index = 0,
prev;
if (position === 0) {
this.head = current.next;
if (this.length === 1) this.tail = null;
else this.head.prev = null;
} else if (position === this.length - 1) {
current = this.tail;
this.tail = current.prev;
this.tail.next = null;
} else {
while (index++ < position) {
prev = current;
current = current.next;
}
prev.next = current.next;
current.next.prev = prev;
}
this.length--;
return current.data;
};
let dll = new DoubleLinkedList();
dll.insert(1);
dll.insert(10);
dll.insert(100);
dll.insert(2, 1);
dll.insert(3, 3);
dll.printNode();
dll.printNodeInverse();
console.log(dll.removeAt(1000)); // null
dll.printNode(); // head -> 100 -> 2 -> 10 -> 3 -> 1 -> null
dll.printNodeInverse(); // null <- 100 <- 2 <- 10 <- 3 <- 1 <- tail
console.log(dll.removeAt(4)); // 1
dll.printNode(); // head -> 100 -> 2 -> 10 -> 3 -> null
dll.printNodeInverse(); // null <- 100 <- 2 <- 10 <- 3 <- tail
console.log(dll.removeAt()); // 100
dll.printNode(); // head -> 2 -> 10 -> 3 -> null
dll.printNodeInverse(); // null <- 2 <- 10 <- 3 <- tail
console.log(dll.removeAt(1)); // 10
dll.printNode(); // head -> 2 -> 3 -> null
dll.printNodeInverse(); // null <- 2 <- 3 <- tail- removeAt은 position 위치 노드를 삭제하고, remove는 value값을 찾아서 노드를 삭제한다.
둘의 차이점을 분명히 기억해두자.
- Double Linked List - 6
- indexOf() : value 값을 갖는 노드 위치 반환
remove2() : indexOf + removeAt = remove
- indexOf() : value 값을 갖는 노드 위치 반환
// indexOf() : value 값을 갖는 노드 위치 반환
DoubleLinkedList.prototype.indexOf = function (value) {
let current = this.head,
index = 0;
while (current != null) {
if (current.data === value) {
return index;
}
index++;
current = current.next;
}
return -1;
};
// remove2() : indexOf + removeAt = remove
DoubleLinkedList.prototype.remove2 = function (value) {
let index = this.indexOf(value);
return this.removeAt(index);
};
let dll = new DoubleLinkedList();
dll.insert(1);
dll.insert(10);
dll.insert(100);
dll.insert(2, 1);
dll.insert(3, 3);
dll.printNode();
dll.printNodeInverse();
console.log(dll.indexOf(1000)); // -1
console.log(dll.indexOf(1)); // 4
console.log(dll.indexOf(100)); // 0
console.log(dll.indexOf(10)); // 2
console.log(dll.remove(1000)); // null
dll.printNode(); // head -> 100 -> 2 -> 10 -> 3 -> 1 -> null
dll.printNodeInverse(); // null <- 100 <- 2 <- 10 <- 3 <- 1 <- tail
console.log(dll.remove(1)); // 1
dll.printNode(); // head -> 100 -> 2 -> 10 -> 3 -> null
dll.printNodeInverse(); // null <- 100 <- 2 <- 10 <- 3 <- tail
console.log(dll.remove(2)); // 2
dll.printNode(); // head -> 100 -> 10 -> 3 -> null
dll.printNodeInverse(); // null <- 100 <- 10 <- 3 <- tail
console.log(dll.remove(100)); // 100
dll.printNode(); // head -> 10 -> 3 -> null
dll.printNodeInverse(); // null <- 10 <- 3 <- tail- 기존 단일 연결 리스트와 똑같은 로직. 그럼에도 불구하고, 모든 값들이 잘 출력되는 것을 볼 수 있다.
[ 출처, 참고 : 제로베이스 프런트엔드 스쿨 ]
728x90
'알고리즘' 카테고리의 다른 글
| [알고리즘] 재귀를 사용한 stringifyNumbers (0) | 2022.06.22 |
|---|---|
| [알고리즘] 스택(Stack)과 구현 메서드 (0) | 2022.05.09 |
| [알고리즘] 연결 리스트(LinkedList)와 구현 메서드 (0) | 2022.05.03 |
| Big O Notation (0) | 2021.12.14 |
| [JS] 백준 1152 단어의 개수 (0) | 2021.10.16 |
'알고리즘' Related Articles
more
