データ構造02二重接続リスト|JS
24250 ワード
画像ソース
二重リンクリスト|二重リンクリスト
prepend: 새 노드를 Head로 붙임
append: Tail 뒤에 덧붙임
delete: 삭제
find: 탐색
deleteTail: Tail 삭제
deleteHead: head 삭제
export default class DoublyLinkedListNode {
constructor(value, next = null, prev = null) {
this.value = value;
this.next = next;
this.prev = previous;
}
toString(callback) {
return callback ? callback(this.value) : `${this.value}`;
}
}
import DoublyLinkedListNode from './DoublyLinkedListNode';
export default class DoublyLinkedList {
constructor(comparatorFunction) {
this.head = null;
this.tail = null;
}
// 새 노드를 Head로 붙임
prepend(value) {
const newNode = new DoublyLinkedListNode(value, this.head);
// 이미 head가 있으면 head의 prev를 새 노드로 설정
// head를 새 노드로 설정
if (this.head) {
this.head.prev = newNode;
}
this.head = newNode;
// tail이 업승ㄹ 경우, 새 노드를 tail로 설정
if (!this.tail) {
this.tail = newNode;
}
return this;
}
// Tail 뒤에 덧붙임
append(value) {
const newNode = new DoublyLinkedListNode(value);
// head가 없으면(노드가 없으면) 새 노드를 head와 tail로 설정
if (!this.head) {
this.head = newNode;
this.tail = newNode;
return this;
}
// 새 노드를 tail의 다음에 설정
this.tail.next = newNode;
// 새 노드의 prev에 tail을 설정
newNode.prev = this.tail;
// 새 노드를 tail로 설정
this.tail = newNode;
return this;
}
// 삭제
delete(value) {
if (!this.head) {
return null;
}
let deletedNode = null;
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === value)) {
// deletedNode 설정
deletedNode = currentNode;
if (deletedNode === this.head) {
// head가 삭제될 예정이라면
// 두번째 노드를 head로 설정
this.head = deletedNode.next;
// 새로운 head의 prev를 null로 설정
if (this.head) {
this.head.prev = null;
}
// 목록에 있는 모든 노드의 값이 인수로 전달된 값과 동일하면
// 모든 노드가 삭제되므로 tail을 업데이트함
if (deletedNode === this.tail) {
this.tail = null;
}
} else if (deletedNode === this.tail) {
// tail이 삭제될 예정이라면
// 뒤에서 두번째 노드를 tail로 설정
this.tail = deletedNode.prev;
this.tail.next = null;
} else {
// 삭제할 노드가 head도 tail도 아닌 경우
const prevNode = deletedNode.prev;
const nextNode = deletedNode.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
}
currentNode = currentNode.next;
}
return deletedNode;
}
// 탐색
find({ value = undefined, callback = undefined }) {
if (!this.head) {
return null;
}
let currentNode = this.head;
while (currentNode) {
// If callback is specified then try to find node by callback.
if (callback && callback(currentNode.value)) {
return currentNode;
}
// If value is specified then try to compare by value..
if (value !== undefined && (currentNode.value === value)) {
return currentNode;
}
currentNode = currentNode.next;
}
return null;
}
// tail 삭제
deleteTail() {
if (!this.tail) {
return null;
}
if (this.head === this.tail) {
// 단 하나의 노드만 있는 경우
const deletedTail = this.tail;
this.head = null;
this.tail = null;
return deletedTail;
}
const deletedTail = this.tail;
this.tail = this.tail.prev;
this.tail.next = null;
return deletedTail;
}
// head 삭제
deleteHead() {
if (!this.head) {
return null;
}
const deletedHead = this.head;
if (this.head.next) {
this.head = this.head.next;
this.head.prev = null;
} else {
this.head = null;
this.tail = null;
}
return deletedHead;
}
}
📚 リファレンス
Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
ダブルリンクリスト
Photo by Alain Pham on Unsplash
Reference
この問題について(データ構造02二重接続リスト|JS), 我々は、より多くの情報をここで見つけました https://velog.io/@protect-me/자료구조02이중연결리스트テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol