Python Program to Swap Adjacent Nodes in a Circular Linked List

This is a Python program to interchange two adjacent nodes of a circular linked list.

Problem Description

The program creates a circular single linked list and allows the user to interchange two adjacent nodes in the list.

Problem Solution

1. Create a class Node with instance variables data and next.
2. Create a class CircularLinkedList with instance variable head.
3. The variable head points to the first element in the circular single linked list.
4. Define methods get_node, get_prev_node, insert_after, insert_before, insert_at_end, append and display.
5. The method get_node takes an index as argument and traverses the list from the first node that many times to return the node at that index. It stops if it reaches the first node again.
6. The method get_prev_node takes a reference node as argument and returns the previous node.
7. The methods insert_after and insert_before insert a node after or before some reference node in the list.
8. The method insert_at_end inserts a node at the last position of the list.
9. The method display traverses the list from the first node and prints the data of each node. It stops when it reaches the first node again.
10. The method appends a node with the data item passed to the end of the list.
11. Define the function interchange which takes a linked list as argument and an index n.
12. The function interchange exchanges the nodes at indices n and n + 1 of the list.
13. Create an instance of CircularLinkedList, append data to it and perform the exchange operation.

Program/Source Code

Here is the source code of a Python program to interchange two adjacent nodes of a circular linked list. The program output is shown below.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class CircularLinkedList:
    def __init__(self):
        self.head = None
 
    def get_node(self, index):
        if self.head is None:
            return None
        current = self.head
        for i in range(index):
            current = current.next
            if current == self.head:
                return None
        return current
 
    def get_prev_node(self, ref_node):
        if self.head is None:
            return None
        current = self.head
        while current.next != ref_node:
            current = current.next
        return current
 
    def insert_after(self, ref_node, new_node):
        new_node.next = ref_node.next
        ref_node.next = new_node
 
    def insert_before(self, ref_node, new_node):
        prev_node = self.get_prev_node(ref_node)
        self.insert_after(prev_node, new_node)
 
    def insert_at_end(self, new_node):
        if self.head is None:
            self.head = new_node
            new_node.next = new_node
        else:
            self.insert_before(self.head, new_node)
 
    def append(self, data):
        self.insert_at_end(Node(data))
 
    def display(self):
        if self.head is None:
            return
        current = self.head
        while True:
            print(current.data, end = ' ')
            current = current.next
            if current == self.head:
                break
 
def interchange(llist, n):
    current = llist.get_node(n)
    current2 = current.next
    if current2.next != current:
        before = llist.get_prev_node(current)
        after = current2.next
        before.next = current2
        current2.next = current
        current.next = after
    if llist.head == current:
        llist.head = current2
    elif llist.head == current2:
        llist.head = current
 
 
a_cllist = CircularLinkedList()
 
data_list = input('Please enter the elements in the linked list: ').split()
for data in data_list:
    a_cllist.append(int(data))
 
n = int(input('The nodes at indices n and n+1 will be interchanged.'
              ' Please enter n: '))
 
interchange(a_cllist, n)
 
print('The new list: ')
a_cllist.display()

Program Explanation

1. An instance of CircularLinkedList is created.
2. The user is prompted to enter the data items for the list.
3. The user is asked to enter n, the index of the node which will be interchanged with the node following it.
4. The function interchange is called to perform the exchange operation.
5. The linked list is displayed.

Runtime Test Cases

Case 1:
Please enter the elements in the linked list: 1 2
The nodes at indices n and n+1 will be interchanged. Please enter n: 0
The new list: 
2 1 
 
Case 2:
Please enter the elements in the linked list: 4 1 5
The nodes at indices n and n+1 will be interchanged. Please enter n: 2
The new list: 
5 1 4 
 
Case 3:
Please enter the elements in the linked list: 3 18 40 1 6
The nodes at indices n and n+1 will be interchanged. Please enter n: 3
The new list: 
3 18 40 6 1

Sanfoundry Global Education & Learning Series – 1000 Python Programs.

If you wish to look at all Python Programming examples, go to 1000 Python Programs.

Free 30-Day Python Certification Bootcamp is Live. Join Now!

« Prev - Python Program to Find Intersection and Union of Two Linked Lists

» Next - Python Program to Swap Two Elements of the List without Key Field

Related Posts:

Recommended Articles: