Python Data Structures - Doubly Linked List Other Related Topics

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



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

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

Doubly Linked List - Add Node At End

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

def push_back(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
    return
  else:
    
    #5. Else, traverse to the last node
    temp = self.head
    while(temp.next != None):
      temp = temp.next
    
    #6. Adjust the links  
    temp.next = newNode
    newNode.prev = temp

The below is a complete program that uses above discussed concept to insert new node at the end of the 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 end of the list
  def push_back(self, newElement):
    newNode = Node(newElement)
    if(self.head == None):
      self.head = newNode
      return
    else:
      temp = self.head
      while(temp.next != None):
        temp = temp.next
      temp.next = newNode
      newNode.prev = temp

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

# test the code                  
MyList = LinkedList()

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

The above code will give the following output:

The list contains: 10 20 30