5 Best Ways to Insert a New Node at the End of a Circular Linked List in Python

Rate this post

πŸ’‘ Problem Formulation: The task is to design a python program that can efficiently insert a new node at the end of a circular linked list – a list where the last node points back to the first node instead of null. We start with a circular linked list and the value for the new node, and aim to insert this node such that it becomes the new end of the list, maintaining the circular structure.

Method 1: Traverse until the last node

This method involves iterating through the list starting at the head node until we reach the last element, which is identified by its next reference pointing back to the head. Once at the last node, we create a new node and adjust the pointers to include the new node in the list.

Here’s an example:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

cllist = CircularLinkedList()
cllist.append(1)
cllist.append(2)
cllist.append(3)
cllist.append(4)  # New node to be inserted at the end
print(cllist.head.next.next.next.data)  # Output should be 4

The output of this code snippet:

4

This snippet defines a Node class which represents an element in the linked list and a CircularLinkedList class that encapsulates the logic to append a node to the end. We then append four nodes and verify that the last node contains the value ‘4’.

Method 2: Improved traversal with a tail pointer

To optimize the append operation, we can maintain an additional tail pointer in our list class that always points to the last node. This eliminates the need for traversal every time we insert, as we can directly access the last node and modify its next reference.

Here’s an example:

class CircularLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            new_node.next = self.head
        else:
            self.tail.next = new_node
            self.tail = new_node
            new_node.next = self.head

# Usage is the same as in Method 1

The output will be the same as the previous example.

This method offers a performance improvement, especially beneficial for large lists, as it maintains a tail reference thus avoiding the need for a full list traversal on each append operation.

Method 3: Insert before head and swap data

We can optimize insertion by inserting the new node right after the head and then swapping the data of the head and new node. This method is effectively constant time because it doesn’t depend on the size of the list.

Here’s an example:

class CircularLinkedList:
    # Same __init__ as in Method 2

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            new_node.next = self.head
        else:
            new_node.next = self.head.next
            self.head.next = new_node
            # Swap the data
            self.head.data, new_node.data = new_node.data, self.head.data
            # Move the head reference so the new node is now the tail
            self.head = new_node

# Usage is the same as in Method 1

The output will be the same as the previous examples.

By inserting the new node after the head and swapping the data with the head node, we treat the new node as the last element and promote the head node, resulting in an append operation that’s consistent in time regardless of list size.

Method 4: If Node class is modifiable, use a circular property method

Assuming we are able to modify the Node class itself, we could integrate a method to identify the circular nature of the list. This method could potentially increase maintainability by encapsulating the circular logic within the node itself.

Here’s an example:

class Node:
    # Constructor as in Method 1
    def is_circular(self):
        return self.next == self.head

class CircularLinkedList:
    # Same as in previous methods but utilizing new Node method in append
    # ...

# Usage is the same as in Method 1

The output will be the same as the previous examples.

Encapsulating the circular-check logic within the Node class helps separate concerns. The CircularLinkedList append method becomes cleaner and more readable.

Bonus One-Liner Method 5: Insert using generator

For Python enthusiasts who love one-liners, you can use a generator to find the last node and then perform the append operation. This is more of a fun and Pythonic approach rather than a practical one for production code.

Here’s an example:

def append(self, data):
    new_node = Node(data)
    last_node = next((node for node in self.iter_nodes() if node.next == self.head), self.head)
    last_node.next = new_node
    new_node.next = self.head

# Assume iter_nodes is a generator yielding nodes from the list

The output will be the same as the previous examples.

This code snippet seeks to demonstrate the power of Python’s generator expressions for a succinct solution. However, this method might not be the most efficient or readable, especially for those less familiar with Python’s advanced features.

Summary/Discussion

  • Method 1: Traverse until the last node. Strengths: Simple and easy to understand. Weaknesses: O(n) complexity with each append.
  • Method 2: Improved traversal with a tail pointer. Strengths: Constant time append. Weaknesses: Requires additional memory to store the tail reference.
  • Method 3: Insert before head and swap data. Strengths: Constant time complexity, no need to traverse the list. Weaknesses: Less intuitive as it manipulates the head data.
  • Method 4: If Node class is modifiable, use a circular property method. Strengths: Encapsulated logic, improved readability and maintainability. Weaknesses: Requires modification of Node class, which might not always be possible.
  • Method 5: Bonus One-Liner Method. Strengths: Concise and Pythonic. Weaknesses: Less efficient, clarity suffers which can make the code harder to understand for some users.