Understanding Doubly Linked Lists in JavaScript

Hello! Today, let’s explore doubly linked lists in JavaScript. We have already covered the singly linked list in our previous article, you know we store data in a linked way, with each node holding a value and a pointer to the next node. With doubly linked lists, we add a pointer to the previous node too. This gives us more flexibility, though it uses a bit more memory.

Doubly Linked List Basics In a singly linked list, each node needed eight memory slots. For a doubly linked list, we need to store three things for each node: the data, the memory address of the previous node, and the memory address of the next node. So now, each node needs four memory slots, making it twelve slots for each element.

// Doubly Linked List Node Structure
class Node {
  constructor(data) {
    this.data = data;      // Data stored in the node
    this.prev = null;      // Reference to the previous node
    this.next = null;      // Reference to the next node
  }
}

Operations on doubly linked lists

Insertion in a doubly linked list

Insertion in a doubly linked list involves updating both the “next” and “previous” pointers of neighboring nodes. Let’s say we want to add a new node with the value 5 at the beginning of the list.

Here’s the process:

1. Create a new node with the value 5.
2. Set the “next” pointer of the new node to point to the current head (let’s call it “node1”).
3. Set the “prev” pointer of the current head (“node1”) to point back to the new node.
4. Update the head pointer to point to the new node, making it the new head.

After these steps, the new node 5 becomes the head of the list, and it points to the previous head node (“node1”). The previous head (“node1”) now has its “prev” pointer pointing back to the new head node 5.

Here’s the JavaScript code:

// Creating a new node with value 5
let newNode = new Node(5);

// Updating pointers
newNode.next = head; // Setting new node's next to current head
head.prev = newNode; // Setting previous head's prev to new node
head = newNode; // Updating head to new node

// Node class definition
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

Now, the doubly linked list looks like this:

head -> 5 <-> node1 <-> node2 <-> ... <-> lastNode

Here, each arrow represents a pointer. The new node 5 is the head, and it points to the previous head node (node1). Node1’s prev pointer points back to 5, and 5’s next pointer points to node1. The rest of the list remains connected as before.

Deletion in a doubly linked list

Deletion in a doubly linked list involves updating the pointers of neighboring nodes to bypass the node being deleted. Let’s say we want to delete a node with the value 2 from the list.

Here’s the process:

1. Find the node with the value 2 that we want to delete.
2. Update the “next” pointer of the node before (let’s call it “prevNode”) to skip the node to be deleted.
3. Update the “prev” pointer of the node after (let’s call it “nextNode”) to skip the node to be deleted.
4. Optionally, remove any references to the node to be deleted so it can be garbage collected.

Here’s the JavaScript code:

// Function to delete a node with a specific value
function deleteNode(value) {
  let current = head;

  // Traverse the list to find the node to delete
  while (current != null) {
    if (current.data === value) {
      let prevNode = current.prev;
      let nextNode = current.next;

      // Update pointers to skip the node to be deleted
      if (prevNode !== null) {
        prevNode.next = nextNode;
      }
      if (nextNode !== null) {
        nextNode.prev = prevNode;
      }

      // Optionally, remove references to the deleted node
      current.prev = null;
      current.next = null;

      // If the node to be deleted is the head, update head
      if (current === head) {
        head = nextNode;
      }

      break; // Exit the loop once deletion is done
    }
    current = current.next;
  }
}

// Assuming head points to the first node of the list

// Deleting a node with value 2
deleteNode(2);

After this deletion operation, the node with value 2 is removed from the list, and the neighboring nodes are properly connected to maintain the doubly linked list structure.

Here’s how the list might look after deletion:

head -> 5 <-> node1 <-> node3 <-> ... <-> lastNode

Here, each arrow represents a pointer. Node 5 is the head, and it points to node1. Node1’s next pointer points to node3, and node3’s prev pointer points back to node1. The node with value 2 has been effectively removed from the list.

Complexity Analysis of doubly linked list

Complexity Analysis The complexities for operations on doubly linked lists are similar to singly linked lists, with slight adjustments for the prev pointer updates.

• Insertion and Deletion at Beginning/End: O(1)
• Insertion and Deletion in Middle: O(n)

The major advantage of doubly linked lists is the ability to move both forwards and backwards, which can be useful in certain situations.

Conclusion

I hope this overview helps in understanding doubly linked lists in JavaScript. Remember, drawing out the memory layout can greatly aid in visualizing how the pointers work. Stay tuned for more discussions on data structures in our next lectures.

Thanks for reading, and see you in the next one! Happy Coding 🙂