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
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
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
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 .
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.
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
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,
},
},
},
},
};
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.
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.
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
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
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
2) point the the next of tail end element to this new node
3) point tail to the new node.
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
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
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.
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
and point the tail to the pre node,
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)
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:
Shift(removing first element from the beginning)
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
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:
- trying to insert at node less than 0 or greater than linked list length, in this case it will return undefined.
- trying to insert at the end,i.e push method.
- 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:
steps to achieve this
Create a new node with the required value
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
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:
We will write this in code as;
newNode.next = temp.next;
Then we assign the temps next to new node as illustrated below:
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
then
and at last
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
And then one by one switch the node pointers in opposite direction
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
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.
- 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.
- we will point temp to previous, this will create the blank(lost) connection.
- we will point previous to temp.
- 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
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.