Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Go

Circular Linked List Operations

Explore how to implement and modify circular linked lists in Go, focusing on traversal, insertion, and deletion techniques. Understand how to maintain the circular connection during these operations and handle edge cases like single-node lists to apply these structures in practical applications such as scheduling and playlists.

We'll cover the following...

At this stage, the difference between a circular linked list and a standard singly linked list is established. Instead of the last node pointing to nil, it points back to the head node, forming a loop. As a result, the list has no natural termination point, and traversal requires explicit stopping conditions.

Now, let’s focus on the operations that can be performed on circular linked lists. While many of these operations are conceptually similar to those used in singly linked lists, there is an important difference: the circular connection must always be preserved.

Because the list forms a loop, operations such as traversal, insertion, and deletion must be implemented carefully. In particular:

  • Traversal cannot rely on reaching nil to stop.

  • Insertions must ensure that the circular link remains intact.

  • Deletions must reconnect neighboring nodes so that the loop structure is maintained.

Traversal in a circular linked list

Traversal in a circular linked list is slightly different from traversal in a standard singly linked list. In a regular linked list, traversal stops when the current node becomes nil. In a circular linked list, this stopping condition does not exist because the last node points back to the head.

Instead, traversal must stop when it returns to the starting node. Typically, the traversal steps are:

  1. Start traversal from the head node.

  2. Print the value stored in the current node.

  3. Move to the next node using current.next.

  4. Stop the traversal when the pointer reaches the head node again.

Let's look at the following interactive visualizer for circular linked list traversal.

Go implementation of traversal in a circular linked list

The following code creates a simple circular linked list and traverses it once, stopping when the traversal returns to the head node.

Go (1.24.2)
package main
import "fmt"
type ListNode struct {
	data int
	next *ListNode // Points to the next node
}
type CircularLinkedList struct {
	head *ListNode // Points to the first node
}
func (list *CircularLinkedList) traverse() {
	if list.head == nil {
		fmt.Println("The list is empty.")
		return
	}
	current := list.head // Start from the head node
	for {
		fmt.Print(current.data, " -> ") // Process current node
		current = current.next           // Move to the next node
		if current == list.head { // Stop when traversal returns to head
			break
		}
	}
	fmt.Println(current.data, "(back to head)")
}
func main() {
	// Create a circular linked list manually: 10 -> 20 -> 30 -> back to 10
	sampleList := &CircularLinkedList{}
	first := &ListNode{data: 10}
	second := &ListNode{data: 20}
	third := &ListNode{data: 30}
	sampleList.head = first
	first.next = second
	second.next = third
	third.next = first // Make the list circular
	// Traverse the circular linked list
	fmt.Print("Traversal of circular linked list: ")
	sampleList.traverse()
}
Circular linked list traversal

  • Time complexity: O(n)O(n) because each node is visited once.

  • Space complexity: O(1)O(1) as traversal only uses a single pointer variable.

Insertion in a circular linked list

Insertion in a circular linked list is similar to insertion in a singly linked list, but there is one extra requirement: the circular connection must remain intact.

Insertion

...