Circular Linked List Implementation in Golang

1. Introduction

A Circular Linked List is a variation of the standard linked list in which the last node in the list points back to the first node, forming a complete loop. This structure provides a cyclic iteration capability where the list can be traversed endlessly in a loop.

2. Implementation Steps

1. Define a Node type with two fields: data (to store the actual value) and next (a pointer to the next node).

2. Define a CircularLinkedList type with a single pointer, head.

3. Implement methods to add elements at the end (Append), delete elements (DeleteWithValue), and display the list (Display).

3. Implementation in Golang

package main
import (
	"fmt"
)
type Node struct {
	data int
	next *Node
}
type CircularLinkedList struct {
	head *Node
}
func (list *CircularLinkedList) Append(data int) {
	newNode := &Node{data: data}
	if list.head == nil {
		list.head = newNode
		newNode.next = list.head
		return
	}
	temp := list.head
	for temp.next != list.head {
		temp = temp.next
	}
	temp.next = newNode
	newNode.next = list.head
}
func (list *CircularLinkedList) DeleteWithValue(data int) {
	if list.head == nil {
		return
	}
	if list.head.data == data {
		curr := list.head
		for curr.next != list.head {
			curr = curr.next
		}
		if list.head.next == list.head { // Only one node
			list.head = nil
		} else {
			curr.next = list.head.next
			list.head = list.head.next
		}
		return
	}
	curr := list.head
	for curr.next != list.head && curr.next.data != data {
		curr = curr.next
	}
	if curr.next.data == data {
		curr.next = curr.next.next
	}
}
func (list *CircularLinkedList) Display() {
	if list.head == nil {
		fmt.Println("List is empty")
		return
	}
	temp := list.head
	for {
		fmt.Print(temp.data, " -> ")
		temp = temp.next
		if temp == list.head {
			break
		}
	}
	fmt.Println(list.head.data)
}
func main() {
	list := &CircularLinkedList{}
	list.Append(1)
	list.Append(2)
	list.Append(3)
	list.Display()
	list.DeleteWithValue(2)
	list.Display()
}

Output:

1 -> 2 -> 3 -> 1
1 -> 3 -> 1

Explanation:

1. Node is the foundational element of the Circular Linked List, containing data and a next pointer to the succeeding node.

2. CircularLinkedList contains a single head pointer indicating the list's start.

3. Append method: Introduces a new node at the end, adjusting the last node's next pointer to the new node and the new node's next to the head, ensuring a loop.

4. DeleteWithValue method: This method first checks if the list is empty. If the head node's data matches the target value, it has special handling due to the circular nature of the list. Otherwise, it traverses the list and modifies the pointers to exclude the target node.

5. Display method: Prints out the list's data in a loop from start to end, then returns to the starting node.

6. The main function demonstrates adding nodes to the list, showcasing its content, removing a node, and displaying the updated list.

The Circular Linked List is especially useful when there's a need for continuous cycling over the list's data without keeping track of the start or end explicitly.