Data structures – circular linked lists

Circular list of a Go language implementation

package main

import "fmt"

// Define the node structure of a circular list
type circleSingleLink struct {
	id int
	name string
	next *circleSingleLink
}

// Insert the node into the circular list
func Insert(head, newnode *circleSingleLink) {
	// Check whether the list is empty
	if head.next == nil{
		// If null, the first element is added to the head node. This differs from other lists where the head node is empty
		head.id = newnode.id
		head.name = newnode.name
		// The key is to make a node also form a ring, i.e. terminal contact
		head.next = head
		return
	}
	// Add non-head nodes to the circular list
	temp := head
	for{
		if temp.next == head {
			// add a tail
			temp.next = newnode
			newnode.next = head
			break
		}
		temp = temp.next
	}
}

// Displays information about all nodes in the circular list
func CircleList(head *circleSingleLink){
	// Check whether the list is empty
	if head.next == nil {
		fmt.Println("Linked list is empty")
		return
	}

	temp := head
	for {
		fmt.Printf("[%d %s] -> ", temp.id, temp.name)
		// Notice how the termination condition is judged
		if temp.next == head{
			break
		}
		temp = temp.next
	}
}

// Delete a node from the list.
func CircleDelete(head, node *circleSingleLink) *circleSingleLink { // There is a return value because the value and direction of the header are changing
	// Delete:
	// Let temp point to head first
	// Let the helper point to the end of the circular list
	// Compare temp with the node to be deleted. If the node is the same, let the helper complete the deletion

	temp := head
	if temp.next == nil { // When the list is empty
		fmt.Println("Linked list is empty")
		return head
	}
	if temp.next == head { // A circular linked list with only one head
		temp.next = nil
		return head
	}
	helper := head
	for {
		if helper.next == head {
			break
		}
		helper = helper.next // Position the pointer to the last node of the circular list
	}

	// If there are two or more nodes
	for {
		if temp.next == head {
			// Indicates the last node and has not determined whether it is to be deleted
			if temp.id == node.id {
				helper.next = temp.next
			}else {
				fmt.Println("There is no such node")}break
		}
		if temp.id == node.id { // The node to delete is found
			if temp == head { // delete a header
				head = head.next
			}
			// Delete non-headers
			helper.next = temp.next // Helper is always the last one of temp
			break
		}
		temp = temp.next // for comparison
		helper = helper.next // Used as an operation
	}

	return head
}

func main(a){
	// Define a list header
	head := &circleSingleLink{}

	// Define the first node
	node1 := &circleSingleLink{
		id: 1,
		name : "number1",
	}
	node2 := &circleSingleLink{
		id: 2,
		name : "number2",
	}
	node3 := &circleSingleLink{
		id: 3,
		name : "number3",
	}
	Insert(head, node1)
	Insert(head, node2)
	Insert(head, node3)
	head = CircleDelete(head, node1)
	CircleList(head)
}
Copy the code

Joseph question:

package main

import "fmt"

type Boy struct {
	id int
	next *Boy
}

// Create a circular list and return the header pointer
func CreateLink(num int) *Boy {
	first := &Boy{} // The head pointer cannot move, so an auxiliary pointer is needed for loop creation
	curBoy := &Boy{}

	if num < 1 {
		return first
	}
	for i := 1; i <= num; i++ {
		boy := &Boy{
			id:   i,
			next: nil,}if i == 1 { // Because the first child is special
			first = boy
			curBoy = boy
			curBoy.next = first
		}else {
			curBoy.next = boy
			curBoy = boy
			curBoy.next = first // Make a circular list}}return first
}

// Display a circular list
func ShowBoy (first *Boy) {
	if first.next == nil {
		fmt.Println("Linked list is empty")
		return
	}
	curBoy := first
	for {
		fmt.Printf("Child %d ->", curBoy.id)
		if curBoy.next == first {
			break
		}
		curBoy = curBoy.next
	}
}

// Use circular linked lists to implement Joseph problems
func PlayGame(first *Boy, startNo int, countNum int) {
	// Empty list
	if first.next == nil {
		fmt.Println("List is empty. Game over.")
		return
	}
	// Define two pointer loops with first for comparison and tail for deletion
	tail := first
	// Place the tail finger at the end of the list
	for {
		if tail.next == first {
			break
		}
		tail = tail.next
	}
	// Start moving startNo-1 step
	for i := 0; i < startNo - 1; i++ {
		first = first.next
		tail = tail.next
	}
	fmt.Println()
	// Start a loop to delete the first countnum-1 node in the circular list
	for {
		for i := 0; i < countNum - 1; i++ {
			first = first.next
			tail = tail.next
		}
		// Prints information about the node to be circled
		fmt.Printf("The node numbered %d is circled \n", first.id)
		// Delete the current node that first points to
		first = first.next
		tail.next = first
		// Determine the end condition
		if tail == first {
			break}}// Prints the last looped node
	fmt.Printf("The node numbered %d is circled \n", first.id)
}

func main(a){
	first := CreateLink(51)
	ShowBoy(first)
	PlayGame(first, 2.3)}Copy the code