Introduction
Continuing the series of our data structures and algorithm.
In this article I will be teaching you how to implement a popular data structure called the linked list.
Hey dude…this is going to be a long one grab that cup of coffee, tea or whatever it is you guys drink these days…maybe a bottle of beer. Looooooooooool.
What is a linked list?
A linked list is a data structure that permits insertion and deletion of items from it and would grow accordingly.
Each element in the linked-list consist of a node that stores the element itself and a reference which is also called a link/pointer to the next element.
Let's look at some examples of a linked list
Let's use a conga line as an example.
The above gif is an example of a conga line.
Each person on the conga line is to an element on the linked-list and their hands are to the reference (pointer/link) on the linked-list.
Each person's hands on the linked-list servers as a link to the next person, this is the same for our linked-list with each node's pointer serving as a link to the next nodes.
It is worth pointing out that there are 4 types of linked-list.
Singly linked list
Doubly linked list
Circular linked list
Doubly circular linked list
In this article, we would be implementing only the singly linked list and in a later article we would be implementing a doubly-linked list.
This is because if you can implement the singly linked list and the doubly linked list, you can easily implement the Circular linked list and the Doubly circular linked list with little explanation.
Before implementing the singly linked list. Let's quickly explain the different types of linked lists.
Singly-linked list
This is the most commonly used linked list. In a singly linked list, each node contains two parts.
One part is the element and the other is a reference (pointer/link) to the next node.
Doubly linked list
In the doubly linked list, each node contains three parts.
One part in the doubly linked list contains a link to the next node and the other part has the link to the previous node.
Circular linked list
In a circular linked list, each node contains two parts just like the singly linked list.
The difference between a circular linked list and a singly linked list is that the last nodes element does not point to null, but instead points to head which is the first element on the list.
Doubly circular linked list
The doubly circular linked is similar to the double linked list because its nodes contain three parts.
One part pointing to the next node and the other pointing to the previous node.
It is also similar to the circular linked but with a slight difference being that the last node's elements points to the head while the head previous points to the tail.
For this tutorial, you can run your codes in your browser console or if you have node.js installed on your local machine, you can run your codes in vscode while using the integrated terminal provided by vscode.
Learn how to install node on windows, Mac, and Linux here.
Now you understand the theory behind the types of the linked list.
Let's implement our linked list data structure.
Since we are using classes we would first create our Node class and our linked list skeleton.
class Node {
constructor(element, next = null) {
this.element = element;
this.next = next;
}
class LinkedList {
constructor(){
this.head = null;
this.length = 0
}
//methods go here
appendFirst(element){}
appendLast(element){}
removeAt(position, element){}
insert(postion, element){}
indexOf(element)
remove(element)
size()
isEmpty()
getHead()
print()
}
Above we have our linked list class with a head property which is where we store the reference to our node.
And also a length property that stores the number of nodes in our linked list.
Let's start implementing our linked list methods.
appendFirst: this method adds a node to the beginning of our linked list.
The insert method takes an element.
Then in this method we instantiate our node and store it in a variable called head, passing in the element which our function received and this.head as the second value of our node class.
Then we set our head variable as the head(this.head) of our linked list.
Then we increment the size.
appendFirst(element){
let head = new Node(element, this.head)
this.head = head
this.length++
}
We put the this.head in our instantiated class, because if there is already a node in the linked list head(this.head), then when adding another node to the list we push the present node to the next, but if the head(this.head) is empty then the node we are adding becomes the only node on the list.
for the sake of this article, I used vscode, and I created a file called index.js(you can name yours with any name of your choice).
Using the vscode integrated terminal would enable us to test and run our codes.
Test
//instantiating our inked list class
let list = new LinkedList()
//using the append first method of the linked list class
list.appendFirst(10)
list.appendFirst(15)
Run in terminal
node index
// head: Node { element: 15, next: Node { element: 10, next: null } },
// length: 2
// }
Before continuing the implementation of our linked list methods, let's implement the print method.
Print: this method enables us to log our linked list element more neatly and conveniently to the console.
In our print method, we set a variable of current to represent the head of our node.
print() {
let current = this.head
while (current) {
console.log(current.element)
current = current.next
}
}
Then we loop through all the nodes using the while loop and in the while loop, we log the current element because we just want the element property.
Then we loop through the nodes by setting the current variable to current.next.
By so doing we simply outputting each element in our linked list.
Test
// add another element to the linked list
list.appendFirst(15)
list.appendFirst(20)
//Run the print method
List.print()
//result logged to the console.
25 20 15 10
appendLast: This adds a node to the end of the linked list,
Things to look out for
When the list is empty and we want to add an element.
When the list is not empty and we want to add an element to it
For this method, the first thing we do is to create our node instance and pass in our element value.
After that, we define a variable current for internal controls
Let node = new Node(element)
Let current;
After this, we want to implement our first case, which is when the list is empty and we want to add an element to the list.
So, we point our head to our node if our head element is null. Since our head element is null this automatically means we are adding our first element to the list.
If(this.head === null){
this.head = node
}else{}
Let's implement the second case when we are adding an element to the list if it's not empty.
So, first in our else block, we create a reference to our head.
Then we iterate through the list until the last element on the list is found.
…}else{
Current = this.head
While(current.next){
Current = current.next
}
When looping the list we know we have reached the last element only when the current.next is null.
So all we have left to do is linking the current element to the node we want to add to the list.
Current.next = node
Then finally we want to increment the length of the list so as to keep track of how many elements we have on the list.
Length++
Below is the complete code for the appendLast method of our linked list.
appendLast(element){
let node = new Node(element)
let current;
if(this.head === null) {
this.head = node;
} else {
current = this.head
while (current.next) {
current = current.next
}
current.next = node
}
this.length++
}
removeAt: this method removes an element from the list at a specified position.
Things to look out for
Removing the first element
Removing any element that's not the first
The first step is creating a method that would take the position of the element to be removed from the list.
removeAt(positon){
}
Next using a conditional we want to check that the position we are passing in is valid.
If the position is valid, we would stem from 0 to the length of the list.
While a value that's is not valid would return a string saying "not a valid position on the linked list"
if(position > -1 && position < this.length){
} else {
Return "not a valid position on the linked list"
}
Let's handle the first case which is removing the first element on the list.
Before doing that we make reference to the first element on the list using the current variable and also declaring other variables such as previous and index which would initially be 0.
All this would be very helpful for internal controls.
Let current = this.head
Index = 0
Previous
Removing the first element on the list, we use a conditional, saying where the position is 0, we want to set the head to the second element on our list.
So to remove the head element we would point the head to the current.next.
If(position === 0){
this.head = current.next
}else{}
Let's handle the second case where we want to remove an element from the end or middle of the list.
In other to achieve this we have to loop the list until we get the position we are looking for.
Then we set our previous to current and our current to current.next.
While(index++ < position){
Previous = current
Current = current.next
}
Then outside our while block, we can remove the current element from the linked list.
All we do is to link the previous.next to the current.next.
Previous.next = current.next
Then we decrement our list.
length--
Note: This method works well for removing both the last and middle elements.
Test
//test if it is a valid position on the list
//result => not a valid position on the list
console.log(list.removeAt(20))
//test for removing the head from the list
Run
//result => 20 15 10 100
// 25 at index 0 was removed
list.removeAt(0)
Run
//test for removing the last element from the list
//the last element on the list is the element with the index of 4 which is 100
//result => 25 20 15 10
list.removeAt(4)
Run
//test for removing the middle element from the list
//we choose element at index 2 which is 15
//result => 25 20 10 100
list.removeAt(2)
Below Is the complete code snippet for our removeAt method.
removeAt(position){
if (position > -1 && position < this.length) {
let current = this.head;
let index = 0;
let previous;
if (position === 0) {
this.head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
} else {
return "the position is not valid"
}
}
Insert: this method inserts a new element to a position on the list.
Things to look out for
Inserting an element to the first position of the list
Inserting an element at the end or middle of the list
The first step to take is creating a method that takes a position and an element to be inserted.
Insert(position, element){
}
Next, we need to do what we did for the removeAt method, since our method is taking values for the position, we want to insert the element, we need to make sure these values are not out of bound.
We do this using a conditional and returning a string saying "no item was added"
If(position > = 0 && position < = length){
}else{
Return "no items added"
}
Now, let's handle the first case where we are adding an element to the first position on the list.
But before going ahead with that let's instantiate our node class as well as create some variables for internal controls.
Const node = new Node(element)
Let current = this.head
Let previous;
Let index = 0
To add an element to the first position of the linked list, we set the node.next to the current.
And simply point the head to the node.
By so doing we have another element on the list.
If(position === 0){
node.current = current
head = node
}else{}
Handling the second case is inserting an element to the end, or the middle of our list.
The first thing we do Is loop the list until we get to the position where we want to insert an element.
We do this in our else block of code.
…} else {
While(index++ < position){
previous = current
current = current.next
}
When we are out of the loop, the previous would be pointing to the element present before the position we want to insert a new element.
While the current variable would be pointing to the element present after the position where we would insert a new element, which is between the previous and current.
Then we need to link the new node and the current element.
node.next = current
After that we want to point the previous.next to node, by so doing we have successfully change the link between the previous and current.
previous.next = node
Then after that, we want to keep track of the length property of our linked list class.
Here we decrement the length and return a string saying "a value has been added to the list".
this.length++
return "a value has been added to the list"
Test
//let's insert an element to the first position on the list //(index of 0)
//current list is 25 20 15 10 100
//after inserting we get 500 25 20 15 10 10
//return "a value has been added to the list"
list.insert(0, 500)
//let's insert to the middle of the list
//current list is 25 20 15 10 100
//after inserting we get 25 20 15 500 10 100
//return "a value has been added to the list"
list.insert(3, 500)
//let's insert to the end of the list
//current list is 25 20 15 10 100
//after inserting we get 25 20 15 10 100 500
//return "a value has been added to the list"
List.insert(5, 500)
//if we try to add to a position that's not on the list it won't be added we
//just return the original list and a string saying "Not a valid position on the list".
console.log(list.insert(10, 500))
Below is the complete code for our insert method.
insert(position, element){
if (position >= 0 && position <= this.length) {
let node = new Node(element)
let current = this.head
let previous
let index = 0
if (position === 0) {
node.next = current
this.head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
this.length++
return "a value has been added to the list"
} else {
return "not a valid position on the list"
}
}
indexOf: this method returns the index of an element on the inked list. If there is no element it returns -1.
First, let's create the method and pass in the element as a value.
indexOf(element) {
Return -1
}
Next, in our method we set a variable current to head that would help us iterate the list, and a variable index to increment our count.
Let current = head
Let index = 0
Then using a while loop we check if the element, we are looking for is the current one by looping through the list.
If the list is empty or we get to the end of the list we where current = current.next is null we would return -1
While(current){
If(element === current.element){
Return index
}
Index++
Current = current.next
}
Return -1
Note: Before testing the indexOf method make sure to clear all the instances where we passed in values for our appendFirst and appendLast methods.
This is just to prevent unnecessary confusion, after doing that you can go ahead and append values last to the empty linked list.
Test
//first let's try to check for some values on the linked list
//result is -1 this is because there are no values on the linked list (we //removed
//themm all)
console.log(list.indexOf(20))
//let's append some values using the appendLast method before checking for their
//index.
list.appendLast(100)
list.appendLast(200)
list.appendLast(300)
list.appendLast(400)
//let's get the index of 100 and 200(you can go ahead and play around with getting
//the index of 300 and 400)
//results should be 0 and 1 which are the index of 100 and 200
console.log(list.indexOf(100))
console.log(list.indexOf(200))
//let's check again for elements that are not on our list
//results would be -1 because our list doesn't contain the element 500
console.log(list.indexOf(500))
You could send me a DM with your solution on Twitter or Instagram.
With the index method implemented, we can implement the remove method of our linked list class.
Below is the complete code for our insert method.
indexOf(element) {
let current = this.head,
index = 0
while (current) {
if (element === current.element) {
return index;
}
index++
current = current.next
}
return -1
}
Remove: this method removes an element from the list.
Remove(element) {
Let index = this.index(element)
Return this.removeAt(index)
}
Taking a closer look you'd see that we are reusing the index and removeAt method.
To easily remove an element from the list.
So, if we pass an element value to our indexOf method and call the index in our removeAt method this removes the element from the list.
Test
//lets try to remove and element that's not on the list
//result we just return the list
list.remove(500)
//lets try to remove the element 200 of index 1
//results should be 100 300 400
list.remove(200)
isEmpty: this returns false if the size of the linked list is bigger than 0 and true if the linked list does not contain any element.
isEmpty() {
return this.length === 0
}
Size: this returns the number of elements that are contained in the linked list.
The length property is controlled internally since the linked list class is built from scratch.
size() {
return this.length;
}
getHead: this returns the heads property of the linked list class.
getHead() {
return this.head
}
There you have it we are done with implementing the linked list.
The linked list data structure is one of the most popular data structure and questions like reversing a linked list usually pop up in tech interviews, so it does help to completely understand the intricacies of how it works and how to implement it.
Guys pls it took quite a lot to make this article of over 3.5k words please share it with your friends on Twitter, Instagram, and Facebook.
This does help get the word out so that every other person can find value in it.
Once again thank you for sticking this long, with me on this one.
You can reach out to me on Twitter or send a Dm on Instagram. Much Love❤️❤️❤️❤️
Top comments (3)
Nice article about Linked Lists. But I have a markdown tip to you.
You can use code blocks with syntax highlight. Only put the tree back-ticks, the name of the language, break a line and insert the code, like this:
Thanks for the article!
Hi bro thanks again for the syntax highlighting tip. Just dropped a new article do check it out.🤓🤓🤓
dev.to/chinedu/javascript-how-to-i...
Thanks so much I'll do that!