Linked Lists in JavaScript

Photo by David Ballew on Unsplash

The Problem

In arrays we are with ease able to locate the elements we are looking for. However there is a major issue with adding anything to the beginning of an array. We have to push over all the elements of (a possibly very large) array. Doing so would be a very costly procedure.

Linked-Lists to the rescue!

Linked Lists are a data structure that not only store the data associated with each element but also store a pointer to another address in memory where another element exists. We call these elements ‘nodes’.
Linked lists are composed of nodes containing their value, and a pointer to the next value.
Because each node points to a following node, each node can be anywhere in memory, so long as the previous node knows the address.

Representing our linked list in Javascript

Javascript does not have a built in library that allows us to represent a linked list. Instead, we’ll have to make due with what we have. Let’s represent each node in our linked list as an array. The first element in the node is the value, the second element is the next element’s address.

let firstNode = [‘a’, 123]
let secondNode = [‘b’, 132]
let thirdNode = [‘c’, null]
let collection = {0: firstNode, 123: secondNode, 132: thirdNode}
let head = firstNode;

So now we need a function that can take in a node as an argument and return the next node.

let firstNode = [‘cameron’, 123]
let secondNode = [‘sloane’, 132]
let thirdNode = [‘ferris’, null]
let collection = {0: firstNode, 123: secondNode, 132: thirdNode}
let head = collection[0];

function next(node){
    let nextAddress = node[1]
    // retrieve the address of the next element
       return collection[nextAddress]
}
next(firstNode) // [‘sloane’, 123]
next(thirdNode) // undefined

So you can see from the above code that given a node, we first find what the given node points to next, and then find the following node at the stated address.

Now let’s try writing a function called indexAt that looks like the following indexAt(head, index) and then returns the node at that index. We can assume a linked list is zero indexed such that indexAt(head, 0) will return head.

Ok, so essentially, we need to begin at the head and call next a number of times equal to our index argument.

let firstNode = [‘cameron’, 123]
let secondNode = [‘sloane’, 132]
let thirdNode = [‘ferris’, null]
let collection = {0: firstNode, 123: secondNode, 132: thirdNode}
let head = collection[0];
   function next(node){
      let nextAddress = node[1]
// retrieve the address of the next element
return collection[nextAddress]
}
function indexAt(head, index){
let node = head;
for(i = 0; i < index; i++){
node = next(node);
}
return node;
}
indexAt(head, 2)
// [‘ferris’, null]

Summary

Linked lists help us solve some of the time complexity issues encountered when manipulating arrays. Unlike arrays, linked lists do not depend on an element at a given index being at a specific location in memory. Because of this, when elements are added or removed, the location of every other element need not change. Instead with a linked list, we only change what the node in question and adjacent nodes point to, leading to less costly data structure for frequently changing data.