Mesi Rendon

home

about

tags

publications

Doubly Linked List

A bidirectional linked lists

  ·   21 min read

We already have seen the Singly Linked List topic. Doubly Linked Lists can be thought of as an extension of Singly Linked Lists where the new Nodes implementation points to not only the next Node but the previous Node, making it a bidirectional implementation.

Doubly Linked List

Linked lists can have multiple forms. We already have seen the Singly Linked List, but, as in this case, they can be Doubly Linked Lists, Sorted, Unsorted, or even Circular (i.e., the head’s previous link points to the tail, and the tail’s next link points to the head).

Doubly Linked List Nodes

We have a slightly different implementation from the normal Linked List Node. Here we need to add the previous link accessor.

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

Linked list nodes are not the actual linked list. While we can perform certain operations, we still need to be careful and not lose references to head and tail accessors.

 1head = new DoublyLinkedListNode(1);
 2next = new DoublyLinkedListNode(2);
 3tail = new DoublyLinkedListNode(3);
 4
 5next.next = tail;
 6head.next = next;
 7tail.previous = next;
 8next.previous = head;
 9
10current = head;
11
12while (current) {
13  console.log(
14    current.previous ? current.previous.value : 'null',
15    '<=', current.value, '=>',
16    current.next ? current.next.value : 'null'
17  );
18  current = current.next;
19}

1null <= 1 => 2
21 <= 2 => 3
32 <= 3 => null

Doubly Linked List

Once again, to avoid losing references, we must implement a wrapper DoublyLinkedList to help us keep them and perform operations on the linked list. I’ll implement as many as needed to explain each procedure.

doublylinkedList.length

We can set a length property for the doubly linked list with O(1) runtime since updating this property is an essential operation at insertion and deletion actions.

1class AReallyBasicDoublyLinkedList {
2  constructor() {
3    this.head = null;
4    this.tail = null;
5    this.length = 0;
6  }
7}

This AReallyBasicDoublyLinkedList is not helpful, but it allows us to see how we can access the length property at any given time.

1doublylinkedList = new AReallyBasicDoublyLinkedList();
2console.log(`Recently Doubly Linked List's length: ${doublylinkedList.length}`);

1Recently Doubly Linked List's length: 0

doublyLinkedList.prepend

Prepend adds a node at the beginning of the doubly linked list. The new prepended node must be linked to the list’s head, and its next node must point to the previous head node. Unlike singly linked lists, we must manipulate the previous head because it has to point to the current head as its previous node. This operation is $O(n)$ runtime because the node to manipulate is easily located through the linked list’s head pointer.

Doubly Linked List Prepend 

 1class PrependDoublyLinkedList {
 2  constructor() {
 3    this.head = null;
 4    this.tail = null;
 5    this.length = 0;
 6  }
 7
 8  prepend(value) {
 9    // We create the new node.
10    const newNode = new DoublyLinkedListNode(value);
11
12    // We must increase this linked list's size.
13    this.length++;
14
15    // If there is no head we must make the new node head and tail.
16    if (!this.head) {
17      this.head = newNode;
18      this.tail = newNode;
19      return this;
20    }
21
22    // Attach the new node to the start of the linked list.
23    this.head.previous = newNode;
24
25    // The current head must be the next of the new head.
26    newNode.next = this.head;
27
28    // Update the head reference to be the new node.
29    this.head = newNode;
30
31    return this;
32  }
33
34  toString() {
35    const nodes = ['null'];
36    let currentNode = this.head;
37    while (currentNode) {
38      nodes.push(currentNode.value);
39      currentNode = currentNode.next;
40    }
41    nodes.push('null');
42    return nodes.join('<=>');
43  }
44}

 1doublyLinkedList = new PrependDoublyLinkedList();
 2console.log(`Doubly linked list's current length: ${doublyLinkedList.length}`);
 3
 4console.log(`Prepend 1, 2, 3, 4, and 5 as nodes.`)
 5doublyLinkedList
 6  .prepend(1)
 7  .prepend(2)
 8  .prepend(3)
 9  .prepend(4)
10  .prepend(5);
11
12console.log(`Doubly linked list's current length: ${doublyLinkedList.length}`);
13console.log(`Doubly Linked List: ${doublyLinkedList.toString()}`);

1Doubly linked list's current length: 0
2Prepend 1, 2, 3, 4, and 5 as nodes.
3Doubly linked list's current length: 5
4Doubly Linked List: null<=>5<=>4<=>3<=>2<=>1<=>null

doublyLinkedList.append

Append adds a node at the end of the doubly linked list. The new appended node must be linked to the list’s tail accessor and point to null for its next reference and to the previous tail for its previous accessor. The previous tail must update its next reference to the new tail. Its algorithmic complexity is $O(1)$.

Doubly Linked List Append 

 1class AppendDoublyLinkedList {
 2  constructor() {
 3    this.head = null;
 4    this.tail = null;
 5    this.length = 0;
 6  }
 7
 8  append(value) {
 9    // We create the new node.
10    const newNode = new DoublyLinkedListNode(value);
11
12    // We must increase this linked list's size.
13    this.length++;
14
15    // If there is no head we must make the new node head and tail.
16    if (!this.head) {
17      this.head = newNode;
18      this.tail = newNode;
19      return this;
20    }
21
22    // Attach the new node to the end of the linked list.
23    this.tail.next = newNode;
24
25    // The current tail must be the previous of the new tail.
26    newNode.previous = this.tail;
27
28    // Update the tail reference to be the new node.
29    this.tail = newNode;
30
31    return this;
32  }
33
34  toString() {
35    const nodes = ['null'];
36    let currentNode = this.head;
37    while (currentNode) {
38      nodes.push(currentNode.value);
39      currentNode = currentNode.next;
40    }
41    nodes.push('null');
42    return nodes.join('<=>');
43  }
44}

 1doublyLinkedList = new AppendDoublyLinkedList();
 2console.log(`Doubly linked list's current length: ${doublyLinkedList.length}`);
 3
 4console.log(`Append 1, 2, 3, 4, and 5 as nodes.`)
 5doublyLinkedList
 6  .append(1)
 7  .append(2)
 8  .append(3)
 9  .append(4)
10  .append(5);
11
12console.log(`Doubly linked list's current length: ${doublyLinkedList.length}`);
13console.log(`Doubly Linked List: ${doublyLinkedList.toString()}`);

1Doubly linked list's current length: 0
2Append 1, 2, 3, 4, and 5 as nodes.
3Doubly linked list's current length: 5
4Doubly Linked List: null<=>1<=>2<=>3<=>4<=>5<=>null

doublyLinkedList.insert

Insert adds a node at a given position in the linked list. We must place the newly inserted node between nodes that are already linked in the list. This operation is, however, more complex than prepending or appending since, in this case, we need to traverse the linked list up to the point of insertion and update references for the current node, the previous and next ones making the links as needed. Thus, insertion is an $O(n)$ runtime complexity operation.

Doubly Linked List Insertion 

 1class InsertDoublyLinkedList {
 2  constructor() {
 3    this.head = null;
 4    this.tail = null;
 5    this.length = 0;
 6  }
 7
 8  prepend(value) {
 9    const newNode = new DoublyLinkedListNode(value);
10    this.length++;
11    if (!this.head) {
12      this.head = newNode;
13      this.tail = newNode;
14      return this;
15    }
16    this.head.previous = newNode;
17    newNode.next = this.head;
18    this.head = newNode;
19    return this;
20  }
21
22  append(value) {
23    const newNode = new DoublyLinkedListNode(value);
24    this.length++;
25    if (!this.head) {
26      this.head = newNode;
27      this.tail = newNode;
28      return this;
29    }
30    this.tail.next = newNode;
31    newNode.previous = this.tail;
32    this.tail = newNode;
33    return this;
34  }
35
36  insert(value, rawIndex) {
37    // We must ensure the index is in the right boundary
38    const index = rawIndex < 0 ? 0 : rawIndex;
39
40    // If index is 0, we should prepend the new node.
41    if (index === 0) this.prepend(value);
42    else {
43      let count = 1;
44      let currentNode = this.head;
45      const newNode = new DoublyLinkedListNode(value);
46
47      // We find the position of insertion
48      while (currentNode) {
49        if (count === index) break;
50        currentNode = currentNode.next;
51        count++;
52      }
53
54      // If the node is found we perform the insertion
55      if (currentNode) {
56        this.length++;
57        newNode.next = currentNode.next;
58        newNode.previous = currentNode;
59        currentNode.next = newNode;
60      }
61
62      // If we don't find the node, it means that we must append the new node.
63      else this.append(value);
64    }
65
66    return this;
67  }
68
69  toString() {
70    const nodes = ['null'];
71    let currentNode = this.head;
72    while (currentNode) {
73      nodes.push(currentNode.value);
74      currentNode = currentNode.next;
75    }
76    nodes.push('null');
77    return nodes.join('<=>');
78  }
79}

 1doublyLinkedList = new InsertDoublyLinkedList();
 2
 3doublyLinkedList
 4  .append(1)
 5  .append(3)
 6  .append(5);
 7
 8doublyLinkedList
 9  .insert(0, -100)
10  .insert(2, 2)
11  .insert(4, 4)
12  .insert(6, 10);
13
14console.log(`Doubly Linked List: ${doublyLinkedList.toString()}`);

1Doubly Linked List: null<=>0<=>1<=>2<=>3<=>4<=>5<=>6<=>null

I’ve used the previous methods prepend and append to build the insertion. How could we eliminate the append at the end of the list? You can modify as you need in the tests to get the same behavior. Remember not to change the tests but the code.

doublyLinkedList.fromArray

Appends each element in the given array to this doubly linked list. This operation has $O(A)$ runtime complexity. $A$ being the array’s length.

 1class FromArrayDoublyLinkedList {
 2  constructor() {
 3    this.head = null;
 4    this.tail = null;
 5    this.length = 0;
 6  }
 7
 8  append(value) {
 9    const newNode = new DoublyLinkedListNode(value);
10    this.length++;
11    if (!this.head) {
12      this.head = newNode;
13      this.tail = newNode;
14      return this;
15    }
16    this.tail.next = newNode;
17    newNode.previous = this.tail;
18    this.tail = newNode;
19    return this;
20  }
21
22  fromArray(array) {
23    for (const e of array) {
24      this.append(e);
25    }
26    return this;
27  }
28
29  toString() {
30    const nodes = ['null'];
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}

1doublyLinkedList = new FromArrayDoublyLinkedList();
2doublyLinkedList
3  .fromArray([1, 2, 3, 4, 5])
4  .fromArray([6, 7, 8, 9, 10]);
5console.log(`Doubly Linked List from Array: ${doublyLinkedList.toString()}`);

1Doubly Linked List from Array: null<=>1<=>2<=>3<=>4<=>5<=>6<=>7<=>8<=>9<=>10<=>null

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

1doublyLinkedList = new ToArrayDoublyLinkedList();
2doublyLinkedList.fromArray([1, 2, 3]);
3console.log(`Doubly Linked List: ${doublyLinkedList.toString()}`);
4nodes = doublyLinkedList.toArray();
5nodes.forEach((node) => console.log(node.value));
6console.log(nodes[1]);

 1Doubly Linked List: null<=>1<=>2<=>3<=>null
 21
 32
 43
 5<ref *1> DoublyLinkedListNode {
 6  value: 2,
 7  previous: DoublyLinkedListNode {
 8    value: 1,
 9    previous: null,
10    next: [Circular *1]
11  },
12  next: DoublyLinkedListNode {
13    value: 3,
14    previous: [Circular *1],
15    next: null
16  }
17}

doublyLinkedList.find

Find operation receives a finder that can be a normal value (i.e., primitives like numbers or strings, etc.) or a custom finding function. We traverse the doubly linked list until we find the 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).

Doubly Linked List Find 

 1class FindDoublyLinkedList {
 2  constructor() {
 3    this.head = null;
 4    this.tail = null;
 5    this.length = 0;
 6  }
 7
 8  append(value) {
 9    const newNode = new DoublyLinkedListNode(value);
10    this.length++;
11    if (!this.head) {
12      this.head = newNode;
13      this.tail = newNode;
14      return this;
15    }
16    this.tail.next = newNode;
17    newNode.previous = this.tail;
18    this.tail = newNode;
19    return this;
20  }
21
22  find(finder) {
23    // If the list is empty we return null
24    if (!this.head) return null;
25
26    // We traverse the linked list
27    let currentNode = this.head;
28    while (currentNode) {
29      // If the finder is a function and the node fulfills the
30      // function's logic, we return it.
31      // It it's a value, we return that node by value
32      if (finder instanceof Function &&
33        finder(currentNode.value) ||
34        currentNode.value === finder) {
35        let found = currentNode;
36        found.next = null;
37        found.previous = null;
38        return found;
39      }
40      currentNode = currentNode.next;
41    }
42
43    return currentNode;
44  }
45
46  fromArray(array) {
47    for (const e of array) {
48      this.append(e);
49    }
50    return this;
51  }
52
53  toString() {
54    const nodes = ['null'];
55    let currentNode = this.head;
56    while (currentNode) {
57      nodes.push(currentNode.value);
58      currentNode = currentNode.next;
59    }
60    nodes.push('null');
61    return nodes.join('<=>');
62  }
63}

1doublyLinkedListByValue = new FindDoublyLinkedList();
2doublyLinkedListByValue.fromArray([1, 2, 3, 4, 5]);
3console.log(`Doubly Linked List By Value: ${doublyLinkedListByValue.toString()}`);
4found = doublyLinkedListByValue.find(3);
5console.log(`Found node: ${JSON.stringify(found)}`);

1Doubly Linked List By Value: null<=>1<=>2<=>3<=>4<=>5<=>null
2Found node: {"value":3,"previous":null,"next":null}

Note: The founded node does not reference the linked list node’s previous and next nodes. We could change this.

Note: This implementation is a reduced version. The coded Doubly Linked List has a default comparator or a custom at the linked list’s creation.

Let’s check by complex values…

1doublyLinkedListByObject = new FindDoublyLinkedList();
2doublyLinkedListByObject.fromArray([
3  { key: 'k1', value: 'Value 1' },
4  { key: 'k2', value: 'Value 2' },
5  { key: 'k3', value: 'Value 3' },
6]);
7console.log(`Doubly Linked List objects: ${doublyLinkedListByObject.toString()}`);
8found = doublyLinkedListByObject.find((value) => value.key === 'k2');
9console.log(`Found node: ${JSON.stringify(found)}`);

1Doubly Linked List objects: null<=>[object Object]<=>[object Object]<=>[object Object]<=>null
2Found node: {"value":{"key":"k2","value":"Value 2"},"previous":null,"next":null}

doublyLinkedList.reverse

Reversing a linked list is a process that starts at the head node. Then, we have to traverse the list using three helper nodes. currentNode to know where we are, previousNode and nextNode to save a reference to the current node’s previous and next nodes, and also to swap those values. After the whole list is traversed, we update the values for the head and tail accessors.

Doubly Linked List Reverse 

 1class ReverseDoublyLinkedList {
 2  constructor() {
 3    this.head = null;
 4    this.tail = null;
 5    this.length = 0;
 6  }
 7
 8  append(value) {
 9    const newNode = new DoublyLinkedListNode(value);
10    this.length++;
11    if (!this.head) {
12      this.head = newNode;
13      this.tail = newNode;
14      return this;
15    }
16    this.tail.next = newNode;
17    newNode.previous = this.tail;
18    this.tail = newNode;
19    return this;
20  }
21
22  reverse() {
23    // Create auxiliary sentinel nodes;
24    let currentNode = this.head;
25    let previousNode = null;
26    let nextNode = null;
27
28    while (currentNode) {
29      // Let's store current node's previous and next
30      // nodes references.
31      nextNode = currentNode.next;
32      previousNode = currentNode.previous;
33
34      // Let's swap current's previous and next nodes
35      // references.
36      currentNode.next = previousNode;
37      currentNode.previous = nextNode;
38
39      // The previous is our current for next iteration.
40      previousNode = currentNode;
41
42      // Our current is next node for next iteration.
43      currentNode = nextNode;
44    }
45
46    // We update references of head and tail sentinel nodes.
47    this.tail = this.head;
48    this.head = previousNode;
49
50    return this;
51  }
52
53  fromArray(array) {
54    for (const e of array) {
55      this.append(e);
56    }
57    return this;
58  }
59
60  toString() {
61    const nodes = ['null'];
62    let currentNode = this.head;
63    while (currentNode) {
64      nodes.push(currentNode.value);
65      currentNode = currentNode.next;
66    }
67    nodes.push('null');
68    return nodes.join('<=>');
69  }
70}

1doublyLinkedList = new ReverseDoublyLinkedList();
2doublyLinkedList.fromArray([1, 2, 3, 4]);
3console.log(`Doubly Linked List Normal: ${doublyLinkedList.toString()}`);
4doublyLinkedList.reverse();
5console.log(`Doubly Linked List Reverserd: ${doublyLinkedList.toString()}`);

1Doubly Linked List Normal: null<=>1<=>2<=>3<=>4<=>null
2Doubly Linked List Reverserd: null<=>4<=>3<=>2<=>1<=>null

doublyLinkedList.deleteHead

The user will get the node in the head accessor by deleting the head. The linked list will have its previous’ head next node as the new head as the previous head has been detached. The new head must point its previous node to null. Since we can access the head immediately, this operation is $O(1)$ runtime complex.

Doubly Linked List Delete Head 

 1class DeleteHeadDoublyLinkedList {
 2  constructor() {
 3    this.head = null;
 4    this.tail = null;
 5    this.length = 0;
 6  }
 7
 8  append(value) {
 9    const newNode = new DoublyLinkedListNode(value);
10    this.length++;
11    if (!this.head) {
12      this.head = newNode;
13      this.tail = newNode;
14      return this;
15    }
16    this.tail.next = newNode;
17    newNode.previous = this.tail;
18    this.tail = newNode;
19    return this;
20  }
21
22  deleteHead() {
23    // If the list is empty we return null.
24    if (!this.head) return null;
25
26    // We dettach the head.
27    let deleted = this.head;
28
29    // We update this list head.
30    this.head = deleted.next;
31
32    // We clean the new head previous to null.
33    this.head.previous = null;
34
35    // We clean the deleted node before returning it.
36    deleted.next = null;
37
38    // We update this list length
39    this.length--;
40
41    return deleted;
42  }
43
44  fromArray(array) {
45    for (const e of array) {
46      this.append(e);
47    }
48    return this;
49  }
50
51  toString() {
52    const nodes = ['null'];
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}

1doublyLinkedList = new DeleteHeadDoublyLinkedList();
2doublyLinkedList.fromArray([0, 1, 2, 3, 4]);
3console.log(`Initial Doubly Linked List: ${doublyLinkedList.toString()}`);
4dettachedHead = doublyLinkedList.deleteHead();
5console.log(`Deleted Head: ${JSON.stringify(dettachedHead)}`);
6console.log(`Modified Doubly Linked List: ${doublyLinkedList.toString()}`);

1Initial Doubly Linked List: null<=>0<=>1<=>2<=>3<=>4<=>null
2Deleted Head: {"value":0,"previous":null,"next":null}
3Modified Doubly Linked List: null<=>1<=>2<=>3<=>4<=>null

doublyLinkedList.deleteTail

The user will get the node in the tail by deleting the tail. The linked list will have its current tail detached and replaced by its previous referenced node. Unlike Singly Linked Lists, here we don’t need to traverse the whole list making the tail deletion $O(1)$ runtime complex because we have a way to update the deleted tail previous node to make it the new tail.

Doubly Linked List Delete Tail 

 1class DeleteTailDoublyLinkedList {
 2  constructor() {
 3    this.head = null;
 4    this.tail = null;
 5    this.length = 0;
 6  }
 7
 8  append(value) {
 9    const newNode = new DoublyLinkedListNode(value);
10    this.length++;
11    if (!this.head) {
12      this.head = newNode;
13      this.tail = newNode;
14      return this;
15    }
16    this.tail.next = newNode;
17    newNode.previous = this.tail;
18    this.tail = newNode;
19    return this;
20  }
21
22  deleteTail() {
23    // If the list is empty we return null.
24    if (!this.head) return null;
25
26    // We dettach the tail.
27    let deleted = this.tail;
28
29    // We update this list tail.
30    this.tail = deleted.previous;
31
32    // We clean the new tail next to null.
33    this.tail.next = null;
34
35    // We clean the deleted node before returning it.
36    deleted.previous = null;
37    this.length--;
38
39    return deleted;
40  }
41
42  fromArray(array) {
43    for (const e of array) {
44      this.append(e);
45    }
46    return this;
47  }
48
49  toString() {
50    const nodes = ['null'];
51    let currentNode = this.head;
52    while (currentNode) {
53      nodes.push(currentNode.value);
54      currentNode = currentNode.next;
55    }
56    nodes.push('null');
57    return nodes.join('<=>');
58  }
59}

1doublyLinkedList = new DeleteTailDoublyLinkedList();
2doublyLinkedList.fromArray([0, 1, 2, 3]);
3console.log(`Doubly Linked List before deleting tail: ${doublyLinkedList.toString()}`);
4deleted = doublyLinkedList.deleteTail();
5console.log(`Deleted tail: ${JSON.stringify(deleted)}`);
6console.log(`Doubly Linked List after deleting tail: ${doublyLinkedList.toString()}`);

1Doubly Linked List before deleting tail: null<=>0<=>1<=>2<=>3<=>null
2Deleted tail: {"value":3,"previous":null,"next":null}
3Doubly Linked List after deleting tail: null<=>0<=>1<=>2<=>null

doublyLinkedList.delete

Delete deletes a node that matches the given value. First, it tries deleting the value from the head. If it hasn’t such value, it tries to delete it from the tail. This approach tries to keep the implementation in $O(1)$ runtime complexity. If neither the head nor tail has the value, it traverses the whole list from the beginning to lookup up the value and deletes it. This operation is $O(n)$ runtime complex for the worst case (i.e., the node is around the end of the linked list). The best case would be $O(1)$ runtime complex (i.e., the node is around the beginning of the linked list).

Doubly Linked List Delete 

 1class DeleteDoublyLinkedList {
 2  constructor() {
 3    this.head = null;
 4    this.tail = null;
 5    this.length = 0;
 6  }
 7
 8  append(value) {
 9    const newNode = new DoublyLinkedListNode(value);
10    this.length++;
11    if (!this.head) {
12      this.head = newNode;
13      this.tail = newNode;
14      return this;
15    }
16    this.tail.next = newNode;
17    newNode.previous = this.tail;
18    this.tail = newNode;
19    return this;
20  }
21
22  deleteHead() {
23    if (!this.head) return null;
24    let deleted = this.head;
25    this.head = deleted.next;
26    this.head.previous = null;
27    deleted.next = null;
28    this.length--;
29    return deleted;
30  }
31
32  deleteTail() {
33    if (!this.head) return null;
34    let deleted = this.tail;
35    this.tail = deleted.previous;
36    this.tail.next = null;
37    deleted.previous = null;
38    this.length--;
39    return deleted;
40  }
41
42  delete(value) {
43    // If the list is empty we return null.
44    if (!this.head) return null;
45
46    // If the head has this value, we delete the head.
47    if (this.head.value === value) return this.deleteHead();
48
49    // If the tail has this value, we delete the tail.
50    if (this.tail.value === value) return this.deleteTail();
51
52    // We delete the first occurrence of the value.
53    let currentNode = this.head;
54    while (currentNode) {
55      if (currentNode.value === value) {
56        currentNode.previous.next = currentNode.next;
57        currentNode.next.previous = currentNode.previous;
58        currentNode.next = null;
59        currentNode.previous = null;
60        this.length--;
61        return currentNode;
62      }
63      currentNode = currentNode.next;
64    }
65
66    return null;
67  }
68
69  fromArray(array) {
70    for (const e of array) {
71      this.append(e);
72    }
73    return this;
74  }
75
76  toString() {
77    const nodes = ['null'];
78    let currentNode = this.head;
79    while (currentNode) {
80      nodes.push(currentNode.value);
81      currentNode = currentNode.next;
82    }
83    nodes.push('null');
84    return nodes.join('<=>');
85  }
86}

 1doublyLinkedList = new DeleteDoublyLinkedList();
 2doublyLinkedList.fromArray([1, 2, 1, 3, 1]);
 3console.log(`Doubly Linked List before deletion: ${doublyLinkedList.toString()}`);
 4deleted = doublyLinkedList.delete(1);
 5console.log(`Deleted Node (The head): ${JSON.stringify(deleted)}`);
 6console.log(`Doubly Linked List after head deletion: ${doublyLinkedList.toString()}`);
 7deleted = doublyLinkedList.delete(1);
 8console.log(`Deleted Node (The tail): ${JSON.stringify(deleted)}`);
 9console.log(`Doubly Linked List after tail deletion: ${doublyLinkedList.toString()}`);
10deleted = doublyLinkedList.delete(1);
11console.log(`Deleted Node (internal): ${JSON.stringify(deleted)}`);
12console.log(`Doubly Linked List after internal deletion: ${doublyLinkedList.toString()}`);
13console.log(`Doubly Linked List length: ${doublyLinkedList.length}`);

1Doubly Linked List before deletion: null<=>1<=>2<=>1<=>3<=>1<=>null
2Deleted Node (The head): {"value":1,"previous":null,"next":null}
3Doubly Linked List after head deletion: null<=>2<=>1<=>3<=>1<=>null
4Deleted Node (The tail): {"value":1,"previous":null,"next":null}
5Doubly Linked List after tail deletion: null<=>2<=>1<=>3<=>null
6Deleted Node (internal): {"value":1,"previous":null,"next":null}
7Doubly Linked List after internal deletion: null<=>2<=>3<=>null
8Doubly Linked List length: 2

You could implement it another way: try to modify to delete the first value found, and while you do it, think of the implications of complexity runtime for the tail deletion case. For example, is it still $O(1)$ runtime complex?

Note: The actual implementation uses the internal compare function.

doublyLinkedList.deleteAll

Delete All deletes all the nodes that match the given value. This option returns the last node that matched the given value. All the nodes matching the given value are detached from the doubly linked list. This operation has $O(n)$ runtime complexity because we need to guarantee having traversed the whole linked list.

This approach eliminates first nodes at the head, then the tail, and then nodes between the head and tail.

Doubly Linked List Delete All 

 1class DeleteAllDoublyLinkedList {
 2  constructor() {
 3    this.head = null;
 4    this.tail = null;
 5    this.length = 0;
 6  }
 7
 8  append(value) {
 9    const newNode = new DoublyLinkedListNode(value);
10    this.length++;
11    if (!this.head) {
12      this.head = newNode;
13      this.tail = newNode;
14      return this;
15    }
16    this.tail.next = newNode;
17    newNode.previous = this.tail;
18    this.tail = newNode;
19    return this;
20  }
21
22  deleteHead() {
23    if (!this.head) return null;
24    let deleted = this.head;
25    this.head = deleted.next;
26    this.head.previous = null;
27    deleted.next = null;
28    this.length--;
29    return deleted;
30  }
31
32  deleteTail() {
33    if (!this.head) return null;
34    let deleted = this.tail;
35    this.tail = deleted.previous;
36    this.tail.next = null;
37    deleted.previous = null;
38    this.length--;
39    return deleted;
40  }
41
42  deleteAll(value) {
43    // If the list is empty we return null.
44    if (!this.head) return null;
45
46    let deleted = null;
47    // If the head has this value, we delete the head constantly.
48    while (this.head.value === value)
49      deleted = this.deleteHead();
50
51    // If the tail has this value, we delete the tail constantly.
52    while (this.tail.value === value)
53      deleted = this.deleteTail();
54
55    // We delete all the value ocurrences throughout the list.
56    let currentNode = this.head;
57    while (currentNode) {
58      if (currentNode.value === value) {
59        deleted = currentNode;
60        currentNode.previous.next = deleted.next;
61        currentNode.next.previous = deleted.previous;
62        currentNode = deleted.next;
63        deleted.next = null;
64        deleted.previous = null;
65        this.length--;
66      }
67      else currentNode = currentNode.next;
68    }
69
70    return deleted;
71  }
72
73  fromArray(array) {
74    for (const e of array) {
75      this.append(e);
76    }
77    return this;
78  }
79
80  toString() {
81    const nodes = ['null'];
82    let currentNode = this.head;
83    while (currentNode) {
84      nodes.push(currentNode.value);
85      currentNode = currentNode.next;
86    }
87    nodes.push('null');
88    return nodes.join('<=>');
89  }
90}

1doublyLinkedList = new DeleteAllDoublyLinkedList();
2doublyLinkedList.fromArray([1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 1, 1]);
3console.log(`Doubly Linked List before deleting ones: ${doublyLinkedList.toString()}`);
4deletedNode = doublyLinkedList.deleteAll(1);
5console.log(`Deleted node: ${JSON.stringify(deletedNode)}`);
6console.log(`Doubly Linked List after deleting ones: ${doublyLinkedList.toString()}`);

1Doubly Linked List before deleting ones: null<=>1<=>1<=>2<=>1<=>3<=>1<=>4<=>1<=>5<=>1<=>1<=>1<=>null
2Deleted node: {"value":1,"previous":null,"next":null}
3Doubly Linked List after deleting ones: null<=>2<=>3<=>4<=>5<=>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 ↩︎

←
Singly Linked List
Test Driven Development
→
back to top