Linked List?
So what are linked lists? Linked lists are linear data structures with nodes that are linked together by pointers. The fact that linked lists are linear data structures means that data is stored and managed in a linear sequence.
Each box shown in the image above is known as a node. Each node contains data relevant to it and one or more pointers pointing to either the next node in simple linked lists or to both the next and previous node in doubly linked lists. The first node in a linked list is known as the head node and the last node is known as the tail node.
A simple visualization of this concept would be a line of connected safety pins as shown in the following image.
What we will see today are simple linked lists. Simple linked lists are linked lists which contain only the relevant data and one pointer, which points to the next node in the list.
Right into the Code
Linked lists can be implemented using arrays, however it would be much more efficient to implement them using classes. So let's get right into the code.
Node Class
The first thing we want to do is create a class that has a constructor that creates an object with a "data" value and a "next" value whenever an object of the class is instantiated.
class Node{
constructor(data, next = null){
this.data = data;
this.next = next;
}
}
Instantiating an object of the class above...
let node1 = new Node(100);
console.log(node1);
Linked List Class
Ok so the Node class is fully functional, now let's work on the linked list class.
class LinkedList{
constructor() {
this.head = null;
this.size = 0;
}
}
In this LinkedList class we have a constructor which will create a head and size value to keep track of the first node and size of the linked list consecutively. Now we can work on adding the necessary operations for the LinkedList class to be fully functional as a simple linked list.
Operations on the Linked List
We'll start out with the simple operations for our linked list: insert, remove, print and get.
Print List Data
We can start from the function to print the values of the data in the nodes to make it easier to visualize the linked list as we code it.
printListData(){
let curr = this.head;
let arr = [];
while(curr){
arr.push("[" + curr.data + "]");
arr.push('->');
curr = curr.next;
}
arr.push("[null]");
console.log(arr);
}
The function above is more or less optional. A less intensive and less complex alternative would be to get rid of the array and simply console.log the "curr.data" while iterating through the while loop. However this function will help create a visual representation of the linked list making it easier to understand so we will keep it as it is.
Insert First
Now that we got that out of the way let us work on a function that inserts a node at the first position of the linked list.
insertFirst(data){
this.head = new Node(data, this.head);
this.size += 1;
}
How this works is that when a LinkedList class object is instantiated the constructor create an object which has null for its head node, and 0 for its size since there is no node in the list. After creating the LinkedList object we can then use the insertFirst() function to add a node to the front of the node.
let linkedList = new LinkedList();
linkedList.insertFirst(50);
console.log(linkedList);
When we add another node to the linked list it will look something like this..
linkedList.insertFirst(60);
console.log(linkedList);
What is happening here is that "next" value of the node we added later now holds the whole value of the first node we added to the list.
Insert Last
Ok now let us look at what other functions we can apply to this linked list. How about a function that inserts nodes at the end of the list?
insertLast(data){
if(!this.head){
this.insertFirst(data);
} else{
let node = new Node(data);
let curr = this.head;
while(curr.next) {
curr = curr.next;
}
curr.next = node;
}
this.size++;
}
What this function does is it first checks to see if there is a head node. If there is no head node it calls the function we declared before (insertFirst()) and passes in the "data" value to it to create a new node at the head of the linked list. If there is a head node the function creates a new Node object by passing in the "data" value. Once it has done that it creates a new pointer that points to the head of the linked list and traverses through the list until it finds the last node. Once it has located the last node it assigns the new Node object to the "next" value of the last node.
linkedList.insertLast(40);
Insert at Index
Ok now let us try coding a function to add a node at a specific index.
insertInd(data, ind){
if(ind > 0 && ind > this.size){
return undefined;
}
if(ind == 0){
this.inFirst(data);
return;
}
const node = new Node(data);
let curr = this.head;
let prev;
while(ind > 0) {
prev = curr;
curr = curr.next;
ind--;
}
prev.next = node;
node.next = curr;
this.size++;
}
Although it may seem complex at first glance, this function is simple to understand. What it does is it first checks to see if the index input is an "out of bounds" input by checking if the input is greater than 0 and if the input is greater than the size of the linked list. If the index input is out of bounds it returns "undefined".
Next it checks if the index input is 0, in which case it simply uses the former insertFirst() function to add the node to the front of the linked list and returns so that the function ends there. Finally if the input passes both test cases it will loop through the list until it reaches the position of the index input and uses two pointers "prev" and "curr" to point to the node at the index and the one before it. Once it has done that it links the next pointer of the "prev" node to the newly created node and links the next pointer of said node to the "curr" node.
Let's look at what this looks like using the printListData() funciton. To keep things simple let us initialize a new LinkedList object and use the function above to insert nodes at the indices we choose.
let linkedList2 = new LinkedList();
linkedList2.insertInd(10,0);
linkedList2.printListData();
linkedList2.insertInd(30,2);
linkedList2.insertInd(20,0);
linkedList2.printListData();
linkedList2.insertInd(15,1);
linkedList2.printListData();
Great! Since this function is fully functional we are only left with removing a node at an index and getting the data of a node at a specific index.
Remove at Index
Removing at an index is very similar to the previous function of inserting at an index.
removeInd(ind){
if(ind > 0 && ind > this.size){
return undefined;
}
if(ind == 0){
this.head = this.head.next
} else{
let curr = this.head;
let prev;
while(ind > 0){
prev = curr;
curr = curr.next;
ind--;
}
prev.next = curr.next;
}
this.size--;
}
Just like the previous function this function first checks if the input is within bounds. If the input is within bounds it checks if this is the input index is the first index. If it is the first index all it does is it moves the head one step ahead removing the first node from the linked list. If the input isn't the first index then it loops through the loop until it gets to the desired node. Finally it links the next pointer of the "prev" node to the node that is linked to the next pointer of the "curr" node which delinks the node at the specified index.
If we take the previous "linkedList2" obj and apply the removeInd() function here is what it will look like.
linkedList2.printListData();
linkedList2.removeInd(0);
linkedList2.printListData();
linkedList2.removeInd(1);
Get Value
What a ride! The final function will be one that returns the value of the node's data. Here is what it looks like.
getInd(ind){
let curr = this.head;
let ctr = 0;
while(curr){
if(ctr == ind){
return curr.data
}
ctr++;
curr = curr.next;
}
return null;
}
This is a pretty straightforward function. All it does it loops until it reaches a desired index by incrementing the "ctr" variable and moving the "curr" pointer forward in the linked list. If the desired index is reached it returns the value of the node's data at that index. If not, it exits the loop and returns null.
Let's see what this looks like if the function was used on the linked list below.
linkedList3.printListData();
console.log(linkedList2.getInd(0));
console.log(linkedList2.getInd(1));
console.log(linkedList2.getInd(2));
console.log(linkedList2.getInd(3));
Hooray! Now you know how to implement a simple linked list using Javascript classes. Here is the final result:
class Node{
constructor(data, next = null){
this.data = data;
this.next = next;
}
}
class LinkedList{
constructor() {
this.head = null;
this.size = 0;
}
printListData(){
let curr = this.head;
let arr = [];
while(curr){
arr.push("[" + curr.data + "]");
arr.push('->');
curr = curr.next;
}
arr.push("[null]");
console.log(arr);
}
insertFirst(data){
this.head = new Node(data, this.head);
this.size++;
}
insertLast(data){
if(!this.head){
this.head = new Node(data, this.head);
this.size++;
} else{
let node = new Node(data);
let curr = this.head;
while(curr.next) {
curr = curr.next;
}
curr.next = node;
this.size++;
}
}
insertInd(data, ind){
if(ind > 0 && ind > this.size){
return undefined;
}
if(ind == 0){
this.inFirst(data);
return;
}
const node = new Node(data);
let curr = this.head;
let prev;
while(ind > 0) {
prev = curr;
curr = curr.next;
ind--;
}
prev.next = node;
node.next = curr;
this.size++;
}
removeInd(ind){
if(ind > 0 && ind > this.size){
return undefined;
}
if(ind == 0){
this.head = this.head.next
} else{
let curr = this.head;
let prev;
while(ind > 0){
prev = curr;
curr = curr.next;
ind--;
}
prev.next = curr.next;
}
this.size--;
}
getInd(ind){
let curr = this.head;
let ctr = 0;
while(curr){
if(ctr == ind){
return curr.data
}
ctr++;
curr = curr.next;
}
return null;
}
}
