Python - Insert a new node at a given position in the Doubly Linked List
In this method, a new element is inserted at the specified position in the doubly linked list. For example - if the given list is 10->20->30 and a new element 100 is added at position 2, the list becomes 10->100->20->30.
First, a new node with given element is created. If the insert position is 1, then the new node is made to head. Otherwise, traverse to the node that is previous to the insert position and check if it is null or not. In case of null, the specified position does not exist. In other case, update the links. The below figure describes the process, if the insert node is other than the head node.
The function push_at is created for this purpose. It is a 6-step process.
def push_at(self, newElement, position): #1. allocate node to new element newNode = Node(newElement) #2. check if the position is > 0 if(position < 1): print("\nposition should be >= 1.") elif (position == 1): #3. if the position is 1, make new node as head newNode.next = self.head self.head.prev = newNode self.head = newNode else: #4. Else, make a temp node and traverse to the # node previous to the position temp = self.head for i in range(1, position-1): if(temp != None): temp = temp.next #5. If the previous node is not null, adjust # the links if(temp != None): newNode.next = temp.next newNode.prev = temp temp.next = newNode if (newNode.next != None): newNode.next.prev = newNode else: #6. When the previous node is null print("\nThe previous node is null.")
The below is a complete program that uses above discussed concept to insert new node at a given position in 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 #Inserts a new element at the given position def push_at(self, newElement, position): newNode = Node(newElement) if(position < 1): print("\nposition should be >= 1.") elif (position == 1): newNode.next = self.head self.head.prev = newNode self.head = newNode else: temp = self.head for i in range(1, position-1): if(temp != None): temp = temp.next if(temp != None): newNode.next = temp.next newNode.prev = temp temp.next = newNode if (newNode.next != None): newNode.next.prev = newNode else: print("\nThe previous node is null.") #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 in the list. MyList.push_back(10) MyList.push_back(20) MyList.push_back(30) MyList.PrintList() #Insert an element at position 2 MyList.push_at(100, 2) MyList.PrintList() #Insert an element at position 1 MyList.push_at(200, 1) MyList.PrintList()
The above code will give the following output:
The list contains: 10 20 30 The list contains: 10 100 20 30 The list contains: 200 10 100 20 30