Python Data Structures - Linked List Other Related Topics

Python - Insert a new node at a given position in the Linked List



In this method, a new element is inserted at the specified position in the linked list. For example - if the given List is 10->20->30 and a new element 100 is added at position 2, the Linked 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, assign next of the new node as next of the previous node and next of previous node as new node. The below figure describes the process, if the insert node is other than the head node.

Linked List - Insert 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 next of the
    #   new node as head and new node as head
    newNode.next = self.head
    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, make 
    #   newNode next as temp next and temp next 
    #   as newNode.
    if(temp != None):
      newNode.next = temp.next
      temp.next = 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 linked list.

# node structure
class Node:
  def __init__(self, data):
    self.data = data
    self.next = 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

  #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 = 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
        temp.next = 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 at the end of 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