Data structures – one-way linked lists

Unidirectional linked list of a Go language implementation

package main

import "fmt"

type Node struct {
	no int
	name string
	next *Node
}

// Insert a node to the end of the list (an implementation of queue Push)
func InsertTail(head *Node, newNode *Node){
	// Create an intermediate temporary node to find the last node in the list
	temp := head
	// Iterate through the list until the last node is inserted
	for {
		if temp.next == nil { // This condition is the last position of the list
			break
		}
		temp = temp.next
	}
	// Add the new node to the end of the list
	temp.next = newNode
}

// Implement an orderly insertion of a node into the list
func InsertSort(head, newNode *Node){
	temp := head
	// Important: You must compare temp.next. No with newNode.no in temp position during insertion, otherwise the insertion time will be missed
	for {
		if temp.next == nil { // The description is already at the end of the list
			// Note: The order of the following two lines cannot be reversed
			newNode.next = temp.next
			temp.next = newNode
			break
		} else if temp.next.no >= newNode.no {
			newNode.next = temp.next
			temp.next = newNode
			break
		}
		temp = temp.next
	}
}

// Implement header insertion node (an implementation of queue Push)
func InsertHead(head, newNode *Node){
	newNode.next = head.next
	head.next = newNode
}

// Implement a function to delete a linked list node
func Delete(head *Node, node *Node) {
	temp := head
	for {
		if temp.next == nil { // It is already at the end of the list, and no node to delete is found
			break
		} else if temp.next.no == node.no {
			temp.next = node.next
			// The following method can also be used, but it is a bit confusing to understand
			//temp.next = temp.next.next
			break
		}
		temp = temp.next
	}
}

// Implement a function that removes linked list nodes in the header (an implementation of queue Pop)
func DeleteHead(head *Node){
	if head.next == nil{
		return
	}else {
		head.next = head.next.next
	}
}

// Implement a function that terminates the list node (an implementation of queue Pop)
func DeleteTail(head *Node){
	temp := head
	for {
		if temp.next == nil{ // Indicates that the linked list is empty
			return
		}else if temp.next.next == nil{
			temp.next = nil
			break
		}
		temp = temp.next
	}
}

// Display the information of all nodes in the linked list
func List(head *Node){
	// The premise is that the header cannot be changed
	temp := head
	if temp.next == nil {
		fmt.Println("Linked list is empty")
		return
	}

	for {
		fmt.Printf("%d %s -->", temp.next.no, temp.next.name) // Prints information about the next node
		temp = temp.next
		if temp.next == nil {
			break}}}func main(a){

	// Define a header
	head := &Node{}
	// Define a node information
	node1 := &Node{
		no:   1,
		name: "Number1",
		next: nil,
	}
	node2 := &Node{
		no:   2,
		name: "Number2",
		next: nil,
	}
	node3 := &Node{
		no:   3,
		name: "Number3",
		next: nil,
	}
	node4 := &Node{
		no:   2,
		name: "Number4",
		next: nil,
	}

	InsertTail(head, node1)
	InsertTail(head, node2)

	InsertSort(head, node3)
	InsertSort(head, node2)
	InsertSort(head, node1)
	InsertSort(head, node4)

	Delete(head, node4)

	InsertHead(head, node1)
	InsertHead(head, node2)
	InsertHead(head, node3)
	InsertHead(head, node4)
	DeleteHead(head)
	DeleteTail(head)
	List(head)
}
Copy the code