golang单链表基本操作
package main
import (
"fmt"
)
type ElemType int
// 定义单单链表的结构体
type Node struct {
data ElemType // 数据域
next *Node // 指针域(存放后继节点地址)
}
// 生成头节点
func New() *Node {
return &Node{0, nil}
}
// 在链表的第i个位置插入元素e
func (head *Node) Insert(i int, e ElemType) bool {
// 申明节点p指向链表第一个节点
var p = head
var j = 1 // 初始j从1开始遍历寻找i节点
for nil != p && j < i {
j++
p = p.next
}
if nil == p || j > i {
// 第i个元素不存在
return false
}
// 生成新节点存储e
var s = &Node{data: e}
// 将p的后继节点赋值给s的后继
s.next = p.next
p.next = s
return true
}
// 遍历链表
func (head *Node) Traverse() {
var p = head
for nil != p {
fmt.Println(p.data)
p = p.next
}
}
// 获取链表中第i个元素
func (head *Node) Get(i int) ElemType {
var p = head
for j := 1; j < i; j++ {
p = p.next
}
return p.data
}
// 删除链表第i个节点
func (head *Node) Delete(i int) bool {
var p = head
var j = 1
for nil != p && j < i {
j++
p = p.next
}
if nil == p || j > i {
return false
}
p.next = p.next.next
return true
}
// 链表反转方式一(头插入发)
// 依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表
func (head *Node) Reverse1() *Node {
var p = head.next
var newHead = &Node{} // 新链表的头指针
var temp = &Node{}
for nil != p {
temp = p
// 将temp插入到新链表的头部
temp.next = newHead
newHead = temp
p = p.next
}
return newHead
}
// 链表反转方式一(就地逆置法)
// 不用新建链表，直接对原链表做修改
func (head *Node) Reverse2() *Node {
var p = head
var beg = head
var end = head.next
for nil != end {
beg.next = end.next
// 将 end 移动至链表头
end.next = p
p = end
// 调整 end 的指向，使其指向 beg 后的一个节点，为反转下一个节点做准备
end = beg.next
}
return p
}
func main() {
var n = New()
n.Insert(1, 10000)
n.Insert(1, 1000)
n.Insert(1, 100)
n.Insert(1, 10)
n.Insert(1, 1)
// 遍历
fmt.Println("遍历链表")
n.Traverse()
// 反转
fmt.Println()
fmt.Println("反转链表")
var newNode = n.Reverse2()
newNode.Traverse()
// 获取第i个元素
//var e = n.Get(3)
//fmt.Println()
//fmt.Println("第3个元素", e)
// 删除第i个节点
//n.Delete(3)
//fmt.Println()
//fmt.Println("删除后元素")
//n.Traverse()
}