JavaScript Linked List Data Structure

June 19, 2020

At some point in your career (today?!) you will want to learn data structures. It’s not just to ace the technical interview and land your dream job. Learning data structures will help you understand how software works and improve your problem-solving skills. In this tutorial, you will implement the Linked List data structure in JavaScript.

What is a Linked List?

A linked list is just that: a list that is linked.

🙄

Okay. A linked list is an ordered series of elements that are not necessarily stored in contiguous memory.

☝️

Contiguous memory?

In a compiled language, such as C++, the length of an array needs to be declared at runtime. When the program is executed, memory is allocated for the length of that array continguously, or side-by-side, whether or not anything is yet stored in the array. This makes for very fast and efficient access of elements.

Elements in a linked list are generally referred to as nodes, although they are sometimes called elements or items, too. Each node contains a field that stores a value generally referred to as the link or pointer, which, you guessed it, links or points to the next node in the list. The head of a linked list is its first node and, depending on the implementation, the tail is either the last element or the series of elements that follow the head.

A common analogy for Linked Lists is a train. The engine is the head and each car is a node. The train cars are linked together, but can be reordered by changing how the cars are linked.

Linked List Operations

There are numerous approaches to implementing a Linked List in JavaScript. The fundamental operations are:

adding, or appending, nodes
removing nodes
inserting nodes

Depending on the implementation, the adding and inserting operations may be one and the same. For the sake of simplicity, we’ll keep them separate in this tutorial. In other implementatons, you may find the following operations:

remove head
repleace head
remove tail
insert before
insert after
find

What Problem(s) Do Linked Lists Solve?

In many programming languages (but not JavaScript), arrays are fixed in length, so it’s computationally expensive to add elements that exceed the memory allocation of the array as well as insert or remove elements, which may require reallocation of memory.
Arrays in JavaScript are implemented as objects and thus less efficient than arrays in other languages. Unless you need random access to elements, a linked list may be more efficient than a one-dimensional array.

What Problem(s) Do Linked Lists Create?

Linked Lists use more memory than arrays due to their pointers.
Linked Lists must be traversed sequentially.

Linked List Data Structure in JavaScript

Let’s implement a Linked List in JavaScript. The first question to answer is: what do we know about Linked Lists?

A linked list is a sequential series of nodes. Each node in the list stores at least two fields: the value we want to store in the node and a pointer to the next node. We implement a linked list to solve the problem(s) that arrays create. So we can’t use an array. What can we use?

{}

☝️

What does that look like?

const node = {
    value: “I’m a node!”,
}

But one node does not a list make!

const nodeA = {
    value: “A is for algorithm”
}

const nodeB = {
    value: “B is for boolean”
}

const nodeC = {
    value: “C is for cookie!”
}

Still not a list. How do we link these? With a property:

const nodeA = {
 value: 'A is for algorithm',
 next: nodeB
}
 
const nodeB = {
 value: 'B is for boolean',
 next: nodeC
}
 
const nodeC = {
 value: 'C is for cookie!',
 next: null
}

Why null and not undefined? Because null is an empty or non-existant value, whereas undefined has been declared but not yet assigned a value.

The snippet above presents two problems. Can you spot them?

First, if we attempt to access the next value in either nodeA or nodeB, we will get an error like the following:

Cannot access 'nodeC' before initialization

To resolve this, we can simply invert the declarations:

const nodeC = {
 value: 'C is for cookie!',
 next: null
}
 
const nodeB = {
 value: 'B is for boolean',
 next: nodeC
}
 
const nodeA = {
 value: 'A is for algorithm',
 next: nodeB
}

But that’s not the real issue. We created three objects that link to each other, but we still didn’t create a list.

What’s the solution?

{}

☝️

Let’s create an object, linkedList, to contain our nodes. What is the first node in a Linked List?

const linkedList = {
 head: nodeA
};

What’s next?

Exactly.

const linkedList = {
 head: nodeA,
 next: nodeB
};

Now there’s a list! But what’s the problem with this implementation?

It’s not self-contained. We want our objects nested in our Linked List.

Let’s replace the variables with their values so we can see the structure.

const linkedList = {
 head: 'A is for algorithm',
 next: {
   value: 'B is for boolean',
   next: {
     value: 'C is for cookie!',
     next: null
   }
 }
};

What’s the pattern?

Nested objects.

Our goal now is to write a function, or functions, that return an object like this. How do we get there?

Let’s create a helper class to create new nodes.

class Node {
 constructor(value) {
   this.value = value;
   this.next = null;
 }
}

Let’s verify that it works. If we declare and log a new Node:

const node = new Node(); //Node { element: undefined, next: null }

Next, let’s declare our LinkedList class:

class LinkedList {
 constructor() {
   this.length = 0;
   this.head = null;
 }
}

Again, let’s verify that it works. If we declare and log it:

const linkedList = new LinkedList(); // LinkedList { length: 0, head: null }

Now we need a method for adding elements to our Linked List.

append(value) {
     const node = new Node(value);
 
     if (!this.head) {
       this.head = node;
     } else {
       let current = this.head;
    
       while(current.next) {
         current = current.next;
       }
      
       current.next = node;
     }
    
     return this.length++;
   }

If we append two elements:

linkedList.append("First");
linkedList.append("Second");

The log will return:

LinkedList {
  length: 2,
  head: Node {
    element: 'First',
    next: Node { element: 'Second', next: null }
  }
}

Now let’s implement a remove method:


   remove(value) {
 
   if (!this.head) {
     return null;
   }
 
   if (this.head.value === value) {
       this.head = this.head.next;
       return this.length--;
   }
    
   let current = this.head;
 
   while((current.next !== null) &&
   (current.next.value !== value)) {
     current = current.next;
   }
  
   if (current.next !== null) {
     current.next = current.next.next;
     return this.length--;
   }
 }

What’s happening here?

First we check our head. If it’s not there, we return null.

Then we check if the value stored in the head is the value we want to remove. If so, we reassign the value of the next node to the value of head.

Next, we create a temporary variable, current, and assign it the value in our head.

If the value of current is not equal to null, we iterate over our list using a while loop.

If the next node is not equal to null and the value in the next node is not equal to the value we want to remove, then we reassign the value of current to the value of the next node.

We repeat until our two conditions are not met. So, if the value of current.next is null or the value of current.next.value is the one we want to remove, we exit the while loop.

Lastly, we check if the value of current.next is not equal to null. Why? Just in case. If the value we are looking to remove is not in the list, attempting to assign current.next.next to current.next will throw an error.

TypeError: Cannot read property 'next' of null

The last method we will write, and perhaps most important for Linked Lists, is insert. To implement insert in our Linked List, we need to know two things:

the value to be inserted
the position to insert the value

There are countless approaches to implementing a Linked List, some using insertBefore and insertAfter and even replaceHead methods. For the sake of brevity, we’ll implement an all purpose insert that inserts a value before an existing node making an assumption that we don’t want to change the head of our Linked List and inserting after would be redundant with our append method at the end of the list.

What’s our approach?

find the insertion position
create a new node before the insert position and assign the next property to the next node
assign the next property of the node before the insertion point to the new node
update the length of the list

 insert(pos, value) {
   let current = this.head;
 
   while ((current.next !== null) &&
   (current.next.value != pos)) {
     current = current.next;
   }
 
   if ((!current.next) || (current.next.value !== pos)) {
     return null;
   } else {
     let node = new Node(value);
     node.next = current.next;
     current.next = node;
 
     return this.length++;
   }
 }

Our insert method accepts two arguments, pos and value. We first initialize a temp variable, current, and assign it the value of our head.

The structure is similar to our remove method.

We first need to find pos. We do so with a while loop. If the value of current.next is not null and the value of current.next.value is not equal to pos, then we iterate over our list. With each iteration, we reassign the value of current to the value of current.next. We exit the while loop when one of our conditions return false, meaning we did or did not find pos.

Next we check if there’s a value in current.next or if current.next.value does not equal pos. This is to catch edge cases so we don’t insert our new node in the wrong position. If neither of those return true, then we create a new node and do the ol’ switcheroo by assigning the value of its next to the value of current.next. and then assigning the value of current.next the new node.

Lastly, we increase the length of the list by 1.

Big O & Linked List Data Structures

What is the order of a Linked List?

For access and search, the order of a Linked List is O(n). In our implementation, the order of our insert and remove methods is also O(n) as they both require iteration. But there are (more involved) approaches to Linked Lists where the insert and remove methods are O(1).

Learn JavaScript Linked List Data Structure

In this tutorial, you learned the Linked List data structure in JavaScript. There are several classic and common interview questions using Linked Lists, including:

Reverse a Linked List
Detect a loop in a Linked List (i.e: nodes that link to each other)
Remove duplicates from a Linked List

In the next tutorial, we’ll learn how to implement a Hash Table. Stay tuned!