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

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

Passionate Programmer. Independent Thinker. Caring Father. Graduate of Flatiron Bootcamp for Software Development. Currently seeking new opportunities.