Forward Linked List in JavaScript

Introduction

A Forward Linked List (FLL in short) is a data structure that connects each element with a pointer. Although there are many linked lists out there, it is good to start with FLL because it is relatively easier to understand. It is called Forward Linked List because we can only iterate at the top and cannot go backward from the end. We will learn how to implement Forward Linked List in JavaScript as well as write some methods to manipulate it.
View Source Code

Structure of A Forward Linked List

FLL is a list of elements in which each element has a value and a pointer to the next element. The graph below shows the structure of FLL.

The picture above is a FLL with four elements. As you can see in the picture, there are three things consisting of a FLL: Node, Head and null. Let's have a deeper look at each.

Node

A black box above represents an element also known as a Node. Inside a node, two types of information are stored: a value and a pointer. A pointer in a node points to another node and not a value. For example, a leftmost node has a value of 6 and a pointer to the next node with a value of 8. A pointer is the only clue to identify the next node.

Head

A head always points to the first node in a FLL. A head is really important because all the operations of FLL start with a node with a Head. In other words, it points to a node that is not pointed by any nodes.

null

The pointer of the last node does not point to a node but instead points to null. This indicates that a FLL ends there.

Null and Undefined in JavaScript
A variable that is null is assigned by someone intentionally to represent an absence of a value. There is a similar data type existing in JS called "undefined". It means that a variable is not assigned. It is crucial to understand the difference between these two.

The overall structure of a FLL

In the graph above, a FLL starts with a node that is pointed by a Head which is a node with a value of 6. The pointer of this node points to a node with a value of 8. The pointer of this node points to a node with a value of 7. The pointer of this node points to a node with a value of 10. And then, The pointer of this node points to null indicating that the list ends.

Operations of A Forward Linked List

There are in general three operations for a FLL: push method, pop method and insert method (it might not be popular to implement an insert method but it is fun to do it so we are doing it!). The push method adds a node at the beginning of a FLL. The pop method removes a node at the beginning of FLL meaning that this method removes a node to which the head indicates, and the insert method put a node into an index specified by a user. Let's have a look at each method in detail.

1. Push method

The push method adds a node at the beginning of a FLL. This graph shows the state of a FLL before and after executing this method. A node added to a FLL holds a value of 7.

As you can see in the graph, a node added to a FLL is at the beginning and the Head points to the node. A node previously at that position is no longer placed there.

2. Pop method

The pop method removes a node at the beginning. The graph down below describes the state of a FLL before and after executing the method.

A node removed from a FLL is always located at the beginning. The important thing to note is that as this node is removed, the head now points to a node that was pointed by the removed node before executing the method.

3. Insert method

The insert method put a node into a certain location of a FLL specified by a user. A graph illustrates the state of a FLL before and after executing an insert method.

In the graph above, a node with a value of 6 is inserted into the FLL at the index of 1. As you can see, the first node now points to the inserted node and the inserted node points to a node with a value of 10.

Implementation with JavaScript

There are multiple ways of creating a FLL in JavaScript but in this article, we are going to create two classes: Node class and ForwardLinkedList(FLL) class. The node class possesses a value and a pointer and the FLL class has a head.

// This is a Node class. It has a value and a pointer.
class Node  {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

// This is a ForwardLinkedList class. It has a head.
// This class also has push method, pop method and insert method.
class ForwardLinkedList {
  constructor() {
    this.head = null;
  }

  // This is a method used only in this class.
  _isNotEmpty = function() {
    if (this.head === null) {
      return true;
    }
    return false;
  }

  push = function(node) {
    // If a node is the first node in a FLL, just set head
    if (this.head === null) {
      this.head = node;
    } else {
      node.next = this.head;
      this.head = node;
    }
  }

  pop = function() {
    // return null if a FLL is empty.
    if (this.head === null) return null;
    const target = this.head;
    this.head = this.head.next;
    target.next = null;
    return target;
  }

  insert = function(node, index) {
    let i = 0;
    // pop a node if a FLL is not empty and index is equal to 0.
    if(this._isNotEmpty() && index === 0) {
      this.pop(node);
    }
    let nextValue = this.head;
    while (true) {
      if (i === index - 1) {
        node.next = nextValue.next;
        nextValue.next = node;
        break;
      }
      nextValue = nextValue.next;
      i++;
    }
  } 
}

1. Push method explained

A push method takes a node(node A) as a parameter. We need to consider two different situations. If node A is the first node in the FLL, set the head to node A. If there is already a node(s), first, set node A pointer to a node pointed by the head. And then, update the head to node A.

2. Pop method explained

Before trying to take out a node from the FLL, it is necessary to check if the FLL has a node(s). If it is empty, just return null. Otherwise, we have to remove a node pointed by a head (node A) and end the relationship between node A and the FLL completely. To achieve this, we set a target node A. Then, move the head to a node that node A points to. All we have to do is to make node A pointer null so that it does not point to the FLL.

3. Insert method explained

An insert method takes two parameters: node (node A) and index. The first if statement checks if the FLL is not empty and the index is equal to zero. If it is the case, we simply pass the rest of the work to the pop method. The nextValue keeps track of a current node starting with a node pointed by the head. In the while loop, what it does is iterate through the FLL until it meets the condition which is "i === index - 1". It is index - 1 because the pointer of the node stored in nextValue has to point to node A. After making this change, let node A pointer point to a node that nextValue points to.

Characteristics of a Forward Linked List

1. Dynamic Data Structure
   A Dynamic Data Structure refers to a data structure that can change the number of elements held inside. Most of the data structures used in JavaScript take this type such as array and JavaScript objects. Unlike a dynamic data, structure, there is a static data structure. Its size is fixed. you are not able to change the number of elements inside once you initialize it.

2. Order is maintained.
   As long as you do not use an insert method, the order of a FLL is always maintained.

3. No random access
   Unlike a hashmap which enables you to access any element inside without iterating elements, with a FLL you need to iterate through nodes until you find the node that you are looking for. Therefore, a FLL may not be a suitable choice if you want to use it for searching.

Time Complexity and Space Complexity

If you are not familiar with these concepts, you can skip this section.

* n is the length of a FLL

Conclusion

Congratulations! Now you know about what a Forward Linked List is and how to implement it in JavaScript. But I highly recommend you try to implement a FLL by yourself to understand deeper so that you are less likely to forget what you have learned.