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.
Comments
Post a Comment