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