Doubly Linked List

Category: Data Structures
Tags: #datastructures#linkedlist

A Doubly Linked List is a linear data structure which collectively represents a sequence of data in which each node has three parts. In this tutorial, we will learn about the implementation of a doubly linked list and various operations on it like insertion, deletion and traversal of a Doubly Linked List and it's advantages and disadvantages over Singly Linked List.

Implementation of Linked List (Singly Linked List)

Table of contents

A Doubly Linked List is a collection of nodes in which each node has three parts i.e, pointer to previous node, data and pointer to next node and last node points to null.

Linked List example

Declaration of type node for Doubly Linked List

We have to create a data structure or Node which contains three part i.e, first part contains address of previous node, second part contains data of the node and third node contains address of next pointer. We can create this by using user defined data type (depends on the programming language used).

Linked List node

Python
class Node:
    def __init__(self, data):
        self.prev = None
        self.data = data
        self.next = None
JavaScript
class Node {
  constructor(data) {
    this.prev = null;
    this.data = data;
    this.next = null;
  }
}

Traversing the Doubly Linked List

Traversing means visiting all the node once i.e, we want to read all the data available in the doubly linked list. We can do so by visiting all the nodes one by one and reading the data available in each node.

Simply, use a temporary variable and initialize it with the head node so that we can start with the begining of the list and then go through all the nodes one by one till the last node is reached. And we can get the last node by checking the next value of node i.e., if next value of node is null then this is the end of node.

Linked List node

Python
def traverse(self):
    if self.head:
        temp = self.head
        while temp:
            print(temp.data)
            temp = temp.next
    else:
        print(None)
JavaScript
traverse() {
  if (this.head) {
    let temp = this.head;
    while (temp) {
      console.log(temp.data);
      temp = temp.next;
    }
  } else {
    console.log(null);
  }
}

Reverse traversing of the Doubly Linked List

Reverse traversing means visiting all the node once from the backward direction i.e, we want to read all the data available in the doubly linked list from the tail. We can do so by visiting all the nodes one by one and reading the data available in each node.

Simply, use a temporary variable and initialize it with the tail node so that we can start with the end of the list and then go through all the nodes one by one till the first node is reached. And we can get the first node by checking the next value of node i.e., if next value of node is null then this is the begining of node.

Linked List node

Python
def reverse_traverse(self):
    if self.tail:
        temp = self.tail
        while temp:
            print(temp.data)
            temp = temp.prev
    else:
        print(None)
JavaScript
reverseTraverse() {
  if (this.tail) {
    let temp = this.tail;
    while (temp) {
      console.log(temp.data);
      temp = temp.prev;
    }
  } else {
    console.log(null);
  }
}

Length of a Doubly Linked List

To find length of a linked list we can simply use a temporary variable and initialize it by assigning the head node. Now, move it to every node one by one and increase the counter variable.

Linked List node

Python
def length(self):
    temp = self.head
    count = 0
    while temp:
        count += 1
        temp = temp.next
    return count
JavaScript
length() {
  let temp = this.head;
  let count = 0;
  while (temp) {
    count++;
    temp = temp.next;
  }
  return count;
}

Insertion in a Doubly Linked List

Insertion in a Linked List can be done in following three ways:

  1. Insertion at the begining
  2. Insertion at the end
  3. Insertion at given position

Insertion at the begining of the Doubly Linked List

While inserting a node at the begining position, two situation may arise:

  1. Insertion when Doubly Linked List is emtpy: In this case we can simply create a new node and put the value in data part, null into the next part and previous part (which is already done in Class Node constructor) then assign it to the head.
  2. Insertion when Doubly Linked List is not empty: In this case create a new node, add value into the data part and assign the node pointed by the head (current starting node) to next of newly created node and then head will now point to new node and null into the previous part (which is already done in Class Node constructor).

Linked List node

Python
def insert_at_start(self, data):
    new_node = Node(data)

    if not self.head:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
JavaScript
insertAtStart(data) {
  const newNode = new Node(data);

  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    newNode.next = this.head;
    this.head.prev = newNode;
    this.head = newNode;
  }
}

Insertion at the end of the Doubly Linked List

While inserting a node at the end position, two situation may arise:

  1. Insertion when Doubly Linked List is emtpy: In this case we can simply create a new node and put the value in data part, null into the next part and previous part (which is already done in Class Node constructor) then assign it to the head.
  2. Insertion when Doubly Linked List is not empty: In this case create a new node, and then assign it to the next part of tail node then tail should point to the newly created node.

Linked List node

Python
def insert_at_end(self, data):
    new_node = Node(data)

    if not self.head:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node
JavaScript
insertAtEnd(data) {
  const newNode = new Node(data);

  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
  }
}

Insertion at given position in the Doubly Linked List

While inserting at any given position following 3 situation may arise based on user input:

  1. Insertion at the begining: In this case, simply call the function used to insert at begining.
  2. Insertion at the end: In this case, simply call the function used to insert at the end.
  3. Insertion at any random position: In this case, use a temporary variable and initialize with the head pointer traverse till the given position - 1 and then insert the new node by adjusting the previous and next pointer.

Linked List node

Python
def insert_at_position(self, pos, data):
    new_node = Node(data)

    if pos < 0 or pos > self.length():
        raise Exception('Enter a valid postion')
    else:
        if pos == 0:
            self.insert_at_start(data)
        elif pos == self.length()-1:
            self.insert_at_end(data)
        else:
            temp = self.head
            for _ in range(pos-1):
                temp = temp.next
            new_node.next = temp.next
            temp.next = new_node
            new_node.prev = temp
JavaScript
insertAtPosition(pos, data) {
  const newNode = new Node(data);

  if (pos < 0 || pos > this.length()) {
    throw "Enter a valid position";
  } else {
    if (pos == 0) {
      this.insertAtStart(data);
    } else if (pos == this.length() - 1) {
      this.insertAtEnd(data);
    } else {
      let temp = this.head;
      for (let i = 0; i < pos - 1; i++) {
        temp = temp.next;
      }
      newNode.next = temp.next;
      temp.next = newNode;
      newNode.prev = temp;
    }
  }
}

Deletion in a Doubly Linked List

Same as insertion deletion in a Linked List can be done in 3 ways:

  1. Deletion from the begining of the Doubly Linked List
  2. Deletion from the end of the Doubly Linked List
  3. Deletion from given position in the Doubly Linked List

Deletion from the begining of the Doubly Linked List

While deleting a node at the from begining, two situation may arise:

  • Deletion when Linked List is emtpy: When Linked List is empty throw an error that Linked List is empty.
  • Deletion when Linked List is not empty: Again, two cases may arise if linked list is not empty
    1. If only one node is present: In this case, delete that node and set head and tail as null
    2. If multiple nodes are present: Then shift the head pointer to next node and set null to the new previous part of new head node.

For languages like Python, Java etc. which have in built mechanism for garbage collection, can remove the deleted node itself but in case of languages like C or C++ we have to point that node and remove it manually.

Linked List node

Python
def delete_from_start(self):
    if self.head:
        if self.head is self.tail:
            data = self.head.data
            self.head = self.tail = None
        else:
            data = self.head.data
            self.head = self.head.next
            self.head.prev = None
        return data
    else:
        raise Exception('Empty linked list')
JavaScript
deleteFromStart() {
  if (this.head) {
    let data;
    if (this.head === this.tail) {
      data = this.head.data;
      this.head = this.tail = null;
    } else {
      data = this.head.data;
      this.head = this.head.next;
      this.head.prev = null;
    }
    return data;
  } else {
    throw "Empty Linked List";
  }
}

Deletion from the end of the Doubly Linked List

While deleting a node at the from the end, two situation may arise:

  • Deletion when Linked List is emtpy: Again two cases may arise if linked list is not empty
  • Deletion when Linked List is not empty: Again two cases may arise if linked list is not empty
    1. If only one node is present: In this case, delete that node and set head and tail as null
    2. If multiple nodes are present: Then shift the tail node to the previous node and set null to the next part of new tail node.

For languages like Python, Java etc. which have in built mechanism for garbage collection, can remove the deleted node itself but in case of languages like C or C++ we have to point that node and remove it manually.

Linked List node

Python
def delete_from_end(self):
    if self.head:
        if self.head is self.tail:
            data = self.head.data
            self.head = self.tail = None
        else:
            data = self.tail.data
            self.tail = self.tail.prev
            self.tail.next = None
        return data
    else:
        raise Exception('Empty linked list')
JavaScript
deleteFromEnd() {
  if (this.head) {
    let data;
    if (this.head === this.tail) {
      data = this.head.data;
      this.head = this.tail = null;
    } else {
      data = this.tail.data;
      this.tail = this.tail.prev;
      this.tail.next = null;
    }
    return data;
  } else {
    throw "Empty Linked List";
  }
}

Deletion from given position in the Doubly Linked List

While deleting at any given position following 3 situation may arise based on user input:

  1. Deletion from the begining: In this case, simply call the function used to delete from begining.
  2. Deletion from the end: In this case, simply call the function used to delete from the end.
  3. Deletion from any random position: In this case, use a temporary variable and initialize with the head pointer and traverse till the given node is reached by the given position and adjust the next and previous pointers of the nodes situated after and before this node. For languages like Python, Java etc. which have in built mechanism for garbage collection, can remove the deleted node itself but in case of languages like C or C++ we have to point that node and remove it manually.

Linked List node

Python
def delete_at_position(self, pos):
    if pos < 0 or pos >= self.length():
        raise Exception('Enter a valid postion')
    else:
        if pos == 0:
            return self.delete_from_start()
        elif pos == self.length()-1:
            return self.delete_from_end()
        else:
            temp = self.head
            for _ in range(pos):
                temp = temp.next
            data = temp.data
            prev_node = temp.prev
            prev_node.next = temp.next
            temp.next.prev = prev_node
            return data
JavaScript
deleteAtPosition(pos) {
  if (pos < 0 || pos >= this.length()) {
    throw "Enter a valid position";
  } else {
    if (pos == 0) {
      return this.deleteFromStart();
    } else if (pos === this.length() - 1) {
      return this.deleteFromEnd();
    } else {
      let temp = this.head;
      for (let i = 0; i < pos; i++) {
        temp = temp.next;
      }
      const data = temp.data;
      const prevNode = temp.prev;
      prevNode.next = temp.next;
      temp.next.prev = prevNode;
      return data;
    }
  }
}

Implementation of Doubly Linked List

Implementation of singly linked list linked list with all the function combined with output.

Python
class Node:
    def __init__(self, data):
        self.prev = None
        self.data = data
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_at_start(self, data):
        new_node = Node(data)

        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)

        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def insert_at_position(self, pos, data):
        new_node = Node(data)

        if pos < 0 or pos > self.length():
            raise Exception('Enter a valid postion')
        else:
            if pos == 0:
                self.insert_at_start(data)
            elif pos == self.length()-1:
                self.insert_at_end(data)
            else:
                temp = self.head
                for _ in range(pos-1):
                    temp = temp.next
                new_node.next = temp.next
                temp.next = new_node
                new_node.prev = temp

    def delete_from_start(self):
        if self.head:
            if self.head is self.tail:
                data = self.head.data
                self.head = self.tail = None
            else:
                data = self.head.data
                self.head = self.head.next
                self.head.prev = None
            return data
        else:
            raise Exception('Empty linked list')

    def delete_from_end(self):
        if self.head:
            if self.head is self.tail:
                data = self.head.data
                self.head = self.tail = None
            else:
                data = self.tail.data
                self.tail = self.tail.prev
                self.tail.next = None
            return data
        else:
            raise Exception('Empty linked list')

    def delete_at_position(self, pos):
        if pos < 0 or pos >= self.length():
            raise Exception('Enter a valid postion')
        else:
            if pos == 0:
                return self.delete_from_start()
            elif pos == self.length()-1:
                return self.delete_from_end()
            else:
                temp = self.head
                for _ in range(pos):
                    temp = temp.next
                data = temp.data
                prev_node = temp.prev
                prev_node.next = temp.next
                temp.next.prev = prev_node
                return data

    def get_first(self):
        if self.head:
            return self.head.data
        else:
            raise Exception('Linked List is empty')

    def get_last(self):
        if self.tail:
            return self.tail.data
        else:
            raise Exception('Linked List is empty')

    def traverse(self):
        if self.head:
            temp = self.head
            while temp:
                print(temp.data)
                temp = temp.next
        else:
            print(None)

    def reverse_traverse(self):
        if self.tail:
            temp = self.tail
            while temp:
                print(temp.data)
                temp = temp.prev
        else:
            print(None)

    def length(self):
        temp = self.head
        count = 0
        while temp:
            count += 1
            temp = temp.next
        return count

dll = DoublyLinkedList()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.insert_at_end(4)
dll.insert_at_end(5)
dll.insert_at_end(6)
dll.traverse()
JavaScript
class Node {
  constructor(data) {
    this.prev = null;
    this.data = data;
    this.next = null;
  }
}

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

  insertAtStart(data) {
    const newNode = new Node(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
  }

  insertAtEnd(data) {
    const newNode = new Node(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  insertAtPosition(pos, data) {
    const newNode = new Node(data);

    if (pos < 0 || pos > this.length()) {
      throw "Enter a valid position";
    } else {
      if (pos == 0) {
        this.insertAtStart(data);
      } else if (pos == this.length() - 1) {
        this.insertAtEnd(data);
      } else {
        let temp = this.head;
        for (let i = 0; i < pos - 1; i++) {
          temp = temp.next;
        }
        newNode.next = temp.next;
        temp.next = newNode;
        newNode.prev = temp;
      }
    }
  }

  deleteFromStart() {
    if (this.head) {
      let data;
      if (this.head === this.tail) {
        data = this.head.data;
        this.head = this.tail = null;
      } else {
        data = this.head.data;
        this.head = this.head.next;
        this.head.prev = null;
      }
      return data;
    } else {
      throw "Empty Linked List";
    }
  }

  deleteFromEnd() {
    if (this.head) {
      let data;
      if (this.head === this.tail) {
        data = this.head.data;
        this.head = this.tail = null;
      } else {
        data = this.tail.data;
        this.tail = this.tail.prev;
        this.tail.next = null;
      }
      return data;
    } else {
      throw "Empty Linked List";
    }
  }

  deleteAtPosition(pos) {
    if (pos < 0 || pos >= this.length()) {
      throw "Enter a valid position";
    } else {
      if (pos == 0) {
        return this.deleteFromStart();
      } else if (pos === this.length() - 1) {
        return this.deleteFromEnd();
      } else {
        let temp = this.head;
        for (let i = 0; i < pos; i++) {
          temp = temp.next;
        }
        const data = temp.data;
        const prevNode = temp.prev;
        prevNode.next = temp.next;
        temp.next.prev = prevNode;
        return data;
      }
    }
  }

  getFirst() {
    if (this.head) return this.head.data;
    throw "Linked List is empty";
  }

  getLast() {
    if (this.tail) return this.tail.data;
    throw "Linked List is empty";
  }

  traverse() {
    if (this.head) {
      let temp = this.head;
      while (temp) {
        console.log(temp.data);
        temp = temp.next;
      }
    } else {
      console.log(null);
    }
  }

  reverseTraverse() {
    if (this.tail) {
      let temp = this.tail;
      while (temp) {
        console.log(temp.data);
        temp = temp.prev;
      }
    } else {
      console.log(null);
    }
  }

  length() {
    let temp = this.head;
    let count = 0;
    while (temp) {
      count++;
      temp = temp.next;
    }
    return count;
  }
}

const dll = new DoublyLinkedList();
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
dll.insertAtEnd(4);
dll.insertAtEnd(5);
dll.insertAtEnd(6);
dll.traverse();

Output

1
2
3
4
5
6

Advantages of Doubly Linked List over Singly Linked List

  1. Doubly Linked List can be traversed in both (forward and backward) directions
  2. Only single temporary variable required for deletetion of a node

Disadvantages of Doubly Linked List over Singly Linked List

  1. Every node required an extra space for previous pointer
  2. All operations take some time to adjust previous pointer
Linked List
Program to find middle element of a Linked List
Author - Abhishek Kumar

Recommended Posts

Introduction to Linked list
Linked List
Program to find middle element of a Linked List
Program to reverse a linked list