Data Structures: Linked List II

Hey guys am back again with part 2 of my 2-part post on Linked list. In the first part we focused on explanation, visualization, and use cases, while in this part we shall look at implementation in Javascript. So let's get into it.

 

Methods Of A Linked List

There are a lot of methods that we can implement into a Linked list, but we're going to be focusing on some of the most common methods:

• Prepend: Add a new node to the head of the list.
• Append: Add a new node to the tail of the list.
• PopFirst: Removes and returns the head/first node of the list or null if the list is empty.
• PopLast: Removes and returns the tail/last node of the list or null if the list is empty.
• Size: Returns the number of nodes in the list.
• Contains: Search through list and returns true or false if the value is present in the list.

In this tutorial we will be building the Doubly-linked list because it is a bit more complex than the Singly-linked list but also not too far from the Circular-linked list.

 

Node Class

class Node {
  constructor(data, next, prev) {
    (this.data = data), (this.next = next || null);
    this.prev = prev || null;
  }
}

Since we're building a Doubly-linked list, our nodes need to have 3 values, the data, the next pointer, and the prev pointer.

 

Linked List Class

class Linkedlist {
  constructor() {
    (this.head = this.tail = null), (this.size = 0);
  }
}

Our Linked list will also have 3 parameters, the head, tail, and size. The head and tail parameters will be set to null initially, and size will be set to 0. The head parameter will keep track of the first node in the list, and the tail will keep track of the last, while size will keep track of the number of nodes in the list.

 

Prepend Method

The prepend method is used to add a new node to the head of the list.

 prepend(data) {
    if (!this.head) {
      this.head = new Node(data);
      this.tail = this.head;
    } else {
      let oldhead = this.head;
      this.head = new Node(data);
      this.head.next = oldhead;
      oldhead.prev = this.head;
    }
    this.size++;
  }

It will take in a value which will be set as the value of the new node. Let's break this function down step by step.

 

• First, we check if the list is empty.
• If it is, we create a node, pass it the data, and make sure the head and tail of the list are pointing to this new node.
• If the list isn't empty, then we take the current head of the list and put it in a variable oldhead; then we change the head pointer of the list to our new node. We set the next pointer of our new node to oldhead and the prev pointer of oldhead to our new head.
• Then lastly, we increase the size count by 1.

 

Append Method

The append method adds a new node to the end of the list.

  append(data) {
    if (!this.tail) {
      this.tail = new Node(data);
      this.head = this.tail;
    } else {
      let oldTail = this.tail;
      this.tail = new Node(data);
      oldTail.next = this.tail;
      this.tail.prev = oldTail;
    }
    this.size++;
  }

The append method follows a similar process to the prepend method.

• First, we check if the list is empty.
• If it is, we create a node, pass it the data, and make sure the head and tail of the list are pointing to this node.
• If the list isn't empty, then we take the current tail of the list and put it in a variable oldtail; then we change the tail pointer of the list to our new node. We set the prev pointer of our new tail to the oldtail and the next pointer of oldtail to our new tail.
• Then lastly, we increase the size count by 1.

 

PopFirst Method

The popFirst method removes and returns the data of the head/first node in the list.

  popFirst() {
    if (this.head) {
      let oldHead = this.head;
      if(this.size === 1){
        this.head = this.tail = null;
      }else {
        this.head = oldHead.next;
        this.head.prev = null;
      }
      this.size--;
      return oldHead.data;
    } else {
      return null;
    }
  }

 

• First we check if there is a node in the list; if there isn't, then we just return null.
• If there is a node, then we check if its the only node in the list by checking if size is equal to 1.
• If it is the only node, then we set both the head and tail of the list to null and return the data of the node.
• If it is not the only node in the list, then we store the current head of the list in a variable oldhead, set the new head of the list to the oldhead.next and set the new head.prev to null and return the data of the oldhead.
• Lastly, we decrease the size count by 1.

 

PopLast Method

The popLast method removes and returns the data of the tail/last node in the list.

  popLast() {
    if (this.tail) {
      let oldtail = this.tail;
      if(this.size === 1){
        this.head = this.tail = null;
      }else {
        this.tail = oldtail.prev;
        this.tail.next = null;
      }
      this.size--;
      return oldtail.data;
    } else {
      return null;
    }
  }

The process of the popLast method is similar to the popFirst method.

• First we check if there is a node in the list; if there isn't, then we just return null.
• If there is a node, then we check if its the only node in the list by checking if size is equal to 1.
• If it is the only node, then we set both the tail and head of the list to null and return the data of the node.
• If it is not the only node in the list, then we store the current tail of the list in a variable oldtail, set the new tail of the list to the oldtail.prev and set the new tail.next to null and return the data of the oldtail.
• Lastly, we decrease the size count by 1.

 

Size Method

  size() {
    return this.size;
  }

The size method is very simple. It just returns the size property of the list which shows how many nodes are in the list.

 

Contains Method

The contains method is a form of search method that checks if a value is present in a list and returns true or false.

contains(data) {
    if (this.size > 0) {
      let currentNode = this.head;
      while (currentNode) {
        if (currentNode.data === data) {
          return true;
        }
        currentNode = currentNode.next;
      }
      return false;
    }else {
      return `list is empty`
    }
  }

• First thing we want to do in this function is check if the list is empty, if it is we return a string to let the user know.
• If the list is not empty, then we want to loop through the list starting from the head and check each node's data property to see if it matches our function argument.
• If we find a match, we return true.
• If we don't find a match, we return false.

 

Our complete Linked list class should look like this after adding all the above methods.

class Linkedlist {
  constructor() {
    (this.head = this.tail = null), (this.size = 0);
  }

  prepend(data) {
    if (!this.head) {
      this.head = new Node(data);
      this.tail = this.head;
    } else {
      let oldhead = this.head;
      this.head = new Node(data);
      this.head.next = oldhead;
      oldhead.prev = this.head;
    }
    this.size++;
  }


  append(data) {
    if (!this.tail) {
      this.tail = new Node(data);
      this.head = this.tail;
    } else {
      let oldTail = this.tail;
      this.tail = new Node(data);
      oldTail.next = this.tail;
      this.tail.prev = oldTail;
    }
    this.size++;
  }

  popFirst() {
    if (this.head) {
      let oldHead = this.head;
      if(this.size === 1){
        this.head = this.tail = null;
      }else {
        this.head = oldHead.next;
        this.head.prev = null;
      }
      this.size--;
      return oldHead.data;
    } else {
      return null;
    }
  }

  popLast() {
    if (this.tail) {
      let oldtail = this.tail;
      if(this.size === 1){
        this.head = this.tail = null;
      }else {
        this.tail = oldtail.prev;
        this.tail.next = null;
      }
      this.size--;
      return oldtail.data;
    } else {
      return null;
    }
  }

  size() {
    return this.size;
  }

  contains(data) {
    if (this.size > 0) {
      let currentNode = this.head;
      while (currentNode) {
        if (currentNode.data === data) {
          return true;
        }
        currentNode = currentNode.next;
      }
      return false;
    }else {
      return `list is empty`
    }
  }
}

 

You can find and tinker with the code here. Try adding some methods of your own and thanks for reading.

Comments

[Irwin]

Great post! Easy to understand