Linked List in JavaScript: Double and Sorted Linked Lists

Read Part 1 of this article

This article already assumes you read or is familiar with the intro to linked list article implementation code as it’s based on it.

Double Linked List

To put it simply, in a double-linked list, the elements of the list have 2 pointers, next and previous. It allows us to traverse in both directions since the elements know what element comes next and before. On top of tracking the head element, we also track the tail element as well and because of this extra detail, some operations like “push” are faster.

class DoubleLinkedList extends LinkedList {
#size = 0;
tail = null;

get size() {
return this.#size;
}

createElement(value) {
return {value, next: null, prev: null}
}
}
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.#size += 1;
return this.size;
}
insert(item, index = 0) {
if (index < 0 || index > this.size) return;
if(index === this.size) {
return this.push(item);
}
const element = this.createElement(item); if (index === 0) {
element.next = this.head;
if(this.head) {
this.head.prev = element;
} else {
this.tail = element;
}
this.head = element;
} else {
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.#size += 1;
return this.size;
}
remove(index = 0) {
if (index < 0 || index >= this.size) return null;
let removedElement = this.head; if (index === 0) {
this.head.next.prev = null;
this.head = this.head.next;
} else if(index === this.size - 1) {
this.tail.prev.next = null;
this.tail = this.tail.prev;
}
else {
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.head = null;
this.tail = null;
}
this.#size -= 1;
return removedElement.value;
}

Sorted Linked List

There is a big difference between sorting a linked list and creating a sorted linked list. A sorted linked list is a linked list that is always sorted and the sorting happens when adding new elements to the list. To sort a linked list is pretty much adding a “sort” method that sorts the list in place or returns a new sorted linked list.

class SortedLinkedList extends DoubleLinkedList {
#sortingFunction;

constructor(sortingFunction = null) {
super();
this.#sortingFunction = sortingFunction;

if(typeof sortingFunction !== 'function') {
this.#sortingFunction = (a, b) => {
if(a === b) return 0;

return a > b ? 1 : -1;
}

}
this.push = undefined;
}
}
insert(item) {
if(this.size === 0) {
return super.insert(item);
}
const index = this.#getNextElementIndex(item); return super.insert(item, index);
}
#getNextElementIndex(item) {
let current = this.head;
let i = 0;
for(; i< this.size; i++) {
const res = this.#sortingFunction(item, current.value);
if(!(res >= 0) || !res) return i; current = current.next;
}
return i;
}
const list = new SortedLinkedList();
const list2 = new SortedLinkedList((a, b) => b - a);
// insert same values for both
list.insert(50);
list.insert(10);
list.insert(40);
list.insert(20);
list.insert(30);
list.toString(); // '10, 20, 30, 40, 50'
list2.toString(); // '50, 40, 30, 20, 10'

Next

Read the third part of this article where you will learn about how to create a circular, and reversed 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