Doubly Linked List

Doubly linked lists are just like linked lists. However instead of having a single link pointer pointing to the next element, they have two link pointers - one pointing to the next element, another pointing to the previous element.

What’s the advantage, you might ask and when compared to the Linked List, why is the backward link needed? To understand that, let’ take an example of what the problem is with Linked List with an example:

The problem with Linked Lists

Let’s think of a scenario (as a question) and see what Linked Lists lack:

Question

You have a Linked List of 100 integers from 1 - 100. All the items in this linked list are unique but are not sorted in any order. You have to find out the node containing the number 50 and remove the node from the list which points to this. You can safely assume that the first node of this list does not contain the value of 50.

Solution

If it is a (singly) linked list we are talking about, then the best way to get this done is to make two passes over the list.

First Pass

  1. Create a counter (let’s call it element_found_at) to count the number of elements we have visited.
  2. Start with the first element and set the counter to 1. Now we start a loop (from step 3) till we find 50 in the list.
  3. Go to the next node using the next-node pointer and increment the counter to 1.
  4. Check if the current element is 50. If yes, then exit the loop. If no, then go to step 3.

At the end of the first pass, we will have the position of the node containing 50 in this list. For this exercise, let’s assume that the value of element_found_at is 68.

Second Pass

In the second pass, we will iterate over the list (using next-node pointers) and remove the element at the position element_found_at - 1 in the list. Something like this:

  1. Created a counter (let’s call it current_node_number) to keep track of the number of nodes we have visited.
  2. Start a loop (from step 3) till we reach node number element_found_at - 1 (67).
  3. Visit next node using next-node pointer and increment the current_node_number by 1.
  4. Check if value of current_node_number is equal to element_found_at - 1 (67).
  5. If yes, then delete the current node. If no, then go to step 3.

What’s bad about this?

What’s bad is that if you want to go back from any node in a (singly) linked list, you have to maintain a counter for counting the nodes visited and then you have to iterate over the list at least one more time. Depending on how complicated a problem we are trying to solve, that might mean a lot of iterations over the same list.

For example: You have a linked list of 1000 elements and you are asked to remove the last 10 elements which contain an odd integer. In the worst case you will have to iterate through nearly 10000 (9955 exactly) elements.

How do Doubly Linked lists solve this problem?

Since doubly linked lists have a previous-node pointer too, you can go back one step without having to iterate over the entire list again. For our given problem above, the solution would be done in a single pass. Something like this:

  1. Start with the first element and start a loop (from step 2) till we find 50 in the list.
  2. Go to the next element using the next-node pointer.
  3. Check if the current element is 50.
  4. If yes, then go back one node (using the previous-node pointer), delete the node and exit the loop. If no, then go to step 2.

There are two significant advantages to this:

  1. You do not have to make two passes.
  2. You do not have to create counters and update them with each node visit.

Differences between singly and doubly linked lists

Structure

Structurally, a doubly linked list node contains 2 pointers:

  1. The next-node pointer: this one is the same as the one we use in singly linked lists. It points to the next node in the doubly linked list.
  2. There is a previous-node pointer: this one points to the previous element in the doubly linked list.

Operation

  1. Doubly Linked Lists work exactly the same way as Linked List when you are using the next-node pointer. You can move to the next node in the list using the next-node pointer.
  2. You can go to the previous node using the previous-node pointer.
  3. When adding a new element at position n, you have to update:
    • The next-node pointer in the node at n position should point to the node you are inserting.
    • The previous-node pointer in the node at n+1 position should point to the node node you are inserting.
    • The next-node pointer in the node you are inserting should point to the node at n+1 position while the previous-node pointer should point at the node currently at n position.

When to use Doubly Linked List?

You can use a Doubly Linked List at any place where you can/should use (singly) Linked Lists. However, if your program does not need to traverse the elements in backward fashion, you should probably use (singly) Linked Lists because you will save some memory from not having to store the previous-node pointers in each node.

The reasons and places where you should use Doubly Linked Lists over arrays are the same as reasons and places you should use Linked Lists.

Updated: