Linked List

Description

Please check my blog post on ugross.dev​

Code

Singly Linked List
Doubly Linked List
SinglyLinkedList.js
1
class Node {
2
/**
3
* @param {number} value of the Node
4
* @param {(Node | null)} next - reference to the next Node
5
*/
6
constructor(value, next = null) {
7
this.value = value;
8
this.next = next;
9
}
10
}
11
​
12
export default class LinkedList {
13
constructor() {
14
this.head = null;
15
this.tail = null;
16
}
17
​
18
/**
19
* Creates new node and inserts at the start of the list
20
*
21
* @param {number} value
22
* @return {LinkedList}
23
*/
24
prepend(value) {
25
// Create new node with the next reference as the head
26
const newNode = new Node(value, this.head);
27
​
28
// Update our head to contain new element
29
this.head = newNode;
30
​
31
// If there is no tail update it too
32
if (!this.tail) {
33
this.tail = newNode;
34
}
35
​
36
return this;
37
}
38
​
39
/**
40
* Creates new node and inserts in the end of the list
41
*
42
* @param {number} value
43
* @return {LinkedList}
44
*/
45
append(value) {
46
const newNode = new Node(value);
47
​
48
if (this.head == null) {
49
this.head = newNode;
50
this.tail = newNode;
51
​
52
return this;
53
}
54
​
55
this.tail.next = newNode;
56
this.tail = newNode;
57
​
58
return this;
59
}
60
​
61
/**
62
* Finds element inside the linked list
63
*
64
* @param {number} value
65
* @return {(Node | null)}
66
*/
67
find(value) {
68
if (!this.head) {
69
return null;
70
}
71
​
72
let currentNode = this.head;
73
while (currentNode) {
74
if (currentNode.value === value) {
75
return currentNode;
76
}
77
currentNode = currentNode.next;
78
}
79
​
80
return null;
81
}
82
​
83
/**
84
* Removes Node from the list by its value
85
*
86
* @param {number} value to remove
87
* @return {Node | null} remove node or null
88
*/
89
delete(value) {
90
if (this.head === null) {
91
return null;
92
}
93
​
94
let deletedNode = null; // Keep deleted Node to return it
95
​
96
if (this.head.value === value) {
97
deletedNode = this.head;
98
// Now make next node to be a new head
99
this.head = this.head.next;
100
}
101
​
102
let currentNode = this.head;
103
if (currentNode !== null && deletedNode === null) {
104
while (currentNode.next !== null) {
105
if (currentNode.next.value === value) {
106
deletedNode = currentNode.next;
107
currentNode.next = currentNode.next.next;
108
} else {
109
currentNode = currentNode.next;
110
}
111
}
112
}
113
​
114
// Check if tail contains Node with the value we are looking for
115
if (this.tail.value === value) {
116
this.tail = currentNode;
117
}
118
​
119
return deletedNode;
120
}
121
​
122
/**
123
* Converts linked list to array
124
*
125
* @return {Node[]}
126
*/
127
toArray() {
128
const nodes = [];
129
​
130
let currentNode = this.head;
131
while (currentNode) {
132
nodes.push(currentNode);
133
currentNode = currentNode.next;
134
}
135
​
136
return nodes;
137
}
138
​
139
/**
140
* Converts linked link to string representation
141
*
142
* @return {string}
143
*/
144
toString() {
145
return this.toArray()
146
.map(node => node.value)
147
.toString();
148
}
149
}
Copied!
DoublyLinkedList.js
1
class Node {
2
/**
3
* @param {number} value of the Node
4
* @param {(Node | null)} next - reference to the next Node
5
* @param {(Node | null)} previous - reference to the previous Node
6
*/
7
constructor(value, next = null, previous = null) {
8
this.value = value;
9
this.next = next;
10
this.previous = previous;
11
}
12
}
13
​
14
export default class DoublyLinkedList {
15
constructor() {
16
this.head = null;
17
this.tail = null;
18
}
19
​
20
/**
21
* Creates new node and inserts at the start of the list
22
*
23
* @param {number} value
24
* @return {DoublyLinkedList}
25
*/
26
prepend(value) {
27
const newNode = new Node(value, this.head);
28
​
29
// if there is head, then update it's previous reference as it won't be head anymore
30
if (this.head) {
31
this.head.previous = newNode;
32
}
33
this.head = newNode;
34
​
35
// If there is no tail create it
36
if (!this.tail) {
37
this.tail = newNode;
38
}
39
​
40
return this;
41
}
42
​
43
/**
44
* @param {*} value
45
* @return {DoublyLinkedList}
46
*/
47
append(value) {
48
const newNode = new Node(value);
49
​
50
// If there is no head create it
51
if (!this.head) {
52
this.head = newNode;
53
this.tail = newNode;
54
​
55
return this;
56
}
57
​
58
// Add new node to the tail
59
this.tail.next = newNode;
60
// Update new Node's previous reference
61
newNode.previous = this.tail;
62
// Set new node to be the tail of the list.
63
this.tail = newNode;
64
​
65
return this;
66
}
67
​
68
/**
69
* Finds Node inside the linked list by its value
70
*
71
* @param {number} value to find
72
* @return {(Node | null)}
73
*/
74
find(value) {
75
if (!this.head) {
76
return null;
77
}
78
​
79
let currentNode = this.head;
80
while (currentNode) {
81
if (currentNode.value === value) {
82
return currentNode;
83
}
84
​
85
currentNode = currentNode.next;
86
}
87
​
88
return null;
89
}
90
​
91
/**
92
* Removes Node from the list
93
*
94
* @param {number} value
95
* @return {(Node | null)}
96
*/
97
delete(value) {
98
if (!this.head) {
99
return null;
100
}
101
​
102
let deletedNode = null; // Save deleted node to return it in the end
103
​
104
let currentNode = this.head;
105
while (currentNode) {
106
if (currentNode.value === value) {
107
deletedNode = currentNode;
108
​
109
if (deletedNode === this.head) {
110
// πŸ”— Node that we need to remove is in the head
111
this.head = deletedNode.next;
112
​
113
if (this.head) {
114
this.head.previous = null; // update new head previous reference
115
}
116
​
117
if (deletedNode === this.tail) {
118
// Our node is in the head and tail, so we can simply remove the tail
119
this.tail = null;
120
}
121
} else if (deletedNode === this.tail) {
122
// πŸ”— Node that we need to delete is in the tail
123
this.tail = deletedNode.previous;
124
this.tail.next = null;
125
} else {
126
// πŸ”— Node that we need to delete is the middle Node
127
const previousNode = deletedNode.previous;
128
const nextNode = deletedNode.next;
129
​
130
previousNode.next = nextNode;
131
nextNode.previous = previousNode;
132
}
133
}
134
​
135
currentNode = currentNode.next;
136
}
137
​
138
return deletedNode;
139
}
140
​
141
/**
142
* Converts linked list to array
143
*
144
* @return {Node[]}
145
*/
146
toArray() {
147
const nodes = [];
148
​
149
let currentNode = this.head;
150
while (currentNode) {
151
nodes.push(currentNode);
152
currentNode = currentNode.next;
153
}
154
​
155
return nodes;
156
}
157
​
158
/**
159
* Converts linked link to string representation
160
*
161
* @return {string}
162
*/
163
toString() {
164
return this.toArray()
165
.map(node => node.value)
166
.toString();
167
}
168
}
Copied!
​
Copy link