Data Structures: Linked List

Linked list is a linear data structure, this means that there is a sequence and an order to how they are constructed and traversed. The linked list data structure is a good choice over arrays when you don't need to have random/indexed access to your data, and when you want to have efficient insertion or deletion of elements in the beginning or in the middle of a list. Both insertion and deletion work fast inside linked list because it doesn't require to do reindexing of elements, on the other hand accessing of an element in arrays is fast while for the linked list it takes a linear period of time to get this element.

Table of Contents

Node

Inside the linked list each element is stored in a form of Node. Node is made up of two items: data and a reference/pointer to a node.

The linked list is formed when many such nodes are linked together to form a chain. These are the most popular linked list types:

• Singly linked list
• Doubly linked list
• Circular linked list

Singly linked list

Singly linked list is the simplest implementation of the linked list data structure. Each of the elements will keep data and a reference/pointer to a next node, in the last node next equals null. The entry point into a linked list is called the Head of the list (it's a first node of the list). The last Node in a linked list is called the Tail, this part isn't necessary to include in a linked list, but it allows to avoid list traversing when you need to get the last element inside a list.

First of all, we need to create a Node class for our list:

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;
  }
}

Next, let's create a class called LinkedList that contains the head and the tail with the values null by default.

class LinkedList {
  constructor() {
    this.head = null; // First element of the linked list
    this.tail = null; // Second element of the linked list
  }
}

Now, let's add some methods one by one to our LinkedList class. The main actions for the linked list data structure are:

• Insert
• Search
• Delete

Insertion

Based on requirements linked list insertion methods can be different. For example, if you need to insert values only to the start of the linked list, we simply need to update the head of our list, and tail if it's empty:

/**
 * 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;
}

Let's try it:

const linkedList = new LinkedList();
linkedList.prepend(5);
linkedList.prepend(2);

console.dir(linkedList);

Searching

To implement linked list search we need to know how to do traversing through the linked list. As mentioned above based on access strategy the linked list is a linear data structure, this means that we need to move from one element to another starting from the head to get to the needed Node.

The algorithm of linked list traversing is simple:

1. Start with the head of the list. Access the content of the head node if it is not null.
2. Then go to the next Node(if exists) and access the Node information.
3. Continue until no more Nodes.

Now let's implement our search method using this knowledge:

/**
 * Finds element inside the linked list
 *
 * @param {number} value
 * @return {(Node | null)}
 */
find(value) {
  if (!this.head) {
    return null;
  }

  // 🔂 Use traversing to find our node
  let currentNode = this.head; // Save current position while moving from one Node to another.
  while (currentNode) {
    if (currentNode.value === value) {
      return currentNode;
    }

    currentNode = currentNode.next; // Update current position
  }

  // 😞 Nothing found
  return null;
}

ℹ️ The method above uses iteration to find value but it can be implemented using recursion.

Deletion

Deletion of a Node can be also implemented in different ways: first node removal (using head), last node removal, or removal by value.

Implementation of the first node removal is simple, we just need to update the head to point to the next Node. For others we need to traverse singly linked list to get to the needed point. Let's implement deletion by value, from this it should be also clear how to remove the last node:

/**
 * 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;

  // 🔂 Traverse the list only if both the head and deletedNode variables equal null
  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;
}

Doubly linked list

Doubly linked list is similar to the Singly linked list structure, difference is that Nodes store pointers to the next and previous elements. The first Node has null as a pointer for the previous element, and the last Node has pointer to the next element with the value null.

So, in the doubly linked list we have the following:

• Node
  • next pointer that refers to the next Node.
  • prev pointer that refers to the previous Node.
• head - keeps first node.
• tail - keeps last node.

Our Node in the doubly linked list looks like the following:

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;
  }
}

Doubly linked list operations are similar to the singly linked list, except that you need to keep updated previous pointer of a Node too.

Let's take a look how our prepend method can look like for the doubly linked list:

class DoublyLinkedList {
  constructor() {
    this.head = null; // First element of the linked list
    this.tail = null; // Last element of the linked list
  }

  /**
   * 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;
  }
}

Full code implementation is available at the end of the article.

Time Complexity

**N** is the length of Linked List

Links

• Singly Linked List using TypeScript on GitHub.
• Doubly Linked List using TypeScript on GitHub.
• Linked list vs Array on geeksforgeeks.
• Solve problems using linked list on LeetCode.