Data Structures. Linked List

8 ноября 2023 г.

This is a short expanded summary of the section about linked lists in the book Computer Science Guide by William Springer.

Basic information

A linked list is a data structure where each element contains data and a pointer to the next element in the list (in a doubly linked list, it also contains a reference to the previous element).

A pointer to a linked list is simply a pointer to the first element, or the head of the list.

Elements can be stored in different memory locations. To find a specific element, you must start from the first element and traverse the entire list.

In many ways, it is an extension of an array.

Example

A train as an analogy for a doubly linked list: each carriage is connected to the previous one and (if it exists) to the next one. New carriages can be easily added to the end of the train, and a carriage can also be inserted in the middle by detaching and reconnecting existing carriages before and after it. However, you cannot directly access a carriage—you must first traverse the entire train to reach it.

Comparison with arrays

JavaScript implementation

This implementation example is based on the one from this website. A slightly different implementation (using a tail pointer) can be found here.

• Each value is stored in a separate object called a node.
• A node stores a value and a reference to the next node in the list.

1class LinkedListNode {
2	constructor(value, next = null) {
3		this.value = value;
4		this.next = next;
5	}
6}

The list is created using a separate class, working only with the head of the list (there are also implementations that store both head and tail).

1class LinkedList {
2	constructor() {
3		// save a pointer to the head
4		this.head = null;
5	}
6}

Adding elements

To the beginning of the list

The new element becomes the head, and its next pointer references the previous head.

1add(value) {
2		this.head = new LinkedListNode(value, this.head);
3}

By index (middle or end of the list)

1insert(index, value) {
2		if (this.head === null) {
3			// if the list is empty, insert the element at the beginning
4			this.head = new LinkedListNode(value, null);
5		} else if (index === 0) {
6			this.add(value);
7		} else {
8		// You cannot insert an element directly into a specific position in a linked list;
9        // you first need to traverse all of its nodes.
10			let current = this.head;
11			while (current.next !== null && index > 1) {
12				current = current.next;
13				index = index - 1;
14			}
15
16			// Set the previous element at the specified index to point to the new node
17			current.next = new LinkedListNode(value, current.next);
18		}
19	}

Example: creating a list and adding three nodes: 4, 24, 88.

1const list = new LinkedList();
2
3list.add(4);
4list.add(24);
5list.add(88);

Head is the node containing the value 88.

We now want to insert a node with the value 21 at index 2:

list.insert(2, 21);

let current= 88;

First iteration:

After the first while loop iteration, the values are: current 24, index 1;

The loop condition is no longer true because index === 1, so we leave the loop and update the next pointer of the node containing 24 to reference the new node.

If we want to add an element at index 3 instead of 2:

list.insert(3, 21);

The initial value of current is also set to head:

let current= 88;

First iteration:

After the first execution of the while loop, we get:

current - 24, index 2;

Second iteration:

We get:current - 4, index 1;

The loop condition is not satisfied because index === 1, so we exit the loop and set the next pointer of the node with the value 4 to point to the new element.

Removing elements

From the beginning

We replace head with the next node.

1remove() {
2		if (this.head === null) return;
3
4		this.head = this.head.next;
5}

By index (middle or end of the list)

1removeAt(index) {
2		if (this.head === null) {
3			return;
4		} else if (index === 0 || this.head.next === null) {
5			this.head = this.head.next;
6		} else {
7			let current = this.head;
8			while (current.next.next !== null && index > 1) {
9				current = current.next;
10				index = index - 1;
11			}
12
13			current.next = current.next.next;
14		}
15	}

As you can see, the process of traversing the list is the same as when inserting an element. For a better understanding, let's also walk through it using the example of the list we created earlier, which consists of the nodes 4, 24, and 88.

1const list = new LinkedList();
2
3list.add(4);
4list.add(24);
5list.add(88);
6
7// LinkedList {
8//   head: LinkedListNode {
9//     value: 88,
10//     next: LinkedListNode { value: 24, next: [LinkedListNode] }
11//   }
12// }

We want to remove the node with the value 4. Its index is 2:

list.removeAt(2)

We assign head to current:

let current= 88;

First iteration:
After the first iteration of the while loop, we get:

current 24, index 1;

The loop terminates because the condition is no longer met (index === 1). We then update the next pointer of the node containing 24 to point to the next node after 4, effectively removing the node with value 4 from the list.

After printing the list to the console, the result will be:

1// LinkedList {
2//   head: LinkedListNode {
3//     value: 88,
4//     next: LinkedListNode { value: 24, next: null }
5//   }
6// }

Full JavaScript implementation

1class LinkedListNode {
2	constructor(value, next = null) {
3		this.value = value;
4		this.next = next;
5	}
6}
7
8class LinkedList {
9	constructor() {
10		this.head = null;
11	}
12
13	add(value) {
14		this.head = new LinkedListNode(value, this.head);
15	}
16
17	// Inserting an element in the middle or at the end of the list (by index)
18	insert(index, value) {
19		if (this.head === null) {
20			this.head = new LinkedListNode(value, null);
21		} else if (index === 0) {
22			this.add(value);
23		} else {
24			let current = this.head;
25			while (current.next !== null && index > 1) {
26				current = current.next;
27				index = index - 1;
28			}
29
30			current.next = new LinkedListNode(value, current.next);
31		}
32	}
33
34	// Remove an element from the head of the list
35	remove() {
36		if (this.head === null) return;
37
38		this.head = this.head.next;
39	}
40
41    // Removing an element by its index
42	removeAt(index) {
43		if (this.head === null) {
44			// Return from the function if the list is empty
45			return;
46		} else if (index === 0 || this.head.next === null) {
47			this.head = this.head.next;
48		} else {
49			let current = this.head;
50			while (current.next.next !== null && index > 1) {
51				current = current.next;
52				index = index - 1;
53			}
54
55			current.next = current.next.next;
56		}
57	}
58}