Doubly Linked List

  • Data Structures
  • List
  • Code
  • Linked List
  • Doubly Linked List

A few weeks ago I did a post focused on that classic data structure, the Singly Linked List. Today I want to focus on a similar structure, the Doubly Linked List. If you haven't already, I highly recommend that you read the Singly Linked List post first. It probably isn't a surprise that the two structures are very similar, and many of the concepts carry over from one to the other.

A Doubly Linked List is a linear data structure that uses pointers to reference adjacent items within the list.

Structure and Terminology

A single data item in a Doubly Linked List is called a node. A node in a Doubly Linked List stores three things:

  1. A Value (I use val), which is the thing you want stored
  2. A Next reference (I use next), which is the pointer that references the next item in the list
  3. A Previous reference (I use prev), which is the pointer that references the previous item in the list

So where a node in a Singly Linked List only has a next pointer that points to the subsequent item in the list, an item in a Doubly Linked List will also have a prev or "previous" pointer, which points to the previous item in the list.

In practical terms, the addition of the previous pointer means that traversing the list in two directions is possible, making certain operations like .pop() or .reverse() a little bit easier. The trade-off is that each list has to store a new pointer, so more memory is needed, and when items are removed from or added to the list, this additional pointer needs to be taken into consideration.

This previous pointer is the main difference between a Singly and a Doubly Linked List. Everything else is otherwise the same. The list will always keep track of the head, which is the node that starts the Linked List.

A Doubly Linked List may also keep track of its tail - the last node in the list. I imagine this is more common with a Doubly Linked List than a Singly Linked List. Accessing items from the end of the list using the prev pointers provides some optimization that would otherwise be impossible without quick access to the tail. A Doubly Linked List might also keep track of the length - the number of items in the list. The Doubly Linked List I will implement in this post will keep track of these two things.

Here is a rough visualization of a Doubly Linked List:

1 <-> 10 <-> 100 <-> 1000

In this basic example, each number represents a node, and the arrows between the two number represent the next and prev pointers that link the two numbers. 1 would be the head of the list, its prev pointer would point to null (since there's no preceding item for the head) and its next pointer would point to 10. 10's prev would point to 1 and its next would point to 100. 100's prev would point to 10 and its next would point to 1000. 1000's prev would point to 100 and its next would point to null, making it the tail. This list's length would be 4, since there are four items in the list.

Practical Examples of a Doubly Linked List

So where might you encounter a Doubly Linked List? You could think of a basic implementation of your browser history as a sort of Doubly Linked List. The page you're currently on would be the tail, and as you navigate with the "Back" and "Forward" buttons, they present a sequential linked view of your browsing history that can be navigated in two directions.

The way I've laid this blog out could also be seen as a Doubly Linked List. For the newest blog post (which might be the head), you can click through to the next, "Older Post", and then for each older blog post you can navigate both to the previous "Newer Post" or the next "Older Post" until you get to my oldest blog post (not recommended reading), which would be the tail of the list.

Big O of a Doubly Linked List

OperationComplexity
InsertionO(1)
RemovalO(1)
SearchingO(n)
AccessO(n)

Insertion: Insertion is where Linked Lists excel, whether it's a Singly or Doubly Linked List. Unlike an Array, which has to re-index everything and can be extremely inefficient when inserting at the beginning of the Array, inserting at the beginning of a Linked List (or really anywhere) is just a matter of updating a pointer or two.

Removal: Removal in a Doubly Linked List is always constant, which is not the case for a Singly Linked List, especially at the end of the Singly Linked List. Remember that for a Singly Linked List it has to iterate all the way from the beginning to get to the end. With a Doubly Linked List, you can start from the end and easily get to the item you are removing.

Searching: Technically Searching is O(n/2) since we optimized the .get() operation to be able to start from both the head and the tail, but that's still O(n).

Access: Same as searching.

Doubly Linked List Implementation

Here's the full implementation for future reference. Sections below will detail each method.

class Node {  constructor(val) {    this.val = val;    this.next = null;    this.prev = null;  }}
class DoublyLinkedList {  constructor() {    this.head = null;    this.tail = null;    this.length = 0;  }  get(index) {    if (index < 0 || index >= this.length) {      return null;    }    var middle = Math.ceil(this.length / 2);    var counter;    var current;    if (index <= middle) {      counter = 0;      current = this.head;      while (counter < index) {        current = current.next;        counter++;      }      return current;    } else {      counter = this.length - 1;      current = this.tail;      while (counter > index) {        current = current.prev;        counter--;      }      return current;    }  }  insert(index, val) {    if (index < 0 || index > this.length) {      return false;    }    if (index === this.length) {      return !!this.push(val);    }    if (index === 0) {      return !!this.unshift(val);    }    var newNode = new Node(val);    var prev = this.get(index - 1);    var temp = prev.next;    prev.next = newNode;    newNode.prev = prev;    newNode.next = temp;    temp.prev = newNode;    this.length++;    return true;  }  pop() {    if (!this.head) {      return undefined;    }    var currentTail = this.tail;    if (this.length === 1) {      this.head = null;      this.tail = null;    } else {      this.tail = currentTail.prev;      this.tail.next = null;      currentTail.prev = null;    }    this.length--;    return currentTail;  }  push(val) {    var newTail = new Node(val);    if (!this.head) {      this.head = newTail;      this.tail = this.head;    } else {      this.tail.next = newTail;      newTail.prev = this.tail;      this.tail = newTail;    }    this.length++;    return this;  }  remove(index) {    if (index < 0 || index >= this.length) {      return undefined;    }    if (index === 0) {      return this.shift();    }    if (index === this.length - 1) {      return this.pop();    }    var prev = this.get(index - 1);    var removedNode = prev.next;    prev.next = removedNode.next;    removedNode.next.prev = prev;    removedNode.prev = null;    removedNode.next = null;    this.length--;    return removedNode;  }  reverse() {    var node = this.head;    this.head = this.tail;    this.tail = node;    var next;    for (var i = 0; i < this.length; i++) {      next = node.next;      node.next = node.prev;      node.prev = next;      node = next;    }    return this;  }  set(index, val) {    var foundNode = this.get(index);    if (foundNode) {      foundNode.val = val;      return true;    }    return false;  }  shift() {    if (!this.head) {      return undefined;    }    var currentHead = this.head;    if (this.length === 1) {      this.head = null;      this.tail = null;    } else {      this.head = currentHead.next;      this.head.prev = null;      currentHead.next = null;    }    this.length--;    return currentHead;  }  unshift(val) {    if (!this.head) {      this.push(val);    } else {      var newHead = new Node(val);      newHead.next = this.head;      this.head.prev = newHead;      this.head = newHead;      this.length++;      return this;    }  }}

Node Class

Each item within the Linked List is called a node. Any time we add a node into the Linked List, we'll do it using a Node Class. This class accepts a value, val, and also has next and prev properties. By default next and prev will be assigned the value of null, but we'll commonly be assigning these properties to point to other nodes in the list. next will point to the next item in the list, in the direction of the tail, and prev will point to the previous item in the list, in the direction of the head. The prev reference will remain null for the head, and the next reference will remain null for the tail.

class Node {  constructor(val) {    this.val = val;    this.next = null;    this.prev = null;  }}

Doubly Linked List Class

We'll also use a Doubly Linked List Class to initialize the list itself. We're starting here just with its constructor, but we'll add in all of the needed methods as we go. On initialization, an empty Doubly Linked List will have a head set to null, a tail also set to null, and a length set to 0.

class DoublyLinkedList {  constructor() {    this.head = null;    this.tail = null;    this.length = 0;  }}

Methods and Operations

.push()

The first method we'll introduce is the .push() method, which adds a new node to the end of the linked list, in practical terms creating a new tail. This method accepts a value, val, that we want to attach to the end of the list.

Here are the steps we take to create the .push() method:

  1. Create a new node with the value val. I'll store this in a variable called newTail
  2. Check if the list is empty. We'll know we have an empty list if the list has no head
  3. If the list is empty:
    1. Assign the new node as the head
    2. Assign the tail to also equal the head
  4. If the list isn't empty:
    1. Set the current tail's next to equal the new node
    2. Set the new node's prev to equal the current tail
    3. Assign the new node as the tail
  5. Increment the length by 1
  6. Return the list

.push() Implementation

push(val) {  var newTail = new Node(val);  if (!this.head) {    this.head = newTail;    this.tail = this.head;  } else {    this.tail.next = newTail;    newTail.prev = this.tail;    this.tail = newTail;  }  this.length++;  return this;}

.pop()

Now let's look at the .pop() method, which removes the last item from the list. For a Singly Linked List, this method was made more complicated by the fact that in order to reassign the new tail to be the item before the current tail, we needed to iterate all the way up through the list.

This is significantly easier in a Doubly Linked List now that the current tail has a prev reference that we can use.

  1. Return undefined if the list is empty (again, if there's no head then it's an empty list)
  2. Store the current tail into a variable, I'll call it currentTail
  3. Check whether the list only has one item
  4. If the list only has one item:
    1. Set the head to equal null
    2. Set the tail to equal null
  5. Otherwise, if there is more than one item in the list
    1. Set the tail to be currentTail's prev
    2. Set the newly-set tail's next to null (breaking the reference to currentTail)
    3. Set currentTail's prev to null
  6. Decrement the length by 1
  7. Finally, return the node that we have removed from the list. Remember that this old tail is stored in the currentTail variable

.pop() Implementation

pop() {  if (!this.head) {    return undefined;  }  var currentTail = this.tail;  if (this.length === 1) {    this.head = null;    this.tail = null;  } else {    this.tail = currentTail.prev;    this.tail.next = null;    currentTail.prev = null;  }  this.length--;  return currentTail;}

.unshift()

Now we'll look at the .unshift() method, which adds a new value, val, to the beginning of the list.

  1. If the list is empty, simply .push(val). This allows us to reuse some logic we've already written
  2. Otherwise:
    1. Create a new node with the value val
    2. Set the new node's next to point to the list's current head
    3. Set the current head's prev to point to the new node
    4. Assign the new node as the head
    5. Increment the length by 1
    6. Return the list

.unshift() Implementation

unshift(val) {  if (!this.head) {    this.push(val);  } else {    var newHead = new Node(val);    newHead.next = this.head;    this.head.prev = newHead;    this.head = newHead;    this.length++;    return this;  }}

.shift()

Now let's remove an item from the beginning of the list with a method called .shift().

  1. If the list is empty return undefined
  2. Store the current head into a variable, I'll use currentHead
  3. Check whether there is only one item in the list.
  4. If there's only one item in the list:
    1. Set the head to null
    2. Set the tail to null
  5. If there's more than one item in the list:
    1. Set the head to be currentHead's next
    2. Set the new head's prev to be null
    3. Set currentHead's next to be null (breaking the reference to the new head)
  6. Decrement the length by 1
  7. Return the old head that we have removed, which is stored in currentHead

.shift() Implementation

shift() {  if (!this.head) {    return undefined;  }  var currentHead = this.head;  if (this.length === 1) {    this.head = null;    this.tail = null;  } else {    this.head = currentHead.next;    this.head.prev = null;    currentHead.next = null;  }  this.length--;  return currentHead;}

.get()

.get() is a handy method that can retrieve a node at a specific index within the list. We'll be using it below in the .set() and .insert() methods.

.get() accepts an index, which corresponds to a place within the list. Like an array, the first item in the Linked List is at index 0, the second item is at index 1, the third item is at index 2, and so on.

A big difference in this method between a Singly Linked List and a Doubly Linked List is that a Doubly Linked List, with its tail and prev pointers, allows us to start at the end of a list and move backwards, rather than only being able to start at the beginning of the list and move forwards. This achieves some optimization as we can cut down the necessary steps to access data by half. I'll walk through how this gets accomplished.

  1. Check to make sure the index is valid. If the index is invalid, return undefined. The index is invalid if:
    1. It is a negative value
    2. It is greater than or equal to the length of the list. If a list is 3 items long, then the highest index is 2. If the list is 100 items long, then the highest index is 99
  2. We need to find the index of the middle point of the list, and store this value in a variable called middle. Using Math.ceil(this.length / 2), we divide the length property of the list by 2, and Math.ceil will round up if we wind up with a decimal (i.e., if length is 5, the middle will be 3).
  3. We also need to create variables called counter and current that will be used for iteration. We'll leave these variables declared but not assigned any value for now.
  4. Now let's check whether index is less than or equal to middle
  5. If index is less than or equal to middle, we will iterate up from the beginning of the list:
    1. Set counter to equal 0
    2. Set current to equal the list's head
    3. Begin a while Loop that checks if counter is still less than index. If so:
      1. Set current equal to current.next
      2. Increment counter by 1
      • This loop stops running once counter is equal to index, meaning current has landed on the item we are looking for
    4. return current
  6. If index is greater than middle, we will iterate down starting from the end of the list:
    1. Set counter equal to this.length - 1 (i.e., the index of the last item in the list)
    2. Set current equal to the list's tail
    3. Begin a while Loop that checks if counter is still greater than index. If so:
      1. Set current equal to current.prev
      2. Decrement counter by 1
      • This loop stops running once counter is equal to index, meaning current has landed on the item we are looking for
    4. return current

.get() Implementation

get(index) {  if (index < 0 || index >= this.length) {    return null;  }  var middle = Math.ceil(this.length / 2);  var counter;  var current;  if (index <= middle) {    counter = 0;    current = this.head;    while (counter < index) {      current = current.next;      counter++;    }    return current;  } else {    counter = this.length - 1;    current = this.tail;    while (counter > index) {      current = current.prev;      counter--;    }    return current;  }}

.set()

.set() accepts an index and a value, val, and changes the value of the node at that index to val. We once again need to make sure that the index is valid, and then iterate through the list to the correct item. But luckily for us, the .get() method takes care of that logic for us.

  1. Use the .get() method to retrieve the node at the provided index. Store this in a variable named foundNode
    1. .get() will return undefined for us if it's an invalid index
    2. .get() will also do all of the (optimized!) iteration for us
  2. If .get() returns our foundNode:
    1. Set foundNode's val to the val that was passed to the .set() method
    2. Return true
  3. Otherwise, return false

.set() Implementation

set(index, val) {  var foundNode = this.get(index);  if (foundNode) {    foundNode.val = val;    return true;  }  return false;}

.insert()

The next method we'll work on is .insert(), which takes an index and a value, val. This method will insert val into the list at the desired index, shifting the item that was previously at that index later into the list. This method will return false if the index passed is invalid, or true if the index is valid and the insertion is done successfully.

  1. Check to make sure the index is a valid number. This is the same as above. Return false if it is an invalid index.
  2. If the index is equal to the list's length property, then we can just use the .push() method to add val as the new tail
    • We can use a !! double bang operator to return true after using the .push() method
  3. If index is 0, then we can just use the .unshift() method to add val as the new head
    • We can use a !! double bang operator to return true after using the .unshift() method
  4. If we've gotten this far, then the index is somewhere in the middle of the list and we can't just rely on the other methods we've written so far
  5. Create a new node with the value val, and assign it to a variable named newNode
  6. Retrieve the node right before the item currently located at index, and assign it to a variable named prev. We can use the .get() method and pass it index - 1 to achieve this
  7. Retrieve the node currently at located at index (same as prev.next), and assign it to a variable named temp
  8. Set prev's next pointer to reference newNode
  9. Set newNode's prev pointer to reference prev
  10. Set newNode's next pointer to reference temp
  11. Set temp's prev pointer to reference newNode
  12. Increment length by 1
  13. Return true

.insert() Implementation

insert(index, val) {  if (index < 0 || index > this.length) {    return false;  }  if (index === this.length) {    return !!this.push(val);  }  if (index === 0) {    return !!this.unshift(val);  }  var newNode = new Node(val);  var prev = this.get(index - 1);  var temp = prev.next;  prev.next = newNode;  newNode.prev = prev;  newNode.next = temp;  temp.prev = newNode;  this.length++;  return true;}

.remove()

Now let's look at the .remove() method, which accepts an index, removes the item at that index from the list, and returns the removed node. Fortunately this logic is very similar to .insert().

  1. Check if it's a valid index. If it's not, return undefined
  2. If index is 0, we can just use the .shift() method to remove the current head
  3. If the index is equal to length - 1, we can just use the .pop() method to remove the current tail
  4. Otherwise we need to go about removing a node from the middle of the list
  5. Retrieve the node right before the item that we want to remove, and assign it to a variable named prev. We can use the .get() method and pass it index - 1 to achieve this
  6. Retrieve the node currently at located at index (same as prev.next), and assign it to a variable named removedNode
  7. Set prev's next pointer to refer to removedNode.next
  8. Set removedNode.next.prev to equal prev. This is a little confusing, but we're basically assign the item after removedNode's prev to point to the item before removedNode
  9. Set removedNode's prev to null
    • This removes one of the connections from the removed node to the rest of the list
  10. Set removedNode's next to null
    • This removes the other connection from the removed node to the rest of the list. This and Step 9 ensure that removedNode isn't a false head or false tail that connects to the list
  11. Decrement length by 1
  12. Return the node we removed, currently stored in the removedNode variable

.remove() Implementation

remove(index) {  if (index < 0 || index >= this.length) {    return undefined;  }  if (index === 0) {    return this.shift();  }  if (index === this.length - 1) {    return this.pop();  }  var prev = this.get(index - 1);  var removedNode = prev.next;  prev.next = removedNode.next;  removedNode.next.prev = prev;  removedNode.prev = null;  removedNode.next = null;  this.length--;  return removedNode;}

.reverse()

The last method we'll look at today is .reverse() that reverses the Doubly Linked List in place. This is much, much easier than reversing a Singly Linked List in place (something that took up half off the Singly Linked List post, and that I later broke out into its own blog post to answer a LeetCode question).

.reverse() Implementation

  1. Swap the head and the tail:
    1. Store head in a temporary node variable
    2. Assign the head to equal the tail
    3. Assign the tail to equal the temporary node variable
  2. Create a next variable, but do not assign anything to it
  3. Loop through the length of the list. Within this loop:
    1. Set the next variable equal to the temporary node's next value
    2. Set the temporary node's next to equal its own prev reference
    3. Set the temporary node's prev reference to point to next
    4. Assign the temporary node to equal next
  4. After the loop has finished, return the list, which will now be reversed

The logic here is pretty much identical to what I've written out twice now in step by step breakdowns (here and here). The only difference is that each node has a prev reference we use instead of a prev variable that we created elsewhere. Hopefully it suffices to point you to those other two previous blog posts that go into step by step detail at each iteration of the loop, rather than basically rewrite that all out here.

reverse() {  var node = this.head;  this.head = this.tail;  this.tail = node;  var next;  for (var i = 0; i < this.length; i++) {    next = node.next;    node.next = node.prev;    node.prev = next;    node = next;  }  return this;}