Talking about Javascript and TypeScript.
Although you can do anything with arrays, sometimes there is a need for more complex data structures, and one of them is the linked list.
What is a linked list?
A linked list is a fundamental data structure in computer science, comprising a series of nodes where each node contains data and a reference, or link, to the next node.
This structure supports dynamic memory allocation and enables efficient insertion and deletion operations compared to arrays.
Unlike arrays, linked lists store nodes non-contiguously in memory, allowing for efficient insertion or removal of elements from any position in the list.
What is a doubly linked list?
A doubly linked list is a data structure consisting of nodes where each node contains data and two pointers: one pointing to the next node and one to the previous node.
This allows traversal in both forward and backward directions, making operations like insertion and deletion more efficient.
Here is a TypeScript doubly linked class, with some extra methods.
export class Node {
data : any;
next : Node | null;
prev : Node | null;
constructor(data : any) {
this.data = data;
this.next = null;
this.prev = null;
}
}
export class LinkedList {
head : Node | null;
tail : Node | null;
size : number;
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// add a data to the end of the list (TAIL)
append(data : any) : void {
const newNode : Node = new Node(data);
if (this.tail) {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
} else {
this.head = newNode;
this.tail = newNode;
}
this.size ++;
}
// add data to the start of the list (HEAD)
prepend(data : any) : void {
const newNode : Node = new Node(data);
if (this.head) {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
} else {
this.head = newNode;
this.tail = newNode;
}
this.size ++;
}
// insert data at a specific position
insertAt(data : any, position : number) : void {
if (position < 0 || position > this.size - 1) {
throw Error('Position ' + position + ' is not in the list');
}
if (position == 0) {
this.prepend(data);
return;
}
if (position == this.size) {
this.append(data);
return;
}
let currentNode : Node = this.head as Node;
let index : number = 0;
while (index < position) {
currentNode = currentNode.next as Node;
index ++;
}
const newNode : Node = new Node(data);
newNode.next = currentNode;
newNode.prev = currentNode.prev;
(currentNode.prev as Node).next = newNode;
currentNode.prev = newNode;
this.size ++;
}
// remove a node at a specific position ad return its data
removeAt(position : number) : any {
if (position < 0 || position > this.size - 1) {
throw Error('Position ' + position + ' is not in the list');
}
if (position == 0) {
return this.removeHead();
}
if (position == this.size - 1) {
return this.removeTail();
}
let current : Node = this.head as Node;
let index : number = 0;
while (index < position) {
current = current.next as Node;
index ++;
}
(current.prev as Node).next = current.next;
(current.next as Node).prev = current.prev;
this.size --;
return current.data;
}
// return node data at a specific position
getAt(position : number) : any {
if (position < 0 || position >= this.size) {
throw Error('Position ' + position + ' is not in the list');
}
let current = this.head;
let index = 0;
while (index < position) {
current = (current as Node).next;
index ++;
}
return (current as Node).data;
}
// return head data
getHead() : any {
if (this.size == 0) {
throw Error('No head in an empty list');
}
return (this.head as Node).data;
}
// return tail data
getTail() : any {
if (this.size == 0) {
throw Error('No tail in an empty list');
}
return (this.tail as Node).data;
}
// remove list head and return its data
removeHead() : any {
if (this.size == 0) {
throw Error('No head in an empty list');
}
const data : any = (this.head as Node).data;
this.head = (this.head as Node).next;
if (this.head) {
this.head.prev = null;
} else {
this.tail = null;
}
this.size --;
return data;
}
// remove list tail and return its data
removeTail() : any {
if (this.size == 0) {
throw Error('No tail in an empty list');
}
const data : any = (this.tail as Node).data;
this.tail = (this.tail as Node).prev;
if (this.tail) {
this.tail.next = null;
} else {
this.head = null;
}
this.size --;
return data;
}
// print list content in the console
log() : void {
if (this.size == 0) {
console.log('Empty list');
return;
}
let current : Node = this.head as Node;
let result : any[] = [];
for (let i : number = 0; i < this.size; i ++) {
result.push(current.data);
if (current.next) {
current = current.next;
}
}
console.log(result.join(' <-> '));
}
}
Let’s see it in action with a simple script:
let list : LinkedList = new LinkedList(); // Empty list
list.append(1); // 1
list.prepend('Hello'); // Hello <-> 1
list.prepend(2); // 2 <-> Hello <-> 1
list.append('Here I am'); // 2 <-> Hello <-> 1 <-> Here I am
list.insertAt('x', 2); // 2 <-> Hello <-> x <-> 1 <-> Here I am
list.insertAt(5, 0); // 5 <-> 2 <-> Hello <-> x <-> 1 <-> Here I am
console.log(list.getHead()); // would prompt 5
console.log(list.getAt(0)); // would prompt 5
console.log(list.getTail()); // would prompt Here I am
console.log(list.getAt(4)) // would prompt 1
console.log(list.removeHead()); // would prompt 5
// then 2 <-> Hello <-> x <-> 1 <-> Here I am
console.log(list.removeTail()); // would pompt Here I am
// then 2 <-> Hello <-> x <-> 1
console.log(list.removeAt(3)); // would prompt 1
// then 2 <-> Hello <-> x
console.log(list.removeAt(1)); // would prompt Hello
// then 2 <-> x
list.log(); // would prompt 2 <-> HelloI will be using the doubly linked list in my Zuma prototype, do you have any ideas about using the doubly linked list?
Never miss an update! Subscribe, and I will bother you by email only when a new game or full source code comes out.