labmem
d375463de5
- 将现有练习及 module 文件迁移至 go/practice，保持代码和依赖不变 - 新增 go/projects 项目区说明，更新目录约定与开发命令 BREAKING CHANGE: Go 练习命令需改在 go/practice 目录下执行
101 lines
2.2 KiB
Go
101 lines
2.2 KiB
Go
package linkedlist
|
|
|
|
import (
|
|
"fmt"
|
|
"strings"
|
|
)
|
|
|
|
// Node 是单向链表的一个节点,持有数据与指向下一个节点的指针。
|
|
type Node[T comparable] struct {
|
|
Data T
|
|
Next *Node[T]
|
|
}
|
|
|
|
// LinkedList 是持有头指针的单向链表,零值即为空表。
|
|
type LinkedList[T comparable] struct {
|
|
head *Node[T]
|
|
}
|
|
|
|
// InsertHead 将新节点插入表头。
|
|
func (l *LinkedList[T]) InsertHead(data T) {
|
|
l.head = &Node[T]{Data: data, Next: l.head}
|
|
}
|
|
|
|
// InsertTail 将新节点追加到表尾;空表时新节点直接成为表头。
|
|
func (l *LinkedList[T]) InsertTail(data T) {
|
|
newNode := &Node[T]{Data: data}
|
|
if l.head == nil {
|
|
l.head = newNode
|
|
return
|
|
}
|
|
current := l.head
|
|
for current.Next != nil {
|
|
current = current.Next
|
|
}
|
|
current.Next = newNode
|
|
}
|
|
|
|
// DeleteHead 删除表头节点;空表时无操作。
|
|
func (l *LinkedList[T]) DeleteHead() {
|
|
if l.head != nil {
|
|
l.head = l.head.Next
|
|
}
|
|
}
|
|
|
|
// DeleteTail 删除表尾节点;空表时无操作,仅剩一个节点时表变空。
|
|
func (l *LinkedList[T]) DeleteTail() {
|
|
switch {
|
|
case l.head == nil:
|
|
case l.head.Next == nil:
|
|
l.head = nil
|
|
default:
|
|
current := l.head
|
|
for current.Next.Next != nil {
|
|
current = current.Next
|
|
}
|
|
current.Next = nil
|
|
}
|
|
}
|
|
|
|
// Search 返回首个 Data 等于 data 的节点;不存在时返回 nil。
|
|
func (l *LinkedList[T]) Search(data T) *Node[T] {
|
|
for current := l.head; current != nil; current = current.Next {
|
|
if current.Data == data {
|
|
return current
|
|
}
|
|
}
|
|
return nil
|
|
}
|
|
|
|
// Len 返回链表的节点个数。
|
|
func (l *LinkedList[T]) Len() int {
|
|
count := 0
|
|
for current := l.head; current != nil; current = current.Next {
|
|
count++
|
|
}
|
|
return count
|
|
}
|
|
|
|
// Reverse 原地反转链表。
|
|
func (l *LinkedList[T]) Reverse() {
|
|
var prev, current *Node[T]
|
|
current = l.head
|
|
for current != nil {
|
|
next := current.Next
|
|
current.Next = prev
|
|
prev = current
|
|
current = next
|
|
}
|
|
l.head = prev
|
|
}
|
|
|
|
// String 以 "1 -> 2 -> nil" 的格式输出整条链,便于打印与调试。
|
|
func (l LinkedList[T]) String() string {
|
|
var sb strings.Builder
|
|
for current := l.head; current != nil; current = current.Next {
|
|
fmt.Fprintf(&sb, "%v -> ", current.Data)
|
|
}
|
|
sb.WriteString("nil")
|
|
return sb.String()
|
|
}
|