Linked List

Description

Please check my blog post on ugross.devā€‹

Code

Singly Linked List
Doubly Linked List
Singly Linked List
SinglyLinkedList.js
class Node {
/**
* @param {number} value of the Node
* @param {(Node | null)} next - reference to the next Node
*/
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
ā€‹
export default class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
ā€‹
/**
* Creates new node and inserts at the start of the list
*
* @param {number} value
* @return {LinkedList}
*/
prepend(value) {
// Create new node with the next reference as the head
const newNode = new Node(value, this.head);
ā€‹
// Update our head to contain new element
this.head = newNode;
ā€‹
// If there is no tail update it too
if (!this.tail) {
this.tail = newNode;
}
ā€‹
return this;
}
ā€‹
/**
* Creates new node and inserts in the end of the list
*
* @param {number} value
* @return {LinkedList}
*/
append(value) {
const newNode = new Node(value);
ā€‹
if (this.head == null) {
this.head = newNode;
this.tail = newNode;
ā€‹
return this;
}
ā€‹
this.tail.next = newNode;
this.tail = newNode;
ā€‹
return this;
}
ā€‹
/**
* Finds element inside the linked list
*
* @param {number} value
* @return {(Node | null)}
*/
find(value) {
if (!this.head) {
return null;
}
ā€‹
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === value) {
return currentNode;
}
currentNode = currentNode.next;
}
ā€‹
return null;
}
ā€‹
/**
* Removes Node from the list by its value
*
* @param {number} value to remove
* @return {Node | null} remove node or null
*/
delete(value) {
if (this.head === null) {
return null;
}
ā€‹
let deletedNode = null; // Keep deleted Node to return it
ā€‹
if (this.head.value === value) {
deletedNode = this.head;
// Now make next node to be a new head
this.head = this.head.next;
}
ā€‹
let currentNode = this.head;
if (currentNode !== null && deletedNode === null) {
while (currentNode.next !== null) {
if (currentNode.next.value === value) {
deletedNode = currentNode.next;
currentNode.next = currentNode.next.next;
} else {
currentNode = currentNode.next;
}
}
}
ā€‹
// Check if tail contains Node with the value we are looking for
if (this.tail.value === value) {
this.tail = currentNode;
}
ā€‹
return deletedNode;
}
ā€‹
/**
* Converts linked list to array
*
* @return {Node[]}
*/
toArray() {
const nodes = [];
ā€‹
let currentNode = this.head;
while (currentNode) {
nodes.push(currentNode);
currentNode = currentNode.next;
}
ā€‹
return nodes;
}
ā€‹
/**
* Converts linked link to string representation
*
* @return {string}
*/
toString() {
return this.toArray()
.map(node => node.value)
.toString();
}
}
Doubly Linked List
DoublyLinkedList.js
class Node {
/**
* @param {number} value of the Node
* @param {(Node | null)} next - reference to the next Node
* @param {(Node | null)} previous - reference to the previous Node
*/
constructor(value, next = null, previous = null) {
this.value = value;
this.next = next;
this.previous = previous;
}
}
ā€‹
export default class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
ā€‹
/**
* Creates new node and inserts at the start of the list
*
* @param {number} value
* @return {DoublyLinkedList}
*/
prepend(value) {
const newNode = new Node(value, this.head);
ā€‹
// if there is head, then update it's previous reference as it won't be head anymore
if (this.head) {
this.head.previous = newNode;
}
this.head = newNode;
ā€‹
// If there is no tail create it
if (!this.tail) {
this.tail = newNode;
}
ā€‹
return this;
}
ā€‹
/**
* @param {*} value
* @return {DoublyLinkedList}
*/
append(value) {
const newNode = new Node(value);
ā€‹
// If there is no head create it
if (!this.head) {
this.head = newNode;
this.tail = newNode;
ā€‹
return this;
}
ā€‹
// Add new node to the tail
this.tail.next = newNode;
// Update new Node's previous reference
newNode.previous = this.tail;
// Set new node to be the tail of the list.
this.tail = newNode;
ā€‹
return this;
}
ā€‹
/**
* Finds Node inside the linked list by its value
*
* @param {number} value to find
* @return {(Node | null)}
*/
find(value) {
if (!this.head) {
return null;
}
ā€‹
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === value) {
return currentNode;
}
ā€‹
currentNode = currentNode.next;
}
ā€‹
return null;
}
ā€‹
/**
* Removes Node from the list
*
* @param {number} value
* @return {(Node | null)}
*/
delete(value) {
if (!this.head) {
return null;
}
ā€‹
let deletedNode = null; // Save deleted node to return it in the end
ā€‹
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === value) {
deletedNode = currentNode;
ā€‹
if (deletedNode === this.head) {
// šŸ”— Node that we need to remove is in the head
this.head = deletedNode.next;
ā€‹
if (this.head) {
this.head.previous = null; // update new head previous reference
}
ā€‹
if (deletedNode === this.tail) {
// Our node is in the head and tail, so we can simply remove the tail
this.tail = null;
}
} else if (deletedNode === this.tail) {
// šŸ”— Node that we need to delete is in the tail
this.tail = deletedNode.previous;
this.tail.next = null;
} else {
// šŸ”— Node that we need to delete is the middle Node
const previousNode = deletedNode.previous;
const nextNode = deletedNode.next;
ā€‹
previousNode.next = nextNode;
nextNode.previous = previousNode;
}
}
ā€‹
currentNode = currentNode.next;
}
ā€‹
return deletedNode;
}
ā€‹
/**
* Converts linked list to array
*
* @return {Node[]}
*/
toArray() {
const nodes = [];
ā€‹
let currentNode = this.head;
while (currentNode) {
nodes.push(currentNode);
currentNode = currentNode.next;
}
ā€‹
return nodes;
}
ā€‹
/**
* Converts linked link to string representation
*
* @return {string}
*/
toString() {
return this.toArray()
.map(node => node.value)
.toString();
}
}

ā€‹