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

by

💡 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

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

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

new_head = insert_at_beginning(head, 0)

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)
  new_node.next = head
  if head is None:
    new_node.next = new_node
  else:
    tail.next = new_node
  return new_node

# Usage
head = Node(1)
tail = head
new_head = insert_at_beginning_with_tail(head, tail, 0)
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):
    self.head = None

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

# Usage
cll = CircularLinkedList()
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.head = None
    self.tail = None

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

# Usage
cll = CircularLinkedList()
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
head = Node(1)
head.next = head
new_head = insert_at_beginning(head, 0)

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.