ES6/ES2015 LinkedList Implementation

2016-05-01

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

1
2
3
4
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:

1
2
3
4
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.

1
2
3
4
5
6
7
8
9
10
11
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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