Mesi Rendon

home

about

tags

publications

Singly Linked List

Linked lists are linear dynamic data structures able to manage memory at runtime.

  ·   21 min read

Linked lists are linear dynamic data structures able to manage memory at runtime. On the surface, it might look like both arrays, and linked lists are the same, but their behavior makes them different underneath.

Elements in a linked list can point to the next element rather than letting the data structure point to a specific physical memory location. These elements are widely known as Linked List Nodes or simply Nodes.

Nodes represent not only a value but a reference to the next node (i.e., the next node’s memory address). This extra reference is known as a Link.

Linked List

Unlike arrays, linked lists do not provide constant time access to a particular node in the list. That means you must traverse the whole list until you find the element. But adding and removing elements from the beginning of the list can be done in constant time.

Linked List Nodes

The following is the implementation of a Linked List Node.

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

While you can perform certain operations using this data structure, you must be careful because accessing the list is done via referencing the head node. As a result, the head accessor can be lost, or if many objects could reference a node that was supposed to be the head, it has changed.

1head = new LinkedListNode(1, new LinkedListNode(2, new LinkedListNode, 3));
2console.log('Head:\n', head);
3
4while (head) {
5        head = head.next;
6}
7
8console.log('Head:', head);

Head:
LinkedListNode {
    value: 1,
    next: LinkedListNode {
        value: 2,
        next: LinkedListNode { value: undefined, next: null }
    }
}
Head: null

How could we solve such a nuance? We could implement a wrapper for the linked list for all its nodes.

Linked List

Let’s see the most basic LinkedList wrapper to implement with the append action (I’ll cover this later).

Note: I’ll be changing the LinkedList implementation to perform explanations better in a concise manner for each section. If you want to check the full implementation, take a look at the LinkedListNode and LinkedList files. It is also worth checking how they connect through the tests in the test

 1class BasicLinkedList {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5    }
 6
 7    append(value) {
 8        const node = new LinkedListNode(value);
 9
10        if (!this.head) {
11            this.head = node;
12            this.tail = node;
13
14            return this;
15        }
16
17        this.tail.next = node;
18        this.tail = node;
19
20        return this;
21    }
22
23    toString() {
24        const nodes = [];
25        let currentNode = this.head;
26        while (currentNode) {
27            nodes.push(currentNode.value);
28            currentNode = currentNode.next;
29        }
30        nodes.push('null');
31        return nodes.join('=>');
32    }
33}

Let’s run our previous example to see how we don’t lose track of the head.

 1linkedList = new BasicLinkedList();
 2linkedList
 3    .append(1)
 4    .append(2)
 5    .append(3)
 6    .append(4)
 7    .append(5);
 8
 9console.log('Linked List:\n', linkedList.toString(), '\n');
10
11head = linkedList.head;
12while (head) {
13    head = head.next
14}
15
16console.log('Head:', head, '\n');
17
18console.log('Linked List:\n', linkedList.toString())

Linked List:
 1=>2=>3=>4=>5=>null 

Head: null 

Linked List:
 1=>2=>3=>4=>5=>null

As you can see, we lost the head on the head variable, but it is not lost at all because the linked list wrapper still has the reference to such a head.

Operations

linkedList.length

This operation has $O(1)$ runtime since keeping the internal length variable updated is the key at insertion and deletion.

Note: I keep length as a function on the linked list implementation that accesses the size property.

 1class LinkedListWithLength {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    append(value) {
 9        // Let's create the isolated node.
10        const node = new LinkedListNode(value);
11
12        // We increase this linked list length.
13        this.length++;
14
15        // The new node is the head and tail if this linked list is empty.
16        if (!this.head) {
17            this.head = node;
18            this.tail = node;
19            return this;
20        }
21
22        // Attach the new node to the end of the linked list.
23        this.tail.next = node;
24        this.tail = node;
25
26        return this;
27    }
28
29    toString() {
30        const nodes = [];
31        let currentNode = this.head;
32        while (currentNode) {
33            nodes.push(currentNode.value);
34            currentNode = currentNode.next;
35        }
36        nodes.push('null');
37        return nodes.join('=>');
38    }
39}

 1linkedList = new LinkedListWithLength();
 2linkedList
 3    .append(1)
 4    .append(2)
 5    .append(3)
 6    .append(4)
 7    .append(5);
 8
 9console.log('Linked List:\n', linkedList.toString(), '\n');
10console.log('Linked List length:', linkedList.length);

Linked List:
 1=>2=>3=>4=>5=>null 

Linked List length: 5

linkedList.append

Append adds a node at the end of the linked list. The new appended node must be the linked list’s tail and point to null since it’s the last one. The previous tail points to the new tail. This operation is $O(1)$ runtime because there is no need to traverse the whole linked list. It’s just a matter of using the current tail and replacing such reference.

Append Linked List

We already have seen how it does work in the previous BasicLinkedList and LinkedListWithLength.

linkedList.prepend

Prepend adds a node at the beginning of the linked list. The new prepended node must be linked to the list’s head and point to the previous head. There is no need for further manipulation on the previous head since it points to the next node. This operation is $O(1)$ runtime because the node to manipulate is easily located through the linked list’s head pointer.

Prepend Linked List 

 1class LinkedListWithPrepend {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    prepend(value) {
 9        // The new node has to be the head of this list no matter what
10        const node = new LinkedListNode(value, this.head);
11        this.head = node;
12
13        // If there is no tail yet, we must have to create it.
14        if (!this.tail) {
15            this.tail = node;
16        }
17        this.length++;
18        return this;
19    }
20
21    toString() {
22        const nodes = [];
23        let currentNode = this.head;
24        while (currentNode) {
25            nodes.push(currentNode.value);
26            currentNode = currentNode.next;
27        }
28        nodes.push('null');
29        return nodes.join('=>');
30    }
31}

1linkedList = new LinkedListWithPrepend();
2linkedList
3    .prepend(1)
4    .prepend(2)
5    .prepend(3)
6    .prepend(4)
7    .prepend(5);
8
9console.log('LinkedList:\n', linkedList.toString());

LinkedList:
 5=>4=>3=>2=>1=>null

linkedList.insert

Insert adds a node at a given position in the linked list. The newly inserted node must be placed between nodes that are already linked in the list. However, this operation is more complex than appending or prepending since, in this case, we need to traverse the linked list to the point where the insertion must occur. Thus, insertion is $O(n)$ runtime complex.

Insert Linked List 

 1class LinkedListWithInsert {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    prepend(value) {
 9        const node = new LinkedListNode(value, this.head);
10        this.head = node;
11        if (!this.tail) {
12            this.tail = node;
13        }
14        this.length++;
15        return this;
16    }
17
18    insert(value, rawIndex) {
19        // We must guarantee the index is in the boundaries
20        const index = rawIndex < 0 ? 0 : rawIndex;
21
22        // If the index is 0, this is a prepend.
23        if (index === 0) this.prepend(value);
24        else {
25            this.length++;
26            let count = 1;
27            let currentNode = this.head;
28
29            // We create the node
30            const node = new LinkedListNode(value);
31
32            // We have to traverse the linked list up to the point of insertion
33            while (currentNode) {
34                if (count === index) break;
35                currentNode = currentNode.next;
36                count++;
37            }
38
39            // We perform the insertion on the reached node.
40            if (currentNode) {
41                node.next = currentNode.next;
42                currentNode.next = node;
43            }
44            else {
45                // We perform the insertion at the end.
46                if (this.tail) {
47                    this.tail.next = node;
48                    this.tail = node;
49                }
50                else {
51                    this.head = node;
52                    this.tail = node;
53                }
54            }
55        }
56        return this;
57    }
58
59    toString() {
60        const nodes = [];
61        let currentNode = this.head;
62        while (currentNode) {
63            nodes.push(currentNode.value);
64            currentNode = currentNode.next;
65        }
66        nodes.push('null');
67        return nodes.join('=>');
68    }
69}

 1linkedList = new LinkedListWithInsert();
 2linkedList
 3    .insert(-1, -1)
 4    .insert(1, 10)
 5    .insert(0, 1)
 6    .insert(5, 50)
 7    .insert(4, 3)
 8    .insert(3, 3)
 9    .insert(2, 2);
10
11console.log('Linked list:\n', linkedList.toString());

Linked list:
 -1=>0=>2=>1=>3=>4=>5=>null

linkedList.deleteHead

By deleting the head, the user will get the node that was in the head. The linked list will have its head pointing to the previous head’s next node, making it the new head, so the last head is detached from the list. The next’s previous node is set to null. Since we can access the head immediately, this operation is $O(1)$ runtime complex.

Delete Linked List Head 

 1class LinkedListWithDeleteHead {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    prepend(value) {
 9        const node = new LinkedListNode(value, this.head);
10        this.head = node;
11        if (!this.tail) {
12            this.tail = node;
13        }
14        this.length++;
15        return this;
16    }
17
18    deleteHead() {
19        // We return null for an empty linked list.
20        if (!this.head) return null;
21
22        // We create the dettached node.
23        let deletedNode = this.head;
24
25        // If the linked list has only one element, we must update the tail reference as well.
26        if (this.head === this.tail) this.tail = null;
27
28        // We move the linked list head to the deleted head's next node.
29        this.head = deletedNode.next;
30
31        // We decrease this linked list length.
32        this.length--;
33
34        // We return the dettached node.
35        return deletedNode;
36    }
37
38    toString() {
39        const nodes = [];
40        let currentNode = this.head;
41        while (currentNode) {
42            nodes.push(currentNode.value);
43            currentNode = currentNode.next;
44        }
45        nodes.push('null');
46        return nodes.join('=>');
47    }
48}

 1linkedList = new LinkedListWithDeleteHead();
 2linkedList
 3    .prepend(3)
 4    .prepend(2)
 5    .prepend(1)
 6    .prepend(-4);
 7
 8console.log('Linked list before deleting heads:\n', linkedList.toString(), '\n');
 9
10currentHead = linkedList.deleteHead();
11console.log('Current head:\n', currentHead, '\n');
12
13currentHead = linkedList.deleteHead();
14console.log('Current head:\n', currentHead, '\n');
15
16console.log('Linked list before deleting heads:\n', linkedList.toString());

Linked list before deleting heads:
 -4=>1=>2=>3=>null 

Current head:
LinkedListNode {
 value: -4,
 next: LinkedListNode {
    value: 1,
    next: LinkedListNode { value: 2, next: [LinkedListNode] }
  }
}

Current head:
LinkedListNode {
 value: 1,
 next: LinkedListNode {
   value: 2,
   next: LinkedListNode { value: 3, next: null }
 }
}

Linked list before deleting heads:
 2=>3=>null

linkedList.deleteTail

The user will get the node in the tail by deleting the tail. Then, the linked list will have the linked list’s tail detached. However, the tail’s previous node cannot be easily tracked (we will discuss this on the topic of the doubly linked list), thus, forcing us to traverse to the n-1th node. Once there, we make the n-1th node the new tail, pointing its next node to null. This situation makes this operation $O(n)$ runtime complex.

Delete Linked List Tail 

 1class LinkedListWithDeleteTail {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    prepend(value) {
 9        const node = new LinkedListNode(value, this.head);
10        this.head = node;
11        if (!this.tail) {
12            this.tail = node;
13        }
14        this.length++;
15        return this;
16    }
17
18    deleteTail() {
19        // If the linked list is empty we return null.
20        if (!this.head) return null;
21        let deletedNode = null;
22
23        // We delete the head if this linked list has only one node.
24        if (!this.head.next) {
25            deletedNode = this.head;
26            this.head = null;
27            this.tail = null;
28            return deletedNode;
29        }
30
31        // We traverse up to the n-1th node
32        let currentNode = this.head;
33        while (currentNode.next.next) {
34            currentNode = currentNode.next;
35        }
36
37        // We set the deleted node, not to the tail, but the n-1th node's next node.
38        deletedNode = currentNode.next;
39
40        // We dettach the tail out of the n-1th node.
41        currentNode.next = null;
42
43        // We update this linked list's tail reference.
44        this.tail = currentNode;
45
46        // We decrease this linked list length.
47        this.length--;
48        return deletedNode;
49    }
50
51    toString() {
52        const nodes = [];
53        let currentNode = this.head;
54        while (currentNode) {
55            nodes.push(currentNode.value);
56            currentNode = currentNode.next;
57        }
58        nodes.push('null');
59        return nodes.join('=>');
60    }
61}

 1linkedList = new LinkedListWithDeleteTail();
 2linkedList
 3    .prepend(5)
 4    .prepend(4)
 5    .prepend(3)
 6    .prepend(2)
 7    .prepend(1)
 8    .prepend(0);
 9
10console.log('Linked list before deleting tails:\n', linkedList.toString(), '\n');
11
12currentTail = linkedList.deleteTail();
13console.log('Current tail:\n', currentTail, '\n');
14
15currentTail = linkedList.deleteTail();
16console.log('Current tail:\n', currentTail, '\n');
17
18console.log('Linked list before deleting tails:\n', linkedList.toString());

Linked list before deleting tails:
 0=>1=>2=>3=>4=>5=>null

Current tail:
 LinkedListNode { value: 5, next: null }

Current tail:
 LinkedListNode { value: 4, next: null }

Linked list before deleting tails:
 0=>1=>2=>3=>null

linkedList.delete

Delete deletes the first node that matches the given value. Like other deletion options, this operation detaches the node from the linked list and returns it to the user.

The worst case for this operation is $O(n)$ runtime complexity (i.e., the node is around the end of the linked list). The best case would be $O(1)$ runtime complexity (i.e., the node is around the beginning of the linked list).

Delete Linked List Node By Value 

 1class LinkedListWithDelete {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    prepend(value) {
 9        const node = new LinkedListNode(value, this.head);
10        this.head = node;
11        if (!this.tail) {
12            this.tail = node;
13        }
14        this.length++;
15        return this;
16    }
17
18    delete(value) {
19        // If the list is empty, we return null
20        if (!this.head) return null;
21        let deletedNode = null;
22        let currentNode = this.head;
23
24        // Special case where the value is at the head.
25        // Here we must to dettach the head and update the linked list reference
26        // to that new head node.
27        if (this.head.value === value) {
28            deletedNode = this.head;
29            this.head = deletedNode.next;
30            this.size--;
31            return deletedNode;
32        }
33
34        // We must traverse the linked list up to the point where we find a
35        // node that matches the value criteria.
36        while (currentNode.next) {
37            if (currentNode.next.value === value) break;
38            currentNode = currentNode.next;
39        }
40
41        // We dettach the node out of the linked list.
42        deletedNode = currentNode.next;
43
44        // If no node matches the criteria, we return null.
45        if (!deletedNode) return deletedNode;
46
47        // We update this linked list's tail reference if the value is at the end.
48        if (deletedNode.value === this.tail.value) this.tail = currentNode;
49
50        // We link the current node's next node to the detached node's next.
51        currentNode.next = deletedNode.next;
52        this.length--;
53        return deletedNode;
54    }
55
56    toString() {
57        const nodes = [];
58        let currentNode = this.head;
59        while (currentNode) {
60            nodes.push(currentNode.value);
61            currentNode = currentNode.next;
62        }
63        nodes.push('null');
64        return nodes.join('=>');
65    }
66}

 1linkedList = new LinkedListWithDelete();
 2linkedList
 3    .prepend(5)
 4    .prepend(4)
 5    .prepend(3)
 6    .prepend(2)
 7    .prepend(1)
 8    .prepend(0);
 9
10console.log('Linked list before deleting some values', linkedList.toString(), '\n');
11
12one = linkedList.delete(1);
13console.log('One:', one, '\n');
14
15four = linkedList.delete(4);
16console.log('Four:', four, '\n');
17
18console.log('Linked list after deleting some values', linkedList.toString());

Linked list before deleting some values 0=>1=>2=>3=>4=>5=>null 

One: LinkedListNode {
  value: 1,
  next: LinkedListNode {
    value: 2,
    next: LinkedListNode { value: 3, next: [LinkedListNode] }
  }
}

Four: LinkedListNode {
  value: 4,
  next: LinkedListNode { value: 5, next: null }
}

Linked list after deleting some values 0=>2=>3=>5=>null

linkedList.deleteAll

Delete All deletes all the nodes that match the given value. This option not only returns a node that matches the value but detaches all the nodes that match the provided criteria. Thus, the runtime complexity is $O(n)$, because we must guarantee having traversed the whole linked list.

Delete All Linked List Nodes By Value 

 1class LinkedListWithDeleteAll {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    prepend(value) {
 9        const node = new LinkedListNode(value, this.head);
10        this.head = node;
11        if (!this.tail) {
12            this.tail = node;
13        }
14        this.length++;
15        return this;
16    }
17
18    deleteAll(value) {
19        // If the list is empty, we return null.
20        if (!this.head) return null;
21        let deletedNode = null;
22
23        // We dettach all the nodes that match the value and become the head.
24        while (this.head && this.head.value === value) {
25            deletedNode = this.head;
26            this.head = deletedNode.next;
27            this.length--;
28        }
29        let currentNode = this.head;
30        if (currentNode !== null)
31            while (currentNode.next) {
32                // We dettach all the nodes that matches the value across the linked list.
33                if (currentNode.next.value === value) {
34                    deletedNode = currentNode.next;
35                    currentNode.next = deletedNode.next;
36                    this.length--;
37                }
38                else {
39                    currentNode = currentNode.next;
40                }
41            }
42
43        // We process the node that is at the tail if it matches the value.
44        if (this.tail.value === value) this.tail = currentNode;
45        return deletedNode;
46    }
47
48    toString() {
49        const nodes = [];
50        let currentNode = this.head;
51        while (currentNode) {
52            nodes.push(currentNode.value);
53            currentNode = currentNode.next;
54        }
55        nodes.push('null');
56        return nodes.join('=>');
57    }
58}

 1linkedList = new LinkedListWithDeleteAll();
 2linkedList
 3    .prepend(5)
 4    .prepend(1)
 5    .prepend(4)
 6    .prepend(1)
 7    .prepend(3)
 8    .prepend(1)
 9    .prepend(2)
10    .prepend(1)
11    .prepend(-1)
12    .prepend(1)
13    .prepend(0);
14
15console.log('Linked list before deleting all ones', linkedList.toString(), '\n');
16
17one = linkedList.deleteAll(1);
18console.log('One:', one, '\n');
19
20console.log('Linked list after deleting all ones', linkedList.toString());

Linked list before deleting all ones 0=>1=>-1=>1=>2=>1=>3=>1=>4=>1=>5=>null 

One: LinkedListNode {
      value: 1,
      next: LinkedListNode { value: 5, next: null }
} 

Linked list after deleting all ones 0=>-1=>2=>3=>4=>5=>null

linkedList.find

This Search operation receives either a value or a custom search function. Then, we traverse the linked list until we find a node that matches either the value or a node that matches the custom search function criteria.

The worst case for this operation is $O(n)$ runtime complexity (i.e., the node is around the end of the linked list). The best case would be $O(1)$ runtime complexity (i.e., the node is around the beginning of the linked list).

This operation is almost identical to Delete a Node by Value. The only difference is that the returned node is not detached from the linked list.

Find Linked List By Value

Note: Check the actual implementation since it gets an object with either the value or the value and a callback function to use with that value. In this way, you also could implement a find by greater than a specific value function.

 1find({ value = undefined, callback = undefined }) {
 2    // If the list is empty, we return null
 3    if (!this.head) return null;
 4
 5    let currentNode = this.head;
 6    while (currentNode) {
 7        // If a custom search function was provided and the node
 8        // matches with the function criteria, we return such node.
 9        if (callback && callback(currentNode.value))
10            return currentNode;
11
12        // If the node's value matches the provided value, we return such node.
13        if (value !== undefined && this.comparator.equal(currentNode.value, value))
14            return currentNode;
15        currentNode = currentNode.next
16    }
17
18    return null;
19}

 1class LinkedListWithFind {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    prepend(value) {
 9        const node = new LinkedListNode(value, this.head);
10        this.head = node;
11        if (!this.tail) {
12            this.tail = node;
13        }
14        this.length++;
15        return this;
16    }
17
18    find(value = undefined) {
19        if (!this.head) return null;
20        let currentNode = this.head;
21        while (currentNode) {
22            if (value !== undefined && currentNode.value === value)
23                return currentNode;
24            currentNode = currentNode.next
25        }
26        return null;
27    }
28
29    toString() {
30        const nodes = [];
31        let currentNode = this.head;
32        while (currentNode) {
33            nodes.push(currentNode.value);
34            currentNode = currentNode.next;
35        }
36        nodes.push('null');
37        return nodes.join('=>');
38    }
39}

 1linkedList = new LinkedListWithFind();
 2linkedList
 3    .prepend(10)
 4    .prepend(9)
 5    .prepend(8)
 6    .prepend(7)
 7    .prepend(6)
 8    .prepend(5)
 9    .prepend(4)
10    .prepend(3)
11    .prepend(2)
12    .prepend(1)
13    .prepend(0);
14
15console.log('Linked list', linkedList.toString(), '\n');
16
17seven = linkedList.find(7);
18console.log('Seven:', seven, '\n');

Linked list 0=>1=>2=>3=>4=>5=>6=>7=>8=>9=>10=>null 

Seven: LinkedListNode {
  value: 7,
  next: LinkedListNode {
    value: 8,
    next: LinkedListNode { value: 9, next: [LinkedListNode] }
  }
}

linkedList.fromArray

This operation appends each element in the provided array to this linked list. Therefore, it has $O(A)$ runtime complexity. $A$ being the array’s length.

 1class LinkedListWithFromArray {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    append(value) {
 9        const node = new LinkedListNode(value);
10        this.length++;
11        if (!this.head) {
12            this.head = node;
13            this.tail = node;
14            return this;
15        }
16        this.tail.next = node;
17        this.tail = node;
18        return this;
19    }
20
21    fromArray(array) {
22        for (const e of array) {
23            this.append(e);
24        }
25    }
26
27    toString() {
28        const nodes = [];
29        let currentNode = this.head;
30        while (currentNode) {
31            nodes.push(currentNode.value);
32            currentNode = currentNode.next;
33        }
34        nodes.push('null');
35        return nodes.join('=>');
36    }
37}

1linkedList = new LinkedListWithFromArray();
2array = [3, 4, 6, 2, 8, 32, 8, 5, -23, -87, 53, 7, 0, 8];
3linkedList.fromArray(array);
4
5console.log('Linked list from array:\n', linkedList.toString());

Linked list from array:
 3=>4=>6=>2=>8=>32=>8=>5=>-23=>-87=>53=>7=>0=>8=>null

linkedList.toArray

This operation returns an array of all the nodes in this linked list. Since we must traverse the linked list, the runtime complexity is $O(n)$.

 1class LinkedListWithToArray {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    append(value) {
 9        const node = new LinkedListNode(value);
10        this.length++;
11        if (!this.head) {
12            this.head = node;
13            this.tail = node;
14            return this;
15        }
16        this.tail.next = node;
17        this.tail = node;
18        return this;
19    }
20
21    fromArray(array) {
22        for (const e of array) {
23            this.append(e);
24        }
25    }
26
27    toArray() {
28        const nodes = [];
29        let currentNode = this.head;
30        while (currentNode) {
31            nodes.push(currentNode);
32            currentNode = currentNode.next;
33        }
34        return nodes
35    }
36
37    toString() {
38        const nodes = [];
39        let currentNode = this.head;
40        while (currentNode) {
41            nodes.push(currentNode.value);
42            currentNode = currentNode.next;
43        }
44        nodes.push('null');
45        return nodes.join('=>');
46    }
47}

1linkedList = new LinkedListWithToArray();
2array = [3, 4, 6, 2, 8, 32, 8, 5, -23, -87, 53, 7, 0, 8];
3linkedList.fromArray(array);
4
5console.log('Linked list from array:\n', linkedList.toString(), '\n');
6
7nodesArray = linkedList.toArray();
8
9console.log('Array of LinkedListNodes', nodesArray);

Linked list from array:
 3=>4=>6=>2=>8=>32=>8=>5=>-23=>-87=>53=>7=>0=>8=>null 

Array of LinkedListNodes [
  LinkedListNode {
     value: 3,
     next: LinkedListNode { value: 4, next: [LinkedListNode] }
   },
  LinkedListNode {
     value: 4,
     next: LinkedListNode { value: 6, next: [LinkedListNode] }
   },
  LinkedListNode {
     value: 6,
     next: LinkedListNode { value: 2, next: [LinkedListNode] }
   },
  LinkedListNode {
     value: 2,
     next: LinkedListNode { value: 8, next: [LinkedListNode] }
   },
  LinkedListNode {
     value: 8,
     next: LinkedListNode { value: 32, next: [LinkedListNode] }
   },
  LinkedListNode {
  ...
  next: LinkedListNode { value: 8, next: null }
  },
  LinkedListNode { value: 8, next: null }
]

Have you noticed this is an array of LinkedListNodes and not their values? That makes me think that the toArray function could also receive a custom function to tell this method how the nodes should be returned as an array. But, on the other hand, maybe we need their values.

1arraifyFn = (node) => node.val;
2nodes = linkedList.toArray(arraifyFn);

linkedList.reverse

Reversing a linked list is a process that starts at the head. First, we temporarily save the next node from the current node’s next accessor. Then, we change the next node of the current node so it would link to the previous node. Then, we move the previous node and current node one step forward. Finally, when we reach the tail, we swap it with the head. Since we must traverse the linked list, this operation has $O(n)$ runtime complexity.

Reverse Linked List 

 1class LinkedListWithReverse {
 2    constructor() {
 3        this.head = null;
 4        this.tail = null;
 5        this.length = 0;
 6    }
 7
 8    append(value) {
 9        const node = new LinkedListNode(value);
10        this.length++;
11        if (!this.head) {
12            this.head = node;
13            this.tail = node;
14            return this;
15        }
16        this.tail.next = node;
17        this.tail = node;
18        return this;
19    }
20
21    fromArray(array) {
22        for (const e of array) {
23            this.append(e);
24        }
25    }
26
27    reverse() {
28        let currNode = this.head;
29        let prevNode = null;
30        let nextNode = null;
31
32        while (currNode) {
33            // Store next node.
34            nextNode = currNode.next;
35
36            // Change next node of the current node so it would link to previous node.
37            currNode.next = prevNode;
38
39            // Move prevNode and currNode nodes one step forward.
40            prevNode = currNode;
41            currNode = nextNode;
42        }
43
44        // Reset head and tail.
45        this.tail = this.head;
46        this.head = prevNode;
47        return this;
48    }
49
50    toString() {
51        const nodes = [];
52        let currentNode = this.head;
53        while (currentNode) {
54            nodes.push(currentNode.value);
55            currentNode = currentNode.next;
56        }
57        nodes.push('null');
58        return nodes.join('=>');
59    }
60}

1linkedList = new LinkedListWithReverse();
2array = [3, 4, 6, 2, 8, 32, 8, 5, -23, -87, 53, 7, 0, 8];
3linkedList.fromArray(array);
4
5console.log('Linked list from array:\n', linkedList.toString(), '\n');
6linkedList.reverse();
7console.log('Reversed linked list:\n', linkedList.toString(), '\n');

Linked list from array:
 3=>4=>6=>2=>8=>32=>8=>5=>-23=>-87=>53=>7=>0=>8=>null 

Reversed linked list:
 8=>0=>7=>53=>-87=>-23=>5=>8=>32=>8=>2=>6=>4=>3=>null

Runtime Complexity Overview

Access Search Insertion Deletion
$O(n)$ $O(n)$ $O(n)$ $O(1)$ at beginning $O(n)$ $O(1)$ at beginning

Space Complexity

Linked lists have $O(n)$ space complexity.

Bibliography

  1. JavaScript Data Structures and Algorithms1
  2. Data Structures and Algorithm Analysis in Java2
  3. Introduction to Algorithms3
  4. Linked list4

  1. https://doi.org/10.1007/978-1-4842-3988-9 ↩︎

  2. https://www.pearson.com/en-us/subject-catalog/p/data-structures-and-algorithm-analysis-in-java/P200000003475/9780137518821 ↩︎

  3. https://archive.org/details/introduction-to-algorithms-third-edition-2009 ↩︎

  4. https://en.wikipedia.org/wiki/Linked_list ↩︎

←
Algorithmic Complexity
Doubly Linked List
→
back to top