Python Data Structures - Circular Doubly Linked List Other Related Topics

Python - Insert a new node at the start of the Circular Doubly Linked List



In this method, a new node is inserted at the start of the circular doubly linked list. For example - if the given List is 10->20->30 and a new element 100 is added at the start, the List becomes 100->10->20->30.

Inserting a new node at the start of the circular doubly linked list is very easy. First, a new node with given element is created. It is then added at the start of the list by linking the head node and last node to the new node.

Circular Doubly Linked List - Add Node At Start

The function push_front is created for this purpose. It is a 6-step process.

def push_front(self, newElement):
  
  #1 & 2 & 3. allocate node, assign data element
  #          assign null to the next and prev of 
  #          the new node
  newNode = Node(newElement)
  
  #4. Check the list is empty or not,
  #   if empty make the new node as head 
  if(self.head == None):
    self.head = newNode
    newNode.next = self.head
    newNode.prev = self.head
    return
  else:
    
    #5. Else, traverse to the last node
    temp = self.head
    while(temp.next != self.head):
      temp = temp.next
    
    #6. Adjust the links  
    temp.next = newNode
    newNode.prev = temp
    newNode.next = self.head
    self.head.prev = newNode
    self.head = newNode

The below is a complete program that uses above discussed concept to insert new node at the start of the circular doubly linked list.

# node structure
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

#class Linked List
class LinkedList:
  def __init__(self):
    self.head = None

  #Add new element at the start of the list
  def push_front(self, newElement):
    newNode = Node(newElement)
    if(self.head == None):
      self.head = newNode
      newNode.next = self.head
      newNode.prev = self.head
      return
    else:
      temp = self.head
      while(temp.next != self.head):
        temp = temp.next
      temp.next = newNode
      newNode.prev = temp
      newNode.next = self.head
      self.head.prev = newNode
      self.head = newNode

  #display the content of the list
  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("The list contains:", end=" ")
      while (True):
        print(temp.data, end=" ")
        temp = temp.next
        if(temp == self.head):
          break
      print()
    else:
      print("The list is empty.")

# test the code                  
MyList = LinkedList()

#Add three elements at the start of the list.
MyList.push_front(10)
MyList.push_front(20)
MyList.push_front(30)
MyList.PrintList()

The above code will give the following output:

The list contains: 30 20 10