We will see what is circular linked list and why is this data structure is needed and also implement an object-based circular linked list in javascript.
What is circular linked list?
A circular linked list is a variation of linked list in which there is no end to the list. The last element of the list will point to the first element instead of pointing to the null. All the nodes are connected to form a circle.
Both single linked list and doubly linked list can be used to create a circular linked list.
When a circular linked list is implemented with a doubly linked list the first element points to the last and last to the first.
Why do we need circular linked list?
1) Any node can be used as a head or starting point. We can traverse the whole list from any point and stop when we reach again to the first node.
2) Useful for implementation of a queue. Unlike queue implemented with the single linked list, we don’t need to keep track of the first and last element. We can just maintain the pointer of the last node and the first node can always be accessed as the next of the last.
3) It also used widely in applications when we have to go around the list or in the cycle.
- In the operating system it is common when to put multiple running applications in the list and cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application.
- Used by browsers to keep track of the user’s history so that user can navigate.
- It is also used in multiplayer games, All the players are kept in circular linked list and pointer keeps movings as the player chance ends.
4) Circular linked list implemented with the doubly linked list is used to create advanced data structure like Fibonacci Heap.
Disadvantages of circular linked list.
- Implementing a circular linked list is very complex compared to its other variants.
- Reversing it also is a complex task.
- If not traversed properly we can end up in an infinite loop.
- Like single and doubly linked list, it also does not support direct accessing of elements.
Now I am sure you have a good idea about what is circular linked list and why do we need it, so let us start implementing an object-based circular single linked list in javascript.
List of operations performed on circular 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.
- getElementAt(position): Returns the node 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.
- isPresent(element): Returns true if element is present in the list, false otherwise.
- isEmpty(): Returns true if the list is empty, false otherwise.
- size(): Returns the size of the list.
- getHead(): Returns the whole list to iterate in forward direction.
Implementing a circular single linked list in javascript
We will use a Node object which will be storing the element and the reference to the next element.
function circularLinkedList() {
//Node
let Node = function(element) {
this.element = element;
this.next = null;
}
let length = 0;
let head = null;
//Other methods go here
}
Getting element at given position
Returns the node at the given index in the list. We will use this function as helper function to get the nodes at specific index to create circular linked list.
//Get element at specific index
this.getElementAt = function(index) {
if(index >= 0 && index <= length){
let node = head;
for(let i = 0; i < index && node != null; i++){
node = node.next;
}
return node;
}
return undefined;
}
Adding an item in the circular linked list
If the head is empty then assign the current Node to the head else add the Node as the next element.
//Add new node
this.append = function(element){
//Create new node
const node = new Node(element);
let current;
//If head is empty
//Then make new node head
if(head === null){
head = node;
}else{
//Else add the new node as the next node
//And mark the next of new node to the head
current = this.getElementAt(length - 1);
current.next = node;
}
node.next = head;
length++;
}
Inserting element at given position in circular linked list
There are three different cases while inserting an element in the circular single linked list.
Insert at the beginning
If the current element is to be added at the start then just make all the existing elements as the next element of the current element and make the last element to point the new node.
Adding new element in the middle
It is a little more complex, we need to make the element at the current index to point to the current element and current element to point to the next element.
Placing new element at the end
If the node is to be added to the end then make the last element point to the new element and new element point to the first element.
//Insert at given position
this.insert = function(element, index){
if(index >= 0 && index <= length){
const node = new Node(element);
let current = head;
//Insert at head
if(index === 0){
if(head === null){
head = node;
node.next = head;
}else{
node.next = current;
current = this.getElementAt(length);
head = node;
current.next = head;
}
}else{
//Insert at given index (middle or end)
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
length++;
return true;
}
return false;
}
Removing element at given position in circular linked list
There are three different cases while removing an element as well in the circular linked list.
Remove from the head
If the element is to be removed from the start then just make head point to the next element of the current element and make the last element to point the new head.
Removing a node from the middle
It is little more complex, we need to make the previous element of the element at the current index to point to the next element of the current element.
Removing an element from the tail
If the node is to be removed from the tail then we need to make the second last node to point to the head.
//Remove at any position
this.removeAt = function (index) {
if(index >= 0 && index < length){
let current = head;
//Remove from head
if(index === 0){
if(length === 1){
head = undefined;
}else{
const removed = head;
current = this.getElementAt(length - 1);
head = head.next;
current.next = head;
current = removed;
}
}else{
//Remove at given index (middle or end)
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
length--;
return current.element;
}
return undefined;
}
Get the index of the element in the circular linked list
We will be returning the zero-based index for linked list elements just like arrays, If the 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 circular linked list
We can store any type of data in a 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;
};
Get the head of the circular linked list
//Get the head
this.getHead = function(){
return head;
}
Delete an element from the circular linked list
To delete an element from the list we will find the index of the element and remove it.
//Delete an item from the list
this.delete = (elm) => {
return this.removeAt(this.indexOf(elm));
};
Delete head from the circular linked list
To delete head from the list just remove the element at index 0.
//Delete the first item from the list
this.deleteHead = function(){
this.removeAt(0);
}
Get the circular linked list as a string
We will convert the circular linked list to the string by concatenating and it and then return it. As it is a circular list we need to be extra careful that we don't end up in an infinite loop.
//Print item of the string
this.toString = function(){
let current = head,
string = '';
//Keep track of the head
const temp = head.element;
while(current){
//If head is the next element then break
if(temp === current.next.element){
string += current.element + (current.next ? '\n' : '');
break;
}
string += current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
Get the circular linked list as an array
We will convert the circular linked list to an array and return it
//Convert list to array
this.toArray = function(){
let arr = [],
current = head;
//Keep track of head
const temp = head.element
while(current){
//Break if first element detected
if(temp === current.next.element){
arr.push(current.element);
break;
}
arr.push(current.element);
current = current.next;
}
return arr;
};
Check if circular linked list is empty
//Check if list is empty
this.isEmpty = function(){
return length === 0;
};
Get the size of circular linked list
//Get the size of the list
this.size = function(){
return length;
}
Complete code of the circular linked list in javascript.
function circularLinkedList() {
//Node
let Node = function(element) {
this.element = element;
this.next = null;
}
let length = 0;
let head = null;
//Other methods go here
//Get element at specific index
this.getElementAt = function(index) {
if(index >= 0 && index <= length){
let node = head;
for(let i = 0; i < index && node != null; i++){
node = node.next;
}
return node;
}
return undefined;
}
//Add new node
this.append = function(element){
//Create new node
const node = new Node(element);
let current;
//If head is empty
//Then make new node head
if(head === null){
head = node;
}else{
//Else add the new node as the next node
//And mark the next of new node to the head
current = this.getElementAt(length - 1);
current.next = node;
}
node.next = head;
length++;
}
//Insert at given position
this.insert = function(element, index){
if(index >= 0 && index <= length){
const node = new Node(element);
let current = head;
//Insert at head
if(index === 0){
if(head === null){
head = node;
node.next = head;
}else{
node.next = current;
current = this.getElementAt(length);
head = node;
current.next = head;
}
}else{
//Insert at given index (middle or end)
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
length++;
return true;
}
return false;
}
//Remove at any position
this.removeAt = function (index) {
if(index >= 0 && index < length){
let current = head;
//Remove from head
if(index === 0){
if(length === 1){
head = undefined;
}else{
const removed = head;
current = this.getElementAt(length - 1);
head = head.next;
current.next = head;
current = removed;
}
}else{
//Remove at given index (middle or end)
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
length--;
return current.element;
}
return undefined;
}
//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;
};
//Find the item in the list
this.isPresent = (elm) => {
return this.indexOf(elm) !== -1;
};
//Get the head
this.getHead = function(){
return head;
}
//Delete an item from the list
this.delete = (elm) => {
return this.removeAt(this.indexOf(elm));
};
//Delete the first item from the list
this.deleteHead = function(){
this.removeAt(0);
}
//Print item of the string
this.toString = function(){
let current = head,
string = '';
const temp = head.element;
while(current){
if(temp === current.next.element){
string += current.element + (current.next ? '\n' : '');
break;
}
string += current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
//Convert list to array
this.toArray = function(){
let arr = [],
current = head;
const temp = head.element
while(current){
//Break if first element detected
if(temp === current.next.element){
arr.push(current.element);
break;
}
arr.push(current.element);
current = current.next;
}
return arr;
};
//Check if list is empty
this.isEmpty = function(){
return length === 0;
};
//Get the size of the list
this.size = function(){
return length;
}
}
Input: let cLL = new circularLinkedList(); cLL.append(20); cLL.append(30); cLL.append(40); cLL.append(50); console.log(cLL.removeAt(3)); cLL.insert(70, 3); cLL.deleteHead(); cLL.delete(70); console.log(cLL.toArray()); Output: 50 [30, 40]
Making the properties and methods private with closure and IIFE (Immediately Invoked Function Expression).
let circularLinkedList = (function(){
return function circularLinkedList() {
//Node
let Node = function(element) {
this.element = element;
this.next = null;
}
let length = 0;
let head = null;
//Other methods go here
//Get element at specific index
this.getElementAt = function(index) {
if(index >= 0 && index <= length){
let node = head;
for(let i = 0; i < index && node != null; i++){
node = node.next;
}
return node;
}
return undefined;
}
//Add new node
this.append = function(element){
//Create new node
const node = new Node(element);
let current;
//If head is empty
//Then make new node head
if(head === null){
head = node;
}else{
//Else add the new node as the next node
//And mark the next of new node to the head
current = this.getElementAt(length - 1);
current.next = node;
}
node.next = head;
length++;
}
//Insert at given position
this.insert = function(element, index){
if(index >= 0 && index <= length){
const node = new Node(element);
let current = head;
//Insert at head
if(index === 0){
if(head === null){
head = node;
node.next = head;
}else{
node.next = current;
current = this.getElementAt(length);
head = node;
current.next = head;
}
}else{
//Insert at given index (middle or end)
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
length++;
return true;
}
return false;
}
//Remove at any position
this.removeAt = function (index) {
if(index >= 0 && index < length){
let current = head;
//Remove from head
if(index === 0){
if(length === 1){
head = undefined;
}else{
const removed = head;
current = this.getElementAt(length - 1);
head = head.next;
current.next = head;
current = removed;
}
}else{
//Remove at given index (middle or end)
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
length--;
return current.element;
}
return undefined;
}
//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;
};
//Find the item in the list
this.isPresent = (elm) => {
return this.indexOf(elm) !== -1;
};
//Get the head
this.getHead = function(){
return head;
}
//Delete an item from the list
this.delete = (elm) => {
return this.removeAt(this.indexOf(elm));
};
//Delete the first item from the list
this.deleteHead = function(){
this.removeAt(0);
}
//Print item of the string
this.toString = function(){
let current = head,
string = '';
const temp = head.element;
while(current){
if(temp === current.next.element){
string += current.element + (current.next ? '\n' : '');
break;
}
string += current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
//Convert list to array
this.toArray = function(){
let arr = [],
current = head;
const temp = head.element
while(current){
//Break if first element detected
if(temp === current.next.element){
arr.push(current.element);
break;
}
arr.push(current.element);
current = current.next;
}
return arr;
};
//Check if list is empty
this.isEmpty = function(){
return length === 0;
};
//Get the size of the list
this.size = function(){
return length;
}
}
}());
ES6 class based implementation of cicular linked list in javascript.
//Node
class Node{
constructor(elm, next = null, prev=null){
this.element = elm;
this.next = next;
}
}
class circularLinkedList{
constructor(){
this.length = 0;
this.head = null;
}
//Get element at specific index
getElementAt = function(index) {
if(index >= 0 && index <= this.length){
let node = this.head;
for(let i = 0; i < index && node != null; i++){
node = node.next;
}
return node;
}
return undefined;
}
//Add new node
append = function(element){
//Create new node
const node = new Node(element);
let current;
//If head is empty
//Then make new node head
if(this.head === null){
this.head = node;
}else{
//Else add the new node as the next node
//And mark the next of new node to the head
current = this.getElementAt(this.length - 1);
current.next = node;
}
node.next = this.head;
this.length++;
}
//Insert at given position
insert = function(element, index){
if(index >= 0 && index <= this.length){
const node = new Node(element);
let current = this.head;
//Insert at head
if(index === 0){
if(this.head === null){
this.head = node;
node.next = this.head;
}else{
node.next = current;
current = this.getElementAt(this.length);
this.head = node;
current.next = this.head;
}
}else{
//Insert at given index (middle or end)
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
this.length++;
return true;
}
return false;
}
//Remove at any position
removeAt = function (index) {
if(index >= 0 && index < this.length){
let current = this.head;
//Remove from head
if(index === 0){
if(this.length === 1){
this.head = undefined;
}else{
const removed = this.head;
current = this.getElementAt(this.length - 1);
this.head = this.head.next;
current.next = this.head;
current = removed;
}
}else{
//Remove at given index (middle or end)
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.length--;
return current.element;
}
return undefined;
}
//Get the indexOf item
indexOf = function(elm){
let current = this.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;
};
//Find the item in the list
isPresent = (elm) => {
return this.indexOf(elm) !== -1;
};
//Get the head
getHead = function(){
return this.head;
}
//Delete an item from the list
delete = (elm) => {
return this.removeAt(this.indexOf(elm));
};
//Delete the first item from the list
deleteHead = function(){
this.removeAt(0);
}
//Print item of the string
toString = function(){
let current = this.head,
string = '';
//Keep track of the head
const temp = this.head.element;
while(current){
//If head is the next element then break
if(temp === current.next.element){
string += current.element + (current.next ? '\n' : '');
break;
}
string += current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
//Convert list to array
toArray = function(){
let arr = [],
current = this.head;
//Keep track of head
const temp = this.head.element
while(current){
//Break if first element detected
if(temp === current.next.element){
arr.push(current.element);
break;
}
arr.push(current.element);
current = current.next;
}
return arr;
};
//Check if list is empty
isEmpty = function(){
return this.length === 0;
};
//Get the size of the list
size = function(){
return this.length;
}
}
Making this class private with closure and IIFE
let circularLinkedList = (function(){
//Node
class Node{
constructor(elm, next = null, prev=null){
this.element = elm;
this.next = next;
}
}
return class circularLinkedList{
constructor(){
this.length = 0;
this.head = null;
}
//Get element at specific index
getElementAt = function(index) {
if(index >= 0 && index <= this.length){
let node = this.head;
for(let i = 0; i < index && node != null; i++){
node = node.next;
}
return node;
}
return undefined;
}
//Add new node
append = function(element){
//Create new node
const node = new Node(element);
let current;
//If head is empty
//Then make new node head
if(this.head === null){
this.head = node;
}else{
//Else add the new node as the next node
//And mark the next of new node to the head
current = this.getElementAt(this.length - 1);
current.next = node;
}
node.next = this.head;
this.length++;
}
//Insert at given position
insert = function(element, index){
if(index >= 0 && index <= this.length){
const node = new Node(element);
let current = this.head;
//Insert at head
if(index === 0){
if(this.head === null){
this.head = node;
node.next = this.head;
}else{
node.next = current;
current = this.getElementAt(this.length);
this.head = node;
current.next = this.head;
}
}else{
//Insert at given index (middle or end)
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
this.length++;
return true;
}
return false;
}
//Remove at any position
removeAt = function (index) {
if(index >= 0 && index < this.length){
let current = this.head;
//Remove from head
if(index === 0){
if(this.length === 1){
this.head = undefined;
}else{
const removed = this.head;
current = this.getElementAt(this.length - 1);
this.head = this.head.next;
current.next = this.head;
current = removed;
}
}else{
//Remove at given index (middle or end)
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.length--;
return current.element;
}
return undefined;
}
//Get the indexOf item
indexOf = function(elm){
let current = this.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;
};
//Find the item in the list
isPresent = (elm) => {
return this.indexOf(elm) !== -1;
};
//Get the head
getHead = function(){
return this.head;
}
//Delete an item from the list
delete = (elm) => {
return this.removeAt(this.indexOf(elm));
};
//Delete the first item from the list
deleteHead = function(){
this.removeAt(0);
}
//Print item of the string
toString = function(){
let current = this.head,
string = '';
//Keep track of the head
const temp = this.head.element;
while(current){
//If head is the next element then break
if(temp === current.next.element){
string += current.element + (current.next ? '\n' : '');
break;
}
string += current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
//Convert list to array
toArray = function(){
let arr = [],
current = this.head;
//Keep track of head
const temp = this.head.element
while(current){
//Break if first element detected
if(temp === current.next.element){
arr.push(current.element);
break;
}
arr.push(current.element);
current = current.next;
}
return arr;
};
//Check if list is empty
isEmpty = function(){
return this.length === 0;
};
//Get the size of the list
size = function(){
return this.length;
}
}
}());
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) |