Linked Lists with JS

Linked Lists with JS

Data Structures with JavaScript

·

18 min read

A lil note to begin with - I am in learning phase of web development and coding, if you find any discrepancy in the article let me know in the comments. This Blog is result of direct inspiration from Scott Barrett's udemy course -Data Structures and algorithms - Javascript. If you understand better from videos go ahead and check out the course Link at the end of the article

3.jpg

Linked Lists

To start With Linked lists, let's compare Linked lists with a data structure we all coding newbies and JS newbies have heard of! - The Arrays

Let us say we have an array like the following

Array.png

Now, The arrays are in contiguous places in the memory ,linked lists are not. Linked lists are spread all over in the memory. Also, Unlike Arrays linked lists don't have indexes either. Lets try to represent that in a picture

LL1.png

So lets say that gap represents random places in memory rather than contiguous places in memory like arrays. Now the items of lists exists but they aren't linked yet . How are they linked with each other? Ans - Through pointers!( a brief discussion about it in a bit). So to link randomly spread data in the memory ,pointers are used to point to the next element in the linked list.

Linked lists also have two more variables: head - > pointing to the first element in the linked list and tail - > pointing to the last element in the linked list.

Lets try to see pictorial representation of this linked list now .

LL2.png
So as we can see, head is pointing to the first element, tail to the last, and first element is pointing to the 2nd ,2nd element is pointing to the third and so on.... . Notice that last element in linked list is pointing to the null.

Brief Aside about pointers in JavaScript You might think that "Hey iv taken 60 hours JS course on udemy but never heard the term pointers in JavaScript? Nor have any of the twitter threads mentioned the term. How on earth are we even gonna create a data structure like linked list when pointers don't even exist!"

Well Rememeber the lessons on references? When we declare a variable,and declare another variable equal to the first declared variable . You change one the other remains the same. But now when you declare a variable as an Object and declare other variable equal to first variable. You change one and BAM!!! Both variables have been Changed. Well both variables changed because Objects point to a particular location in memory and Primitives create a new location in the memory. You can read more about references here

The point i am trying to make is Objects act as pointers in JavaScript. And thats exactly what we are going to use to create a Linked list!

Linked List's building block

Linked List is made of nodes! What is a node? let me pick up one node from the linked list we saw above.

LL3.png The pic above represents one node of linked list...As you can see what constitutes a node? A node is made of two things a) Value and b) pointer. And this is how we represent a node via code ( spitting bars,bad joke!)

{
    value: 3,
    next: some value
}

if we look further

LL4.png

representing it as code will be

{
  value: 3,
  next: {
    value: 7,
    next: null,
  },
};

In the above code tail is going to point to the next value of 2nd last item .i.e tails points to the the object {value:7,next:null}.It is difficult to put it in representation right now, but do not worry we will see tail being assigned properly in a bit when we will construct a linked list from scratch!

For now let's see how the complete linked list we represented will look like in code:

{
  head: {
    value: 22,
    next: {
      value: 12,
      next: {
        value: 3,
         next: {
          value: 7,
          next: null,
        },
      },
    },
  },
};

Frame 1 (1).png

So thats how the linked list is going to look! with head pointing to first element which in turn is pointing to 2nd element and so on and lastly tail points to the last element which in turn is pointing to null.

Now, lets construct our first Linked list programmatically:

Constructing our Linked list

So we will be creating a new data structure class from the scratch with all the methods of data structure it will look something like:

class LinkedList{
constructor(value){...}
push(value){ create a node, add node to the end of the linked list}
pop(){}
unshift{create a node,add the node to the beginisng of the linked list}
shift{}
...............
}

before we go ahead an dbuild the linked list constructor, we realise that other than linked list contructor few methods like push, unshift and insert, all have one step in common and that is the creation of the new node. if you remember form above, a node consists of both, the value and the pointer.

Group 17.png So we create a new node class separately

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

Now whenever we have to create a new node,rather than writing the whole code again we create a new instance of it. e.g:

const node1 = new Node(22);

This will create a new node with value 22 and pointing to null.

clog1.png

Now lets start building the linked list class. we will first create a linked list with one node. That means head and tail point to the same node. Something like this

Group 19.png

And below is how we put it in code.

class LinkedList {
  constructor(value) {
    const newNode = new Node(value); //create a new node with the value
    this.head = newNode; //point head to the new node
    this.tail = this.head;  //point tail to the new node,we can obviously say this.tail = newNode too
    this.length = 1; //set linked list length to 1
  }
}

let myLinkedList = new LinkedList(22);

So the above code creates a linked list with one element and with head and tails pointing to the one element like this

Group 19i.png

Methods

Lets build some class methods for Linked lists.

a) push

with push we mean adding element to the tail end of the linked list. Big O for push of linked list is O(1)
Steps involved to push an element to the end

1) create a new node

Group 28.png

2) point the the next of tail end element to this new node
3) point tail to the new node.

Group 29.png
The push method has an edge case .i.e if linked list is blank,in that case we will point the head and the tail to the new node.

Lets put all this in code

class LinkedList {
  constructor(value) {
    ............
  }
  push(value) {
    const newNode = new Node(value); //create a new node
    if (!this.head) {//edge case as no head means blank link list
      this.head = newNode, //if a blank linked list was there then ppint head and tail to the new node
      this.tail = newNode;
    } else { //if not a blank linked list then
      this.tail.next = newNode,//point next of the tail element(which is right now pointing to the null) to the new node
      this.tail = newNode; // point tail to the new node
    }
    this.length++; //increase the length of the linked list by1
    return this; //return the linked list
  }
}

b) pop

2nd method we are going to look at is pop. in theory it is opposite of push. We take an element out from the tail end of the linked list and return the removed item. It has two edge case a) The linked list is empty and there is nothing to be removed b) The linked list has only one item and removing that one item will end up resulting in an empty data structure.
Now thinking about removing an element we

1) take the last element out
2)point the tail to the right element
3) Return the removed element

Group 28i.png

But here is the catch
When we had to point tail to the next element it was a one step process but now when we want to point tail on node on the left i.e node with the 7 value, the only thing point to the node with value 7 is the node 3, and the only thing pointing to the node 3 is node 12 and so on..So to move the tail back we have to traverse the whole linked list hence POP is O(n)
Now lets see how to achieve this
We will use two pointers temp and pre to keep track of elements. we will use temp to reach out to the last element to be taken out and returned ultimately and pre will be used to point to the second last element where will point tail to.
for starting lets point temp and pre to the the head

Group 29b.png

And then we will iterate through the list, if temp.next exists will point the temp to next item and pre to the temp which in 1st iteration is already pointed at temp.

Group 30.png

So in this whole iteration process temp will reach the last node and pre will be in the second last node. The whole purpose of pre was to get the node we'd point the tail to after last item is removed. So we remove the node temp is pointed to

Group 32.png and point the tail to the pre node,

Group 33.png and return the temp node. Thus completing the pop method

Now lets see the Pop in code with all the edge cases

class LinkedList {
  constructor(value) {
    ............
  }
  pop() {
    if (!this.head) return undefined;//edge case 1 if linked list is blank return undefined
    let temp = this.head; // point temp to head 
    let pre = this.head; //point pre to head
    while (temp.next) { //start iterating the list, and while temp.next exists
      pre = temp; //point pre to temp
      temp = temp.next; //and point temp to next item
    }
    this.tail = pre; //now when we reach the node where temp.next is null i.e the last node ,point the tail to the pre
    this.tail.next = null; // point the next of the pre,i.e the tail now to null
    this.length--; //decrement the length of the linked list
    if (this.length === 0) { //2nd edge case if list had only one element and removing it results in the blank linked list
      this.head = null; //point head to null
      this.tail = null;//point tail to null
    }
    return temp; //return the removed node
  }
}

c) UNSHIFT and SHIFT (O(1))
unshift (adding element in the begining) and shift (removing element form the begining) is where the linked list outshines the arrays.
Since arrays are indexed data structure, if we add and remove element from the beginning we will have to reindex the whole array thus increasing the time complexity of operation and making shift and unsfit O(n) operation in arrays.
But in linked list since there are no indexes adding and removing element in the beginning is O(1) operation . All we have to do is add /remove the node and point the head to the rigth node.
lets see how it will look in code

Unshift(adding element in the beginning)

Group 33 i.png

Let's see how to add the element to the begining with code, the process will be similar to as explained above, pointing right things to right place is all what it takes.

 unshift(value) {
    const newNode = new Node(value);//create a new node
    if (!this.head) { //edgecase -if linked list is empty
      this.head = newNode; //point head to the new node
      this.tail = newNode;//point tail to the new node
    } else { //else
      newNode.next = this.head;  // point newNode's next to the head
      this.head = newNode; //and pont head to the new node
    }
    this.length++; // increase the length of the linked list by 1
    return this; //return the linked list
  }

above code will result in:

Group 33 (1).png

Shift(removing first element from the beginning)

Group 35.png point the head to the second element, remove the first element and return it.Since we have to return the removed node, we need to assign it to a variable temp

Group 36.png

let's see all this in code

shift() {
    if (!this.head) return undefined; //edge case, if empty linked list return undefined
    let temp = this.head; //point temp to the head
    this.head = this.head.next; //point head to the head.next
    this.length--; //decrement the length
    if (this.length === 0) {//if there was only one item and removing it resulted in empty linked list
      this.tail = null;//point the tail to null
    }
    temp.next = null; // completes the removal of the temp node
    return temp;
  }

d) Get method

Get method is used for getting the value at a particular index. Wait!
Didnt we discuss that linked lists dont have indexes? Right they dont,but we do create a method to iterate through the linked list assigning indexes and returning the value at particular index
Since we have to return an element we will see the temp variable again :)

 get(index) {
    if (index < 0 || index >= this.length) return undefined; //edge case if index value entered is negative or more than length of the linked list
    let temp = this.head; //assign temp to the head
    for (let i = 0; i < index; i++) {
      temp = temp.next; //iterate temp to the required index
    }
    return temp; //return temp
  }

so if we try

let myLinkedList = LinkedList(22);
mylinkedList.push(12)
mylinkedList.push(3)
mylinkedList.push(7)
myLinkedList.get(1) // returns Node{value:12,next:node}

12 will be returned from the above code, the value at index 1

e) SET method

Set method looks for value at a particular index and sets/changes the value. We will use the get method to the get the value at index and then change the value. Let's get straight into the code for the set method

set(index, value) {
    let temp = this.get(index); //get value of element at particular index
    if (temp) { 
      temp.value = value;
      return true;
    }
    return false;
  }

now if we try get and set methods on the linked list we created in the get method above

myLinkedList.get(1) // Node{value:12,next:node}
myLinkedList.set(1, 19)
myLinkedList.get(1) //Node{value:19,next:node}
myLinkedList.set(1, 12) 
myLinkedList.get(1) // Node{value:12,next:node}

e) Insert method

Insert method is when we want to insert a node in between the linked list.

There can be three edge cases:

  • 1) trying to insert at node less than 0 or greater than linked list length, in this case it will return undefined.
  • 2) trying to insert at the end,i.e push method.
  • 3) trying to insert in beginning that is unshift.

Lets try to see this in code.

insert(index, value) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return this.push(value);
    if (index === 0) return this.unshift(value);
}

Now lets say we want to insert a node at index 2 with value 49 like illustrate4d below:

Group 36c.png

steps to achieve this

1) Create a new node with the required value
2) point temp variable to the node previous to the index at which new node is meant to be inserted
Lets see the illustration of these two steps first

Group 39.png

This in the code will be

const newNode = new Node(value);
const temp = this.get(index - 1);

Next we point the newNodes next to the temps next like illustrated below:

Group 40.png

We will write this in code as;

newNode.next = temp.next;

Then we assign the temps next to new node as illustrated below:

Group 40b.png

this in code will be like:

temp.next = newNode;

So after adding the new node we increase the length of the linked list.

Lets see the whole insert method in code.

insert(index, value) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return this.push(value);
    if (index === 0) return this.unshift(value);

    const newNode = new Node(value);
    const temp = this.get(index - 1);
    newNode.next = temp.next;
    temp.next = newNode;
    this.length++;
    return true;
}

Remove Method

lets now talk about removing an element from a particular index.

Steps involved,First comes the three edge cases

  • Remove the element at first position, then we just use the Shift method defined earlier.
  • Removing the element form last index, thats when we use the Pop method from earlier
  • Trying to remove the element from invalid index, then we return the undefined

Then we handle the case ,when we try to remove the element from in-between the linked list, following are the steps involved

  • Point a variable "before" to the node before the node to be removed i.e node at index -1
  • Point a variable temp at the node to be removed
  • point before node's next to the temp's next
  • Point temp's next to the null thus effectively removing it
  • Then we reduce the linked list's length

Let's see all this in illustrations now

Group 52.png

then


Group 41.png

and at last

Group 39 (2).png

Lets write the whole method in code now

remove(index) {
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();
    if (index < 0 || index >= this.length) return undefined;

    const before = this.get(index - 1);
    const temp = before.next; //better time complexity than this.get(index)
    before.next = temp.next;
    temp.next = null;
    this.length--;
    return temp;
}

REVERSING THE LINKED LIST

And now we try to turn the linked list 180 degrees. First things first. SO to reverse the linked list the first thing we will do, is switch the head and tail pointers and we will use a temp variable to do this switching.

Switching method

  • Point temp to the head
  • point head to the tail
  • Point tail to the temp

601.png

And then one by one switch the node pointers in opposite direction

Group 60.png

As we can see in the illustration above when we switch the pointer to previous element we create a gap and connection of the linked list is lost.Now to keep track we need something to point to next and previous element before we start reversing the node pointers.So we will use two more variables previous and next to the temp variable and then we iterate over the whole list and keep on switching the pointer from next to previous

something like

602.png

Now to understand how we reverse the list keeping track of previous and next nodes its very important that you create mental modal or use a pen and paper to realize what is happening. we will use a for loop to iterate over the list and in each iteration will use the following steps.

  • 1) Point next to the temp's next node, which in first iteration already is pointing there, but as you will see after 4th step temp makes the jump and joins next ,hence for first step in iteration we point next to the temp's next.
  • 2) we will point temp to previous, this will create the blank(lost) connection.
  • 3) we will point previous to temp.
  • 4) we will point temp to next ,(this will make temp jump to the next).

Then we return the linked list. This completes the reversal of linked list.

Let's see all this in code.

reverse() {
    let temp = this.head;
    this.head = this.tail;
    this.tail = temp;

    let next = temp.next;
    let prev = null;
    for (let i = 0; i < this.length; i++) {
      next = temp.next;
      temp.next = prev;
      prev = temp;
      temp = next;
    }
    return this;
}

The Complete Look

So we have created a singly linked list from the scratch with all its methods, let's take a look at the complete code.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class LinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = this.head;
    this.length = 1;
  }
  push(value) {
    const newNode = new Node(value);
    if (!this.head) {
      (this.head = newNode), (this.tail = newNode);
    } else {
      (this.tail.next = newNode), (this.tail = newNode);
    }
    this.length++;
    return this;
  }
  pop() {
    if (!this.head) return undefined;
    let temp = this.head;
    let pre = this.head;
    while (temp.next) {
      pre = temp;
      temp = temp.next;
    }
    this.tail = pre;
    this.tail.next = null;
    this.length--;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return temp;
  }

  unshift(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }

  shift() {
    if (!this.head) return undefined;
    let temp = this.head;
    this.head = this.head.next;
    this.length--;
    if (this.length === 0) {
      this.tail = null;
    }
    temp.next = null;
    return temp;
  }
  get(index) {
    if (index < 0 || index >= this.length) return undefined;
    let temp = this.head;
    for (let i = 0; i < index; i++) {
      temp = temp.next;
    }
    return temp;
  }
  set(index, value) {
    let temp = this.get(index);
    if (temp) {
      temp.value = value;
      return true;
    }
    return false;
  }

  insert(index, value) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return this.push(value);
    if (index === 0) return this.unshift(value);

    const newNode = new Node(value);
    const temp = this.get(index - 1);
    newNode.next = temp.next;
    temp.next = newNode;
    this.length++;
    return true;
  }

  remove(index) {
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();
    if (index < 0 || index >= this.length) return undefined;

    const before = this.get(index - 1);
    const temp = before.next; //better time than this.get(index)
    before.next = temp.next;
    temp.next = null;
    this.length--;
    return temp;
  }

  reverse() {
    let temp = this.head;
    this.head = this.tail;
    this.tail = temp;

    let next = temp.next;
    let prev = null;
    for (let i = 0; i < this.length; i++) {
      next = temp.next;
      temp.next = prev;
      prev = temp;
      temp = next;
    }
    return this;
  }
}


Short Comparison Chart between the Big O notation of different operations between linked lists and the Arrays

Big O.png

pic resource - Scott Barrett's udemy course material -Data Structures and algorithms - Javascript

Notice the advantages Linked list has over the arrays when it comes to shift and unshift



note - I am learning Data Structures from https://www.udemy.com/course/data-structures-algorithms-javascript/ . I'd like to thank Scott for making such interactive course! Go ahead an take a look at its very beginner friendly.