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

Rate this post

π‘ Problem Formulation: This article discusses how to insert a new node at the beginning of a circular linked list using Python. In a circular linked list, each node points to the next node in the list and the last node points back to the first node, forming a circle. The task is to add a new node such that it becomes the new head of the list, with its next pointer referencing the previous head, and the last node’s next pointer referencing the new node. This ensures the circular nature of the list is maintained.

## Method 1: Basic Node Insertion

This method involves creating a new node and adjusting pointers to insert it at the beginning of the circular linked list. The new node’s next pointer will point to the current head, and then the new node becomes the head. Additionally, we will update the last nodeβs next pointer to point to the new head to maintain the circular nature of the list.

Here’s an example:

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

new_node = Node(data)
if head is not None:
while temp.next != head:
temp = temp.next
temp.next = new_node
else:
new_node.next = new_node
return new_node

# Usage
second = Node(2)
third = Node(3)
head.next = second; second.next = third; third.next = head

Output:

`The list now starts with the new node containing data "0".`

This code snippet defines a function `insert_at_beginning()` that takes the current head of a circular linked list and the data for the new node to be inserted. The main steps it follows are creating a new node, traversing the list to find the last node, and modifying the next pointers to insert the new node at the beginning. It then returns the new head of the list. The list maintenance is critical to ensure that the structure remains circular after the insertion.

## Method 2: More Efficient Node Insertion

The second method optimizes the node insertion by reducing the traversal needed to insert the new node. Instead of traversing the entire list to find the last node, we keep track of the tail node in every insertion, which points back to the head, enabling O(1) insertion time complexity.

Here’s an example:

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

def insert_at_beginning_with_tail(head, tail, data):
new_node = Node(data)
if head is None:
new_node.next = new_node
else:
tail.next = new_node
return new_node

# Usage
tail = head # update tail if head changes```

Output:

`The list now starts with the new node containing data "0", and the insertion is done in O(1) time.`

The code snippet introduces an `insert_at_beginning_with_tail()` function that uses an additional tail parameter to avoid full list traversal. It performs the same node insertion as in Method 1 but does so in constant time by directly linking the new node with the tail’s next pointer. Remember to update the tail reference every time the head changes to keep the tail pointing to the correct node.

## Method 3: Class-Based Circular Linked List

This method encapsulates the circular linked list within a class, enhancing the insertion method to provide a better-organized and more maintainable structure. The class itself manages the details like updating pointers which makes your code more reusable and encapsulated.

Here’s an example:

```class CircularLinkedList:
def __init__(self):

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

# Usage
cll.insert_at_beginning(1)
cll.insert_at_beginning(0)```

Output:

`The CircularLinkedList now starts with the node containing data "0".`

In this approach, a `CircularLinkedList` class manages nodes and insertion logic. The `insert_at_beginning` method within the class creates a new node and adjusts the head and last node’s pointers, as needed. This encapsulation allows us to handle the circular linked list more abstractly, managing the head internally and providing a clear interface for insertion.

## Method 4: Tail Pointer within Class

Improving upon the previous class-based approach, this method maintains the tail pointer as part of the class state. This allows us to optimize the insertion operation further by eliminating the need to traverse the list when inserting a new node at the beginning.

Here’s an example:

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

def insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.tail = new_node
new_node.next = new_node
else:
self.tail.next = new_node

# Usage
cll.insert_at_beginning(1)
cll.insert_at_beginning(0)```

Output:

`The CircularLinkedList starts with the node containing data "0" and insertion is optimized using the tail pointer.`

The `CircularLinkedList` class now includes a `tail` attribute that is maintained along with the head pointer for every insertion operation. The `insert_at_beginning` method uses the tail pointer for quick insertion of new nodes at the beginning, resulting in a constant time complexity for insertions, improving performance over the classic traversal method.

## Bonus One-Liner Method 5: Lambda Function

For a more Pythonic one-liner solution, you can utilize a lambda function that wraps the node insertion logic concisely. This method is meant for those who prefer functional programming style and are comfortable with using lambda functions.

Here’s an example:

```insert_at_beginning = lambda head, data: (lambda new_node: (new_node if head is None else (new_node.next, head.next, lambda last_node: [last_node, last_node.next][0])(head)))(Node(data))

# Usage

Output:

`The head is now a new node containing data "0".`

The provided lambda function showcases the power of Python’s functional programming capabilities, creating a new node and linking it in place as the new head of the circular linked list instantaneously. While this one-liner may be intriguing to write, it’s not easily readable, and it is generally discouraged for complex operations such as linked-list manipulation due to concerns about code readability and maintainability.

## Summary/Discussion

Here are the summarized strengths and weaknesses of each method:

• Method 1: Basic Node Insertion. It’s easy to understand and implement. However, traversing the list to find the last node every time can lead to a higher time complexity.
• Method 2: More Efficient Node Insertion. By maintaining a reference to the tail, insertion complexity is reduced to O(1). It requires careful management of the tail pointer.
• Method 3: Class-Based Circular Linked List. Offers better organization and encapsulation. Still requires full traversal for each insertion unless a tail pointer is added.
• Method 4: Tail Pointer within Class. This optimizes the insertion method, achieving O(1) complexity. Implies additional complexity in maintaining the tail attribute correctly.
• Method 5: Lambda Function. Delivers a concise and functional solution. Might be difficult to understand for some, leading to potential challenges in debugging and maintaining the code.