Linked Lists with Javascript

The linked list is a fundamental type of data structure in programming. They consists of nodes containing values and their pointers. Linked lists can be found in a small variety of forms, most generally as singly or doubly.

This article touches on methods of a singly linked list.

What is a node?

Every node contains a value of data, and a pointer to the next node.

// Two nodes, with pointers
var node1 = { value: "ABC", next: node2 }
var node2 = { value: "123", next: node3 }

What are pointers?

Pointers point to the next node in order. The first node of linked list is the “head” node, with each node following pointing to a different node within the list. A pointer with a null value marks the “tail” end of a linked list.

// Two nodes, single pointer (heads and tail)
var node1 = { value: "ABC", next: node2 }
var node2 = { value: "123", next: null }

How do we create the list?

Putting it all together, the linked list is created by initializing an object with a head value pointing to null.

function linkedList( ) {
this.head = null;
}

From here, we must modify the list’s prototypal push method in order to correctly set node pointers to their appropriate values (more nodes).

linkedList.prototype.push = function (val) {
var node = { value: val, next: null }
  if (!this.head) {
this.head = node;
} else {
var current = this.head;

while (current.next) {
current = current.next;
}

current.next = node;
}
}

The block above does a few different things.

First, it creates a node out of a given value. When there is no head, the first node given is set as the list’s head node.

Secondly, when the head does exists, a current value is created to track the beginning and latest values within the list. Within loop (and explicitly before the reaching last item), the new node is set as the last item, or the “tail” of the linked list. **

How does it all work?

In action, the linked list is looks quite ordinary and behaves as similar as a Javascript array would.

var linkedList = new LinkedList(); //push node 
linkedList.push(2); 
linkedList.push(3);
linkedList.push(4);
//check values by traversing LinkedList
linkedList.head; //Object {data: 2, next: Object}
linkedList.head.next; //Object {data: 3, next: Object}
linkedList.head.next.next; //Object {data: 4, next: null}

–Fin.


Written primarily for educational purposes.
Sources: 1, 2, 3