Linked List in JavaScript: How to Create Circular and Reversed Lists

Read previous parts of this article

This article already assumes you read or is familiar with the previously linked list articles covering what it is and its single and double implementations.

Circular Linked List

A circular linked list is simply a list in which the tail and head elements point to each other. So what is so special about it?

Circular List Implementation

You should already be familiar with single and double linked list implementations from the previous articles. For the circular linked list implementation the focus would be on the “push”, “insert” and “remove” methods.

class CircularLinkedList {
#size = 0;
head = null;
tail = null;

get size() {
return this.#size;
}
}
toString() {
if(!this.size) return '';
let str = `${this.head.value}`;
let current = this.head.next;
while(current && current !== this.head) {
str += `, ${current.value}`;
current = current.next;
}
return str;
}
push(item) {
const element = this.createElement(item);
if(this.head === null) {
this.head = element;
this.tail = element;
} else {
this.tail.next = element;
element.prev = this.tail;
this.tail = element;
}
this.tail.next = this.head;
this.head.prev = this.tail;
this.#size += 1;
return this.size;
}
insert(item, index = 0) {
if (index < 0 || index > this.size) return;
const element = this.createElement(item); if (index === 0) { <- insert at the start
element.next = this.head;
if(this.head) {
this.head.prev = element;
} else {
this.tail = element;
}
this.head = element;
} else if(index === this.size) { <- insert at the end
this.tail.next = element;
element.prev = this.tail;
this.tail = element;
} else { <- insert anywhere in the middle
let previous = this.head;
for(let i = 0; i < index - 1; i++) {
previous = previous.next;
}
element.next = previous.next;
previous.next.prev = element;
previous.next = element;
element.prev = previous;
}
this.tail.next = this.head;
this.head.prev = this.tail;
this.#size += 1;
return this.size;
}
remove(index = 0) {
if (index < 0 || index >= this.size) return null;
let removedElement = this.head; if (index === 0) { <- remove at the start
this.head.next.prev = null;
this.head = this.head.next;
} else if(index === this.size - 1) { <- remove at the end
this.tail.prev.next = null;
this.tail = this.tail.prev;
} else { <- remove anywhere in the middle
let previous = this.head;
for(let i = 0; i < index - 1; i++) {
previous = previous.next;
}
removedElement = previous.next;
previous.next = removedElement.next;
removedElement.next.prev = previous;
}
if(this.head && this.tail) {
this.tail.next = this.head;
this.head.prev = this.tail;
} else {
this.head = null;
this.tail = null;
}
this.#size -= 1;
return removedElement.value;
}

Reversed Linked List

The reverse a linked list algorithm is a common algorithm problem asked at job interviews and perhaps one of the related linked list algorithms that require some careful thought. What needs to happen is to make the last element on the list the head element and revert the pointer of all elements.

reverse() {
// make the head element
// point to null since
// it will become the last

let previous = this.head;
let current = this.head.next;
previous.next = null;
while(current) {
const next = current.next;
current.next = previous;
previous = current;
current = next;
}
this.head = previous;
}
reverse() {
let current = this.head;
this.head = this.tail;
this.tail = current;
while(current) {
const prev = current.prev;
const next = current.next;
current.prev = next;
current.next = prev;
current = next;
}
}

Conclusion

Linked lists are fun to implement in Javascript and developers should consider it in many applications they often pick an array instead. As a developer, working with data is inevitable and most of the time you are doing more write operations than reading on a list. Whenever that's the case, consider a linked list.

Blog & YouTube Channel for Web, UI & Software Development - beforesemicolon.comyoutube.com/c/BeforeSemicolon

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store