Doubly Linked Lists in Python

A Doubly Linked List is an ordered collection of data elements with each data node having links to both its next as well as its previous elements.

Doubly Linked Lists are similar to Singly Linked Lists. It is a dynamic data structure too. Any type of data can be stored in a Doubly Linked List.

A Doubly Linked List Node consists of three parts, namely; a data field, and two link fields. One of the two link fields is supposed to point at the data element on the left-hand side of the current node, while the other to the right-hand side node.
doubly-linked-list

A Doubly Linked List consists of two head variables, each of which points at the two end nodes of the Linked List.

The availability of two links from each node enables two-way traversal of Doubly Linked Lists.

Characteristics of Doubly Linked Lists

  • Ordered - Data elements are stored in a certain order
  • Mutable- Data elements can be added/ deleted/ modified
  • Dynamic - The length of the Linked List is dynamic
  • Traversable - Unlike Singly Linked Lists, Doubly Linked Lists can be traversed in both directions enabled by the two pointers available
  • Can store data of any type
  • Unlike Singly Linked Lists, deletion of a node is easier to implement using the left-hand node-link

Doubly Linked List methods

  • add() - Used to add an element to the Linked List
    • At the beginning
    • At the end
    • Before an element
    • After an element
  • delete() - Used to delete an element from the Linked List
    • The head node
    • The last node
    • A middle node
  • clear() - Empties the Linked List
  • empty() - Checks whether or not the Linked List is empty
  • display() - Displays the Linked List in a user-comprehendible format
    • Displays in the forward direction
    • Displays in the backward direction

The two head variables point at one each end of the Linked List.

Implementing Doubly Linked List in Python

Doubly Linked Lists can be implemented in Python using its object-oriented characteristic.

Doubly linked Lists can be implemented via the following steps:

  1. Defining the Node class for the Linked List
    class Node:
        def __init__(self, val):
            self.value = val
            self.left = None
            self.right = None​
  2. Defining the Doubly Linked List (DLL) class which holds and initializes the two head variables
    class DLL:
        def __init__(self):
            self.head1 = None
            self.head2 = None​
  3. Defining the add() method used to add elements to the Doubly Linked List
    1. Defining the method
      def add(self, val):​
    2. Initializing the Linked List if found empty
              if self.empty() is True:
                  self.head1 = Node(val)
                  self.head2 = self.head1
                  print("Head value created")
                  return​
    3. To insert the Node at the beginning
              if opt == 1:
                  a = Node(val)
                  a.right = self.head1
                  self.head1.left = a
                  self.head1 = self.head1.left​
    4. To insert the Node at the end of the Linked List
              elif opt == 2:
                  a = Node(val)
                  self.head2.right = a
                  a.left = self.head2
                  self.head2 = self.head2.right​
    5. To insert before a specified location
              elif opt == 3:
                  pos = int(input("Enter the position ::"))
                  i = 1
                  n = self.head1.right
                  flag = 0
                  while n is not None:
                      if i == pos:
                          flag = 1
                          break
                      n = n.right
                      i = i + 1
                  if flag == 1:
                      a = Node(val)
                      a.right = n
                      n.left.right = a
                      a.left = n.left
                      n.left = a
                  else:
                      print("Position not found")​
    6. To insert after a specified location
              elif opt == 4:
                  pos = int(input("Enter the position ::"))
                  i = 0
                  n = self.head1
                  flag = 0
                  while n.right is not None:
                      if i == pos:
                          flag = 1
                          break
                      n = n.right
                      i = i + 1
                  if flag == 1:
                      a = Node(val)
                      n.right.left = a
                      a.right = n.right
                      a.left = n
                      n.right = a
                  else:
                      print("Position not found")​
  4. Defining the delete() method to delete an element from the Linked List
    1. Declaring the delete() method
      def delete(self):​
    2. Checking whether the Linked List is empty or not
              if self.empty() is True:
                  print("Linked List empty")
                  return​
    3. Checking and removing the last element in the Linked List
              elif self.head1.right is None:
                  self.head1 = None
                  self.head2 = None
                  return​
    4. Deleting the first element in the Linked List
              if opt == 1:
                  self.head1 = self.head1.right
                  self.head1.left = None​
    5. Deleting the last element in the Linked List
              elif opt == 2:
                  self.head2 = self.head2.left
                  self.head2.right = None​
    6. Deleting elements in the Linked List based on position or value
              else:
                  op = int(input("Enter 1 to delete by position\nEnter 2 to delete by value ::"))
                  if op == 1:
                      pos = int(input("Enter the position ::"))
                      i = 1
                      n = self.head1.right
                      flag = 0
                      while n.right is not None:
                          if i == pos:
                              flag = 1
                              break
                          i = i + 1
                          n = n.right
                      if flag == 1:
                          n.left.right = n.right
                          n.right.left = n.left
                      else:
                          print("Position not found")
                          return
                  else:
                      val = int(input("Enter the value you want to delete ::"))
                      n = self.head1
                      flag = 0
                      while n.right is not None:
                          if n.value == val:
                              flag = 1
                              break
                          n = n.right
                      if flag == 1:
                          n.left.right = n.right
                          n.right.left = n.left
                      else:
                          print("Value not found")
                          return​
  5. Defining the clear() method used to delete all the elements in the Linked List
        def clear(self):
            self.head1 = None
            self.head2 = None
            print("Linked List cleared")​
  6. Defining the empty() method used to check whether or not the Linked List is empty
        def empty(self):
            if self.head1 is None:
                return True
            else:
                return False​
  7. Defining the display() method used to print the Linked List in a user-comprehendible format
    1. Declaring the method
      def display(self):​
    2. Checking whether Linked List is empty or has only a single element
              if self.empty() is True:
                  print("Linked List empty")
                  return
              elif self.head1.right is None:
                  print("LINKED LIST")
                  print(self.head1.value, "HEAD 1 & 2")
                  print("Linked List ends")
                  return​
    3. To print in the forward direction
              if o == 1:
                  print(self.head1.value, " <== HEAD 1")
                  n = self.head1.right
                  while n is not self.head2:
                      print(n.value)
                      n = n.right
                  print(self.head2.value, " <== HEAD 2")
                  print("Linked List ends")​
    4. To print in the backward direction
              elif o == 2:
                  print(self.head2.value, " <== HEAD 2")
                  n = self.head2.left
                  while n is not self.head1:
                      print(n.value)
                      n = n.left
                  print(self.head1.value, " <== HEAD 1")
                  print("Linked List ends")​
  8. After assembling the entire code, creating an instance of the Linked List, implementing the methods to manipulate it, and finally compiling the code
    class Node:
        def __init__(self, val):
            self.value = val
            self.left = None
            self.right = None
    
    class DLL:
        def __init__(self):
            self.head1 = None
            self.head2 = None
    
        def add(self, val):
            if self.empty() is True:
                self.head1 = Node(val)
                self.head2 = self.head1
                print("Head value created")
                return
            opt = int(input(
                "Enter 1 to add a Node at the beginning\nEnter 2 to add a Node at the end\nEnter 3 to add a Node before "
                " a node\nEnter 4 to add a Node after a node ::"))
            if opt == 1:
                a = Node(val)
                a.right = self.head1
                self.head1.left = a
                self.head1 = self.head1.left
            elif opt == 2:
                a = Node(val)
                self.head2.right = a
                a.left = self.head2
                self.head2 = self.head2.right
            elif opt == 3:
                pos = int(input("Enter the position ::"))
                i = 1
                n = self.head1.right
                flag = 0
                while n is not None:
                    if i == pos:
                        flag = 1
                        break
                    n = n.right
                    i = i + 1
                if flag == 1:
                    a = Node(val)
                    a.right = n
                    n.left.right = a
                    a.left = n.left
                    n.left = a
                else:
                    print("Position not found")
            elif opt == 4:
                pos = int(input("Enter the position ::"))
                i = 0
                n = self.head1
                flag = 0
                while n.right is not None:
                    if i == pos:
                        flag = 1
                        break
                    n = n.right
                    i = i + 1
                if flag == 1:
                    a = Node(val)
                    n.right.left = a
                    a.right = n.right
                    a.left = n
                    n.right = a
                else:
                    print("Position not found")
    
            else:
                print("Wrong option")
    
        def delete(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            elif self.head1.right is None:
                self.head1 = None
                self.head2 = None
                return
            opt = int(input("Enter 1 to delete the beginning element\nEnter 2 to delete the last element\nEnter 3 to "
                            "delete elements in between ::"))
            if opt == 1:
                self.head1 = self.head1.right
                self.head1.left = None
            elif opt == 2:
                self.head2 = self.head2.left
                self.head2.right = None
            else:
                op = int(input("Enter 1 to delete by position\nEnter 2 to delete by value ::"))
                if op == 1:
                    pos = int(input("Enter the position ::"))
                    i = 1
                    n = self.head1.right
                    flag = 0
                    while n.right is not None:
                        if i == pos:
                            flag = 1
                            break
                        i = i + 1
                        n = n.right
                    if flag == 1:
                        n.left.right = n.right
                        n.right.left = n.left
                    else:
                        print("Position not found")
                        return
                else:
                    val = int(input("Enter the value you want to delete ::"))
                    n = self.head1
                    flag = 0
                    while n.right is not None:
                        if n.value == val:
                            flag = 1
                            break
                        n = n.right
                    if flag == 1:
                        n.left.right = n.right
                        n.right.left = n.left
                    else:
                        print("Value not found")
                        return
    
        def clear(self):
            self.head1 = None
            self.head2 = None
            print("Linked List cleared")
    
        def empty(self):
            if self.head1 is None:
                return True
            else:
                return False
    
        def display(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            elif self.head1.right is None:
                print("LINKED LIST")
                print(self.head1.value, "HEAD 1 & 2")
                print("Linked List ends")
                return
            o = int(input("Enter 1 to print in forward direction\nEnter 2 to print in backward direction ::"))
            print("LINKED LIST")
            if o == 1:
                print(self.head1.value, " <== HEAD 1")
                n = self.head1.right
                while n is not self.head2:
                    print(n.value)
                    n = n.right
                print(self.head2.value, " <== HEAD 2")
                print("Linked List ends")
            elif o == 2:
                print(self.head2.value, " <== HEAD 2")
                n = self.head2.left
                while n is not self.head1:
                    print(n.value)
                    n = n.left
                print(self.head1.value, " <== HEAD 1")
                print("Linked List ends")
            else:
                print("Wrong option")
    
    LL = DLL()
    while True:
        option = int(input("Enter 1 to add an element\nEnter 2 to delete an element\nEnter 3 to clear the Linked "
                           "List\nEnter 4 to display the Linked List\nEnter 5 to exit ::"))
        if option == 1:
            value = int(input("Enter the value you want to add ::"))
            LL.add(value)
            continue
        elif option == 2:
            LL.delete()
            continue
        elif option == 3:
            LL.clear()
            continue
        elif option == 4:
            LL.display()
            continue
        elif option == 5:
            print("Goodbye")
            break
        elif option == 6:
            print(LL.empty())
        else:
            print("Wrong option")​

    the output of the above code is

    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::5
    Head value created
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::6
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node before  a node
    Enter 4 to add a Node after a node ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::7
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node before  a node
    Enter 4 to add a Node after a node ::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::8
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node before  a node
    Enter 4 to add a Node after a node ::3
    Enter the position ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::9
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node before  a node
    Enter 4 to add a Node after a node ::4
    Enter the position ::0
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    Enter 1 to print in forward direction
    Enter 2 to print in backward direction ::1
    LINKED LIST
    6  <== HEAD 1
    9
    8
    5
    7  <== HEAD 2
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::3
    Enter 1 to delete by position
    Enter 2 to delete by value ::1
    Enter the position ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    Enter 1 to print in forward direction
    Enter 2 to print in backward direction ::2
    LINKED LIST
    5  <== HEAD 2
    9  <== HEAD 1
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::3
    Linked List cleared
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    Linked List empty
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::5
    Goodbye

Advantages and Disadvantages of Doubly Linked Lists

Advantages
  • Reversing a Doubly Linked List is very easy
  • Dynamic memory allocation enabled
  • Easy to implement
  • Bidirectional traversal enabled
  • Deletion is easy as only a single pointer is used
Disadvantages
  • Uses extra memory for one extra link per node
  • Elements require to be accessed sequentially due to random storage in the memory

Applications of Doubly Linked Lists

  • Navigation systems for front and back navigation
  • Used by browsers to implement web page navigation
  • Used to represent classic game deck of cards
  • Used to implement undo/ redo operations
  • Used as a thread scheduler in operating systems
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions