An Implementation of Double Linked Lists

Next on the list of data structures to implement is the Double Linked List.

I found this tutorial to code along to.

https://dev.to/miku86/javascript-data-structures-doubly-linked-list-intro-and-setup-275b

I’m able to create new nodes, push those nodes into a Double Linked List, pop, unshift and shift. This is my Node.js class in Javascript.

export class Node{
// Syntax: new Node(value);
constructor(value){
// this refers to the current instance of Node
// Used like: node1.value, node1.prev, node1.next
this.value = value;
// Initialize this.prev and this.next as null
this.prev = null;
this.next = null;
}
}

Since I wanted to practice ES6 import syntax, I had to make some modifications. First, in order to import modules, node looks for the closest parent package.json file. To make things easy, since I couldn’t find the closest package.json file, I just created a new file called package.json and saved it in my working directory/repo. In my package.json, I just have the following code.

{
"type": "module"
}

When I run node, this just tells npm to look for modules. Now I can import modules with ES6 syntax. At the top of my DoublyLinkedList.js file, I have this code.

import { Node } from './Node.js';

And when I run it in the terminal to test it, I have to do it like so.

$ node --experimental-modules DoublyLinkedList.js

Now I’m able to test my DoublyLinkedList. This is my code for DoublyLinkedList.js.

// A Doubly Linked List has a length, a beginning (= head), an end (= tail)
class DoublyLinkedList{
constructor(){
this.length = 0;
this.head = null;
this.tail = null;
}
/**
* Add node to end
* Return newly added node
* @return {Node}
*/
push(value){
// Create a new node
const newNode = new Node(value);
// If the list is empty, the new node should become the head and tail
if(!this.length){
this.head = newNode;
this.tail = newNode;
} else {
// The current tail should point forward (= next) to the new node
this.tail.next = newNode;
// The new node should point back (= prev) to the current tail
newNode.prev = this.tail;
// The new node should become the new tail
this.tail = newNode;
}
// Increment length by 1
this.length++;
// Return new node
return newNode;
}
/**
* Remove node from end
* Return removed node
* @return {Node}
*/
pop(){
// No node in the list so it's empty, therefore return null
// this.length = false if empty, so !this.length returns true
if(!this.length){
return null;
} else {
// Save current tail to return to later
const nodeToRemove = this.tail;
if(this.length === 1){
// After removing the only node, there will be no head and tail
this.head = null;
this.tail = null;
} else {
// Set the node before the current tail as the new tail
this.tail = this.tail.prev;
// Remove the connection from the new tail to the old tail, after reassigning the new tail
this.tail.next = null;
// Remove the connection from the old tail to the next tail
nodeToRemove.prev = null;
}
// Decrement length by 1
this.length--;
// Return old tail
return nodeToRemove;
}
}
/**
* Add node to beginning
* Return newly added Node
* @returns {Node}
*/
unshift(value){
// Create a new node
const newNode = new Node(value);
// If list is empty, set head and tail to new node
// this.length = 0 = false when empty, so !this.length would return true when empty
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
// Set new node's next to current head
newNode.next = this.head;
// Set the current head's prev to new node
this.head.prev = newNode;
// Set list's head to new node
this.head = newNode;
}
// Increment length by 1
this.length++;
// return new node
return newNode;
}
/**
* Remove Node from beginning
* Return removed node
* @return {Node}
*/
shift(){
// If the list is empty, return null. We can't remove data from an empty list
// this.length = 0 = false if empty, so !this.length returns true
if (!this.length) {
return null;
}
// Set head as nodeToRemove
const nodeToRemove = this.head;
// After removing the only element, the list will be empty, so head and tail will be null
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
// The node after nodeToRemove becomes the new head
this.head = nodeToRemove.next;
// Remove both connections from the new head and the old head (nodeToRemove)
this.head.prev = null;
nodeToRemove.next = null;
}
// Decrement length by 1
this.length--;
// Return nodeToRemove
return nodeToRemove;
}
}

These functions work just like you would expect them to work, pop, push, unshift and shift. It definitely helped to recode everything from scratch. I understand what’s happening under the hood a lot better.

Happy quarantining! #Covid-19 #Coronavirus