Simple Linked List using JavaScript

As the name implies, a linked list is a list of items (referred to as nodes). Unlike an array, the memory allocation for the nodes of a linked list is not contiguous. In simple linked list (i.e. uni-direction), a node has two attributes.

  • Its value.
  • A reference to the next node in the list.

For the last node in the list, the reference to the next node will be null. To create a linked list using JavaScript, we need two objects. First to create nodes and second to keep track of the list.

The node constructor looks like the following:

/**
 * @description Constructor function to create a node.
 */
 function Node (data) {
   this.data = data;
   this.next = null;
 }

And the linked list constructor, like this:

 /**
  * @description Constructor function to create the linked list.
  */
 function LinkedList () {
   this.head = null;
   this.length = 0;
 }

A node has a data and a next property. The “data” keeps the values we want to assign to a node and, “next” keeps the reference to the next node.

Head is the first node of the linked list. So, for an empty linked list, the head is null and, the length is 0.

All linked lists should allow following actions:

  • Insertion of a node.
  • Deletion of a node at a given position.
  • Traversal of nodes of the list.
  • Search a node for a given data.

Insertion of a node

To insert a node, we need to check the list first, create a head node if there are no nodes present, else add the node at the end. For both the cases, however, we would need to create a node first using the node constructor function.

The steps to create a head node (should the list be empty) is as follows:

  • Create a node A.
  • Assign the data given.
  • By default, the next property of newly created node will be null, as we do not know what’s going to be the next node.

To insert a node a the end of the list, we need to traverse till the end, then do the following:

  • Create a node X.
  • Assign the data given, and next to null.
  • Start from the head and traverse to the end.
  • Assign the next property of the last node to X.

Link: Simple Linked List

Deletion of a node at a given position.

The code to remove a node at a given position might seem complicated but, the logic is simple. There are two extra checks we need to make before going into the actual logic of removing the node.

First is the easy one, check if the linked list is empty or if the position given is not a valid one, i.e. it is either less than 0, or it is larger than the length of the linked list. To keep things simple, I have indexed the linked list from 1 not 0 like arrays.

The second check is for the head node. If the given position is 1, we need to remove the head node. For any other valid position, we need to traverse the list.

Consider the following list:

A -> B -> C -> D -> E -> F -> G -> H -> I -> null

If we need to remove the node “D”, we have to do the following steps:

  • Detach the connection C -> D.
  • Detach the connection D -> E.
  • Attach C -> E.
  • Nullify D.

In this case, we do not need to make any changes with the head. Going back to the case where the given position is 1, i.e. the head node needs to removed from the list, in that case, we would also need to adjust the head.

So the steps will be:

  • Detach the connection A -> B.
  • Make B the head.
  • Nullify A.

Link: Simple Linked List

Traversal & Search

After doing the insert and deletion, traversal and search should be an easy job. We have already done that while inserting a node at the end, and removing the node from a given position. The difference between deletion and search is a simple one. Instead of checking the position, check the data property of the node, return the index of the current node if there is a match.

Link: Simple Linked List

PS: The link is given in this post also contains one additional method to add a node at a given position.