Data Structures: Linked List II
Tags: javascript, beginners, programming, algorithms
Published: 2022-04-23 14:26:08

Hey guys am back again with part 2 of my 2-part post on Linked list. In the [first part](https://dev.to/m13ha/data-structures-linked-list-i-312k) 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.


![Linked list meme](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wewhtee2xduy631d2fqa.png)

<p>&nbsp;</p>

### 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.

<p>&nbsp;</p>

#### Node Class


![classsy](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3jfjtwhm0ue66msdkh1y.png)

```Javascript

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.

<p>&nbsp;</p>

#### Linked List Class

```Javascript

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.

<p>&nbsp;</p>

#### Prepend Method


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


```Javascript

 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.


![Break it down](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bi08lhh2u4l2tvqvjb28.gif)

<p>&nbsp;</p>

- 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.

<p>&nbsp;</p>

#### Append Method

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

```Javascript

  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.

<p>&nbsp;</p>

#### PopFirst Method

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

```Javascript

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

```
<p>&nbsp;</p>

- 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.

<p>&nbsp;</p>

#### PopLast Method

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

```Javascript

  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.

<p>&nbsp;</p>

#### Size Method

```Javascript

  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.

<p>&nbsp;</p>

#### 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`.

```Javascript
  
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.

<p>&nbsp;</p>

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

```Javascript
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`
    }
  }
}

```
<p>&nbsp;</p>

You can find and tinker with the code [here.] 
(https://onecompiler.com/javascript/3xzqx248r) Try adding some methods of your own and thanks for reading.


![byeeee](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v4cc9cvoq88y8vmv1q71.gif)