Python Data Structures - Doubly Linked List Other Related Topics

Python - Swap node values of a Doubly Linked List



There are many instances where it is required to swap value of two nodes while working with a list. This can be achieved by traversing to the interested nodes and swap their values if the nodes are valid. For example - if the given list is 10->20->30->40->50. After swapping values of first and fourth nodes, the list will become 40->20->30->10->50.

The function swapNodeValues is created for this purpose which is a 4-step process.

def swapNodeValues(self, node1, node2):
  
  #1. count the number of nodes in the list
  temp = self.head
  N = 0
  while (temp != None):
    N += 1
    temp = temp.next

  #2. check if the swap positions are valid entries
  if(node1 < 1 or node1 > N or node2 < 1 or node2 > N):
    return

  #3. traverse to the nodes where values to be swapped
  pos1 = self.head
  pos2 = self.head
  for i in range(1, node1):
    pos1 = pos1.next;
  for i in range(1, node2):
    pos2 = pos2.next;

  #4. swap the values of two nodes
  val = pos1.data
  pos1.data = pos2.data
  pos2.data = val  

The below is a complete program that uses above discussed concept to swap values of two given nodes of a 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

  #swap node values
  def swapNodeValues(self, node1, node2):
    
    temp = self.head
    N = 0
    while (temp != None):
      N += 1
      temp = temp.next

    if(node1 < 1 or node1 > N or node2 < 1 or node2 > N):
      return

    pos1 = self.head
    pos2 = self.head
    for i in range(1, node1):
      pos1 = pos1.next;
    for i in range(1, node2):
      pos2 = pos2.next;

    val = pos1.data
    pos1.data = pos2.data
    pos2.data = val 

  #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 five elements in the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.push_back(40)
MyList.push_back(50)

#Display the content of the list.
MyList.PrintList()

#swap values of node=1 and node=4
MyList.swapNodeValues(1, 4)

#Display the content of the list.
MyList.PrintList()

The above code will give the following output:

The list contains: 10 20 30 40 50 
The list contains: 40 20 30 10 50