Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6b354ad

Browse files
huzaimatrekhleb
authored andcommitted
Added doubly linked list (trekhleb#92)
* Added doubly linked list* improved doubly linked list coverage
1 parentfef2aa7 commit6b354ad

File tree

5 files changed

+510
-0
lines changed

5 files changed

+510
-0
lines changed
Lines changed: 211 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,211 @@
1+
importDoublyLinkedListNodefrom'./DoublyLinkedListNode';
2+
importComparatorfrom'./../../utils/comparator/Comparator';
3+
4+
exportdefaultclassDoublyLinkedList{
5+
/**
6+
*@param {Function} [comparatorFunction]
7+
*/
8+
constructor(comparatorFunction){
9+
/**@var DoublyLinkedListNode */
10+
this.head=null;
11+
12+
/**@var DoublyLinkedListNode */
13+
this.tail=null;
14+
15+
this.compare=newComparator(comparatorFunction);
16+
}
17+
18+
/**
19+
*@param {*} value
20+
*@return {DoublyLinkedList}
21+
*/
22+
prepend(value){
23+
// Make new node to be a head.
24+
constnewNode=newDoublyLinkedListNode(value,this.head);
25+
26+
// If there is head, then it won't be head anymore
27+
// Therefore, make its previous reference to be new node (new head)
28+
// Then mark the new node as head
29+
if(this.head){
30+
this.head.previous=newNode;
31+
}
32+
this.head=newNode;
33+
34+
// If there is no tail yet let's make new node a tail.
35+
if(!this.tail){
36+
this.tail=newNode;
37+
}
38+
39+
returnthis;
40+
}
41+
42+
/**
43+
*@param {*} value
44+
*@return {DoublyLinkedList}
45+
*/
46+
append(value){
47+
constnewNode=newDoublyLinkedListNode(value);
48+
49+
// If there is no head yet let's make new node a head.
50+
if(!this.head){
51+
this.head=newNode;
52+
this.tail=newNode;
53+
54+
returnthis;
55+
}
56+
57+
// Attach new node to the end of linked list.
58+
this.tail.next=newNode;
59+
60+
// Attach current tail to the new node's previous reference
61+
newNode.previous=this.tail;
62+
63+
// Set new node to be the tail of linked list.
64+
this.tail=newNode;
65+
66+
returnthis;
67+
}
68+
69+
/**
70+
*@param {*} value
71+
*@return {DoublyLinkedListNode}
72+
*/
73+
delete(value){
74+
if(!this.head){
75+
returnnull;
76+
}
77+
78+
letdeletedNode=null;
79+
letcurrentNode=this.head;
80+
81+
do{
82+
if(this.compare.equal(currentNode.value,value)){
83+
deletedNode=currentNode;
84+
85+
if(deletedNode===this.head){
86+
// set head to second node, which will become new head
87+
this.head=deletedNode.next;
88+
89+
// set new head's previous to null
90+
if(this.head){
91+
this.head.previous=null;
92+
}
93+
94+
// If all the nodes in list has same value that is passed as argument
95+
// then all nodes will get deleted, therefore tail needs to be updated
96+
if(deletedNode===this.tail){
97+
this.tail=null;
98+
}
99+
}elseif(deletedNode===this.tail){
100+
// set tail to second last node, which will become new tail
101+
this.tail=deletedNode.previous;
102+
this.tail.next=null;
103+
}else{
104+
constpreviousNode=deletedNode.previous;
105+
constnextNode=deletedNode.next;
106+
previousNode.next=nextNode;
107+
nextNode.previous=previousNode;
108+
}
109+
}
110+
111+
currentNode=currentNode.next;
112+
}while(currentNode);
113+
114+
returndeletedNode;
115+
}
116+
117+
/**
118+
*@param {Object} findParams
119+
*@param {*} findParams.value
120+
*@param {function} [findParams.callback]
121+
*@return {DoublyLinkedListNode}
122+
*/
123+
find({ value=undefined, callback=undefined}){
124+
if(!this.head){
125+
returnnull;
126+
}
127+
128+
letcurrentNode=this.head;
129+
130+
while(currentNode){
131+
// If callback is specified then try to find node by callback.
132+
if(callback&&callback(currentNode.value)){
133+
returncurrentNode;
134+
}
135+
136+
// If value is specified then try to compare by value..
137+
if(value!==undefined&&this.compare.equal(currentNode.value,value)){
138+
returncurrentNode;
139+
}
140+
141+
currentNode=currentNode.next;
142+
}
143+
144+
returnnull;
145+
}
146+
147+
/**
148+
*@return {DoublyLinkedListNode}
149+
*/
150+
deleteTail(){
151+
if(!this.tail){
152+
returnnull;
153+
}elseif(this.head===this.tail){
154+
constdeletedTail=this.tail;
155+
this.head=null;
156+
this.tail=null;
157+
158+
returndeletedTail;
159+
}
160+
161+
constdeletedTail=this.tail;
162+
this.tail=this.tail.previous;
163+
this.tail.next=null;
164+
165+
returndeletedTail;
166+
}
167+
168+
/**
169+
*@return {DoublyLinkedListNode}
170+
*/
171+
deleteHead(){
172+
if(!this.head){
173+
returnnull;
174+
}
175+
176+
constdeletedHead=this.head;
177+
178+
if(this.head.next){
179+
this.head=this.head.next;
180+
this.head.previous=null;
181+
}else{
182+
this.head=null;
183+
this.tail=null;
184+
}
185+
186+
returndeletedHead;
187+
}
188+
189+
/**
190+
*@return {DoublyLinkedListNode[]}
191+
*/
192+
toArray(){
193+
constnodes=[];
194+
195+
letcurrentNode=this.head;
196+
while(currentNode){
197+
nodes.push(currentNode);
198+
currentNode=currentNode.next;
199+
}
200+
201+
returnnodes;
202+
}
203+
204+
/**
205+
*@param {function} [callback]
206+
*@return {string}
207+
*/
208+
toString(callback){
209+
returnthis.toArray().map(node=>node.toString(callback)).toString();
210+
}
211+
}
Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
exportdefaultclassDoublyLinkedListNode{
2+
constructor(value,next=null,previous=null){
3+
this.value=value;
4+
this.next=next;
5+
this.previous=previous;
6+
}
7+
8+
toString(callback){
9+
returncallback ?callback(this.value) :`${this.value}`;
10+
}
11+
}
Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
#Doubly Linked List
2+
3+
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.
4+
5+
![Doubly Linked List](https://upload.wikimedia.org/wikipedia/commons/5/5e/Doubly-linked-list.svg)
6+
7+
##References
8+
9+
-[Wikipedia](https://en.wikipedia.org/wiki/Doubly_linked_list)
10+
-[YouTube](https://www.youtube.com/watch?v=JdQeNxWCguQ)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp