We will see why we need to use linked list over arrays and implement an object based linked list data structure in javascript.
Why do we need linked list?
Arrays are the most common data structures that are used to store collection of data.
This however has some disadvantages
- Arrays in most programming languages are of fixed length, so it is really not easy to store data beyond its size.
- Also adding and removing element in the middle of the array is expensive because we have to shift all the other elements in the array.
- In javascript, arrays are flexible but they are not efficient. They are just objects with some extra features which make them feel like an array, This makes them really slow to work with.
If we want to random access any element then arrays are the best choice else we can probably use linked list anywhere an array can be used.
What is linked list?
Linked list stores the collection of data, but unlike arrays data are not stored in contagious memory, instead each element in the linked list consists of a node which stores the data and a reference(pointer or link) to the next element.
Have a look at the following figure for better understanding.
There are two ends to the linked list head and tail.
- head: Represent the elements from the beginning of the list.
- tail: Represent the elements from the end of the list.
Advantage
- We can dynamically increase the size of the list and store any amount of data.
- We don’t have to shift elements while adding or removing element from the middle of the list. We can just change the reference to other element.
Disadvantage
- Every time we need to search for any data in the list we will need iterate from the start or (Head) till the desired element.
- We will be storing the reference to the next element, so we need to pay extra attention to make things work properly.
Examples of linked list
There are many examples of linked list in real life like.
- Scavenger hunt game where you have a clue and this clue has a reference to the other clues and thus to the treasure.
- A train where all the wagons are linked to each other. We can easily remove and add new wagons to the train or change their position.
Now I am sure you have got a good idea about what is a linked list so lets start implementing it in javascript.
We will use modern ESNext features and implement the linked list with function as well as with Class.
List of operations performed on linked list
- append(element): Adds a new element in the list.
- removeAt(position): Removes an element from the given position in the list and returns it.
- insert(position, element): Adds an element at the given position in the list.
- toString(): Joins all the elements of the list and returns it as a string.
- toArray(): Converts the linked list to the array and returns it.
- indexOf(element): Returns the position of the given element in the list.
- delete(element): Removes the given element from the list.
- deleteHead(): Removes the first element from the list.
- deleteTail(): Removes the last element from the list.
- isPresent(element): Returns
trueif element is present in the list,falseotherwise. - isEmpty(): Returns
trueif the list is empty,falseotherwise. - size(): Returns the size of the list.
- getHead(): Returns the whole list.
Creating a linked list data structure in javascript
We will use a Node which will be storing the element and the reference to the next element.
function linkedlist() {
//Node
let Node = function(elm) {
this.element = elm;
this.next = null;
}
//To keep track of the size
let length = 0;
//To keep track of the list
let head = null;
//Other methods go here
}
Adding an item in the linked list
We will check if head is empty then assign the current node to it, else add the node as a reference of the next element to the previous node.
//Add new item in the linkedlist
this.append = function(elm) {
let node = new Node(elm),
current;
//If head is empty then
//Add the node at the beginning
if(head === null){
head = node;
}else{
//Else add the node as the
//Next element of the existing list
current = head;
while(current.next){
current = current.next;
}
current.next = node;
}
//Increase the length
length++;
};
Removing an item from the given position in the linked list
If the element is at the beginning of the list then just simply update the head to point to the next element in the list.
Else we will have to iterate in the list and make the previous node of the element at the given position to point to the next node of the element.
//Remove item from any position
this.removeAt = function(pos){
if(pos > -1 && pos < length){
let current = head,
previous, index = 0;
//If removing the first element
//then simply point to the next element
if(pos === 0){
head = current.next;
}else{
//Else find the correct pos
//and then remove the element.
while(index++ < pos){
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
}else{
return null;
}
};
Insert element at the given position in the linked list
Adding the element at the beginning
If we are adding the element at the beginning i.e at the head, then just simply assign the existing list to the new node.
Adding the element in the middle
If we are adding the element in the middle of the list then we will need to iterate till the given position and then make the current node to point to the new node and new node to point at the next node.
Adding the element at the end of the list
If we are adding the element to end of the list i.e at the tail, then we will need to iterate till the last element in the list and then make it point to the new node.
//Add item at any position
this.insert = function(pos, elm){
if(pos >= 0 && pos <= length){
let node = new Node(elm),
current = head,
previous, index = 0;
if(pos === 0){
node.next = current;
head = node;
}else{
while(index++ < pos){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
}else{
return false;
}
};
Getting the index of the element in the list
We will be returning the zero based index for linked list elements just like arrays, If element is not present then we will return -1.
//Get the indexOf item
this.indexOf = function(elm){
let current = head,
index = -1;
//If element found then return its position
while(current){
if(elm === current.element){
return ++index;
}
index++;
current = current.next;
}
//Else return -1
return -1;
};
Check if element is present in the list
We can store any type of data in linked list in javascript but here we are only finding the data for String and Numeric type.
//Find the item in the list
this.isPresent = (elm) => {
return this.indexOf(elm) !== -1;
};
Delete element from the list
//Delete an item from the list
this.delete = (elm) => {
return this.removeAt(this.indexOf(elm));
};
Delete the first element from the list
Removing the element from the head will remove the first element from the linked list.
//Delete first item from the list
this.deleteHead = function(){
let current = head;
if(current === null){
return true;
}
if(current.next){
current = current.next;
head = current;
}else{
head = null;
}
return true;
}
Delete the last element from the list
Removing the element from the tail will remove the last element from the linked list.
//Delete last item from the list
this.deleteTail = function(){
let current = head;
if(current === null){
return true;
}
while(current.next){
if(!current.next.next){
current.next = null;
}else{
current = current.next;
}
}
return true;
}
Return the list as a string
We will concatenate all the elements of the list together and return them as a string.
//Print item of the string
this.toString = function(){
let current = head,
string = '';
while(current){
string += current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
Return the list as an array
We will push all the elements of the list to the array and return it.
//Convert list to array
this.toArray = function(){
let arr = [],
current = head;
while(current){
arr.push(current.element);
current = current.next;
}
return arr;
};
Check if list is empty
//Check if list is empty
this.isEmpty = function(){
return length === 0;
};
Get the size of the list
//Get the size of the list
this.size = function(){
return length;
}
Get the head of the list
//Get the head of the list
this.getHead = function(){
return head;
}
Complete code of the linked list
function linkedlist() {
//Node
let Node = function(elm) {
this.element = elm;
this.next = null;
}
//To keep track of the size
let length = 0;
//To keep track of the list
let head = null;
//Other methods go here
//Add new item in the linkedlist
this.append = function(elm) {
let node = new Node(elm),
current;
if(head === null){
head = node;
}else{
current = head;
while(current.next){
current = current.next;
}
current.next = node;
}
length++;
};
//Remove item from any position
this.removeAt = function(pos){
if(pos > -1 && pos < length){
let current = head,
previous, index = 0;
if(pos === 0){
head = current.next;
}else{
while(index++ < pos){
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
}else{
return null;
}
};
//Add item at any position
this.insert = function(pos, elm){
if(pos >= 0 && pos <= length){
let node = new Node(elm),
current = head,
previous, index = 0;
if(pos === 0){
node.next = current;
head = node;
}else{
while(index++ < pos){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
}else{
return false;
}
};
//Print item of the string
this.toString = function(){
let current = head,
string = '';
while(current){
string += current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
//Convert list to array
this.toArray = function(){
let arr = [],
current = head;
while(current){
arr.push(current.element);
current = current.next;
}
return arr;
};
//Get the indexOf item
this.indexOf = function(elm){
let current = head,
index = -1;
while(current){
if(elm === current.element){
return ++index;
}
index++;
current = current.next;
}
return -1;
};
//Delete an item from the list
this.delete = (elm) => {
return this.removeAt(this.indexOf(elm));
};
//Delete first item from the list
this.deleteHead = function(){
let current = head;
if(current === null){
return true;
}
if(current.next){
current = current.next;
head = current;
}else{
head = null;
}
return true;
}
//Delete last item from the list
this.deleteTail = function(){
let current = head;
if(current === null){
return true;
}
while(current.next){
if(!current.next.next){
current.next = null;
}else{
current = current.next;
}
}
return true;
}
//Find the item in the list
this.isPresent = (elm) => {
return this.indexOf(elm) !== -1;
};
//Check if list is empty
this.isEmpty = function(){
return length === 0;
};
//Get the size of the list
this.size = function(){
return length;
}
//Get the head of the list
this.getHead = function(){
return head;
}
}
Input:
let ll = new linkedlist();
ll.append('prashant');
ll.append('anil');
ll.append('29');
console.log(ll.toArray());
//Remove 'anil' from the list
ll.removeAt(1);
console.log(ll.toArray());
//Remove the first element from the list
ll.deleteHead();
console.log(ll.toArray());
Output:
["prashant", "anil", "29"]
["prashant", "29"]
["29"]
Making the properties and methods private with closure and IIFE (Immediately Invoked Function Expression).
let LinkedList = (function(){
//Return the function
return function linkedlist() {
//Node class
let Node = function(elm) {
this.element = elm;
this.next = null;
}
let length = 0;
let head = null;
//Add new item in the linkedlist
this.append = function(elm) {
let node = new Node(elm),
current;
if(head === null){
head = node;
}else{
current = head;
while(current.next){
current = current.next;
}
current.next = node;
}
length++;
};
//Remove item from any position
this.removeAt = function(pos){
if(pos > -1 && pos < length){
let current = head,
previous, index = 0;
if(pos === 0){
head = current.next;
}else{
while(index++ < pos){
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
}else{
return null;
}
};
//Add item at any position
this.insert = function(pos, elm){
if(pos >= 0 && pos <= length){
let node = new Node(elm),
current = head,
previous, index = 0;
if(pos === 0){
node.next = current;
head = node;
}else{
while(index++ < pos){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
}else{
return false;
}
};
//Print item of the string
this.toString = function(){
let current = head,
string = '';
while(current){
string += current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
//Convert list to array
this.toArray = function(){
let arr = [],
current = head;
while(current){
arr.push(current.element);
current = current.next;
}
return arr;
};
//Get the indexOf item
this.indexOf = function(elm){
let current = head,
index = -1;
while(current){
if(elm === current.element){
return ++index;
}
index++;
current = current.next;
}
return -1;
};
//Delete an item from the list
this.delete = (elm) => {
return this.removeAt(this.indexOf(elm));
};
//Delete first item from the list
this.deleteHead = function(){
let current = head;
if(current === null){
return true;
}
if(current.next){
current = current.next;
head = current;
}else{
head = null;
}
return true;
}
//Delete last item from the list
this.deleteTail = function(){
let current = head;
if(current === null){
return true;
}
while(current.next){
if(!current.next.next){
current.next = null;
}else{
current = current.next;
}
}
return true;
}
//Find the item in the list
this.isPresent = (elm) => {
return this.indexOf(elm) !== -1;
};
//Check if list is empty
this.isEmpty = function(){
return length === 0;
};
//Get the size of the list
this.size = function(){
return length;
}
//Get the head of the list
this.getHead = function(){
return head;
}
}
})();
Input:
let ll = new LinkedList();
ll.append('prashant');
ll.append('anil');
ll.append('29');
console.log(ll.toArray());
//Remove 'anil' from the list
ll.removeAt(1);
console.log(ll.toArray());
//Remove the first element from the list
ll.deleteHead();
console.log(ll.toArray());
Output:
["prashant", "anil", "29"]
["prashant", "29"]
["29"]
Class based implementation of linked list data structure in javascript
We will be using two different classes, one for node and another one for linked list.
//Node
class Node{
constructor(elm, next = null){
this.element = elm;
this.next = next;
}
}
//LinkedList
class LinkedList{
constructor(){
this.length = 0;
this.head = null;
}
//Add new item in the linkedlist
append = function(elm) {
let node = new Node(elm),
current;
if(this.head === null){
this.head = node;
}else{
current = this.head;
while(current.next){
current = current.next;
}
current.next = node;
}
this.length++;
};
//Remove item from any position
removeAt = function(pos){
if(pos > -1 && pos < this.length){
let current = this.head,
previous, index = 0;
if(pos === 0){
this.head = current.next;
}else{
while(index++ < pos){
previous = current;
current = current.next;
}
previous.next = current.next;
}
this.length--;
return current.element;
}else{
return null;
}
};
//Add item at any position
insert = function(pos, elm){
if(pos >= 0 && pos <= this.length){
let node = new Node(elm),
current = this.head,
previous,
index = 0;
if(pos === 0){
node.next = current;
this.head = node;
}else{
while(index++ < pos){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
this.length++;
return true;
}else{
return false;
}
};
//Print item of the string
toString = function(){
let current = this.head,
string = '';
while(current){
string += current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
//Convert list to array
toArray = function(){
let arr = [],
current = this.head;
while(current){
arr.push(current.element);
current = current.next;
}
return arr;
};
//Get the indexOf item
indexOf = function(elm){
let current = this.head,
index = -1;
while(current){
if(elm === current.element){
return ++index;
}
index++;
current = current.next;
}
return -1;
};
//Delete an item from the list
delete = (elm) => {
return this.removeAt(this.indexOf(elm));
};
//Delete first item from the list
deleteHead = function(){
let current = this.head;
if(current === null){
return true;
}
if(current.next){
current = current.next;
this.head = current;
}else{
this.head = null;
}
return true;
}
//Delete last item from the list
deleteTail = function(){
let current = this.head;
if(current === null){
return true;
}
while(current.next){
if(!current.next.next){
current.next = null;
}else{
current = current.next;
}
}
return true;
}
//Find the item in the list
isPresent = (elm) => {
return this.indexOf(elm) !== -1;
};
//Check if list is empty
isEmpty = function(){
return this.length === 0;
};
//Get the size of the list
size = function(){
return this.length;
}
//Get the head of the list
getHead = function(){
return this.head;
}
}
Input:
let ll = new LinkedList();
ll.append('prashant');
ll.append('anil');
ll.append('29');
console.log(ll.toArray());
//Remove 'anil' from the list
ll.removeAt(1);
console.log(ll.toArray());
//Remove the first element from the list
ll.deleteHead();
console.log(ll.toArray());
Output:
["prashant", "anil", "29"]
["prashant", "29"]
["29"]
Making this class private with closure and IIFE
let LinkedList = (function(){
//Node
class Node{
constructor(elm, next = null){
this.element = elm;
this.next = next;
}
}
//Return the linked list
return class linkedlist{
constructor(){
this.length = 0;
this.head = null;
}
//Add new item in the linkedlist
append = function(elm) {
let node = new Node(elm),
current;
if(this.head === null){
this.head = node;
}else{
current = this.head;
while(current.next){
current = current.next;
}
current.next = node;
}
this.length++;
};
//Remove item from any position
removeAt = function(pos){
if(pos > -1 && pos < this.length){
let current = this.head,
previous, index = 0;
if(pos === 0){
this.head = current.next;
}else{
while(index++ < pos){
previous = current;
current = current.next;
}
previous.next = current.next;
}
this.length--;
return current.element;
}else{
return null;
}
};
//Add item at any position
insert = function(pos, elm){
if(pos >= 0 && pos <= this.length){
let node = new Node(elm),
current = this.head,
previous,
index = 0;
if(pos === 0){
node.next = current;
this.head = node;
}else{
while(index++ < pos){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
this.length++;
return true;
}else{
return false;
}
};
//Print item of the string
toString = function(){
let current = this.head,
string = '';
while(current){
string += current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
//Convert list to array
toArray = function(){
let arr = [],
current = this.head;
while(current){
arr.push(current.element);
current = current.next;
}
return arr;
};
//Get the indexOf item
indexOf = function(elm){
let current = this.head,
index = -1;
while(current){
if(elm === current.element){
return ++index;
}
index++;
current = current.next;
}
return -1;
};
//Delete an item from the list
delete = (elm) => {
return this.removeAt(this.indexOf(elm));
};
//Delete first item from the list
deleteHead = function(){
let current = this.head;
if(current === null){
return true;
}
if(current.next){
current = current.next;
this.head = current;
}else{
this.head = null;
}
return true;
}
//Delete last item from the list
deleteTail = function(){
let current = this.head;
if(current === null){
return true;
}
while(current.next){
if(!current.next.next){
current.next = null;
}else{
current = current.next;
}
}
return true;
}
//Find the item in the list
isPresent = (elm) => {
return this.indexOf(elm) !== -1;
};
//Check if list is empty
isEmpty = function(){
return this.length === 0;
};
//Get the size of the list
size = function(){
return this.length;
}
//Get the head of the list
getHead = function(){
return this.head;
}
}
})();
Time Complexity
| # | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Average | Θ(N) | Θ(N) | Θ(1) | Θ(1) |
| Worst | O(N) | O(N) | O(1) | O(1) |
Space Complexity
| # | space |
|---|---|
| Worst | O(N) |