ES6/ES2015 LinkedList Implementation

#JavaScript #Algorithm #ES2015 #ES6 #Data Structure

JavaScript ES6/ES2015 Implementation of a LinkedList.

Definition

A LinkedList is a list of Node. A Node is the most basic building block for many Data Structures.

A Node does two things:

Contain a Value
Connect itself to other Nodes via an object reference pointer

In a LinkedList, all Nodes can only have one Child Node.

Implementation

Nodes

For our Node, we will use a simple JavaScript Object

Example

var node1 = {
    data: 5,
    next null
};

This node does not point to anything at the moment. Let’s create a second Node and have it point to the first Node:

var node2 = {
    data: 7,
    next: node1
};

LinkedList

A LinkedList is a class that encapsulated the Nodes. It will contain

a head property that is a pointer to the first Node.
a tail property that is a pointer to the last Node.
a count property that keeps track of node count.
Add and Remove methods to manipulate the nodes in the list.

1) Base

For the LinkedList, we will use a class and store the head Node and Tail Node as class property as well as a count variable that stores the number of Nodes.

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }
  
  get length() {
    return this.count;
  }
}

2) Add functions

We will now create two add functions. A addFirst to add at the start of the list and addLast to add at the end of the list.

Here is the addLast method:

addLast(data) {
  // Create a new Node
  const node = {
    data: data,
    next: null
  }
  
  if(this.count === 0) {
    // If this is the first Node, assign it to head
    this.head = node;
  } else {
    // If not the first node, link it to the last node
    this.tail.next = node;
  }
  
  this.tail = node;
  
  this.count++;
}

Here is the addFirst method:

addFirst(data) {
  // Create a new Node
  const node = {
    data: data,
    next: null
  }
  
  // Save the first Node
  const temp = this.head;
  
  // Point head to the new Node
  this.head = node;
  
  // Add the rest of node behind the new first Node
  this.head.next = temp;
  
  this.count++;
  
  if(this.count === 1) {
    // If first node, 
    // point tail to it as well
    this.tail = this.head;
  }
}

3) Remove functions

Likewise, we will create a removeFirst and removeLast functions.

Here is the removeFirst method:

removeFirst(data) {
  if(this.count > 0) {
    // The head should point to the second element
    this.head = this.head.next;
    
    this.count--;
    
    if(this.count === 0) {
      // If list empty, set tail to null
      this.tail = null;  
    } 
  }
}

Here is the removeLast method:

removeLast(data) {
  if(this.count > 0) {
    if(this.count === 1) {
      this.head = null;
      this.tail = null;
    } else {
      // Find the Node right before the last Node
      let current = this.head;
      while(current.next !== this.tail) {
        current = current.next;
      }
      
      current.next = null;
      this.tail = current;
    }
    this.count--;
  }
}

And that’s it, our LinkedList is ready.

See it in action here.

Here is the full code