复习一下数据结构,用golang来实现单向链表
成都创新互联公司是一家集网站建设,五华企业网站建设,五华品牌网站建设,网站定制,五华网站建设报价,网络营销,网络优化,五华网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。
package main
import "fmt"
type Object interface{}
type Node struct {
Data Object
next *Node
}
type List struct {
size uint64
head *Node
tail *Node
}
func (list *List) Init() {
(*list).size = 0
(*list).head = nil
(*list).tail = nil
}
// 向链表追加节点
func (list *List) Append(node *Node) bool {
if node == nil {
return false
}
(*node).next = nil // 新加节点在末尾,没有next
if (*list).size == 0 {
(*list).head = node
} else {
oldTail := (*list).tail // 取尾结点
(*oldTail).next = node // 尾结点的next指向新加节点
}
(*list).tail = node // 新节点是尾结点
(*list).size++
return true
}
// 向第i个节点处插入节点
func (list *List) Insert(i uint64, node *Node) bool {
if node == nil || i > (*list).size || (*list).size == 0 {
return false
}
if i == 0 {
(*node).next = (*list).head
(*list).head = node
} else {
preNode := (*list).head
for j := uint64(1); j < i; j++ {
preNode = (*preNode).next
}
(*node).next = (*preNode).next // 新节点指向旧节点原来所指的next
(*preNode).next = node // 原节点的next指向新节点
}
(*list).size++
return true
}
// 移除指定位置的节点
func (list *List) Remove(i uint64) bool {
if i >= (*list).size {
return false
}
if i == 0 {
preHead := (*list).head // 取出旧的链表头
(*list).head = preHead.next // 旧链表头的next变为新的头
// 如果仅有一个节点,则头尾节点清空
if (*list).size == 1 {
(*list).head = nil
(*list).tail = nil
}
} else {
preNode := (*list).head
for j := uint64(1); j < i; j++ {
preNode = (*preNode).next
}
node := (*preNode).next // 找到当前要删除的节点
(*preNode).next = node.next // 把当前要删除节点的next赋给其父节点的next,完成后代转移
// 若删除的尾部,尾部指针需要调整
if i == ((*list).size - 1) {
(*list).tail = preNode
}
}
(*list).size--
return true
}
// 移除所有节点
func (list *List) RemoveAll() bool {
(*list).Init()
return true
}
// 获取指定位置的节点
func (list *List) Get(i uint64) *Node {
if i >= (*list).size {
return nil
}
node := (*list).head
for j := uint64(0); j < i; j++ {
node = (*node).next
}
return node
}
// 搜索某个数据的节点位置
func (list *List) IndexOf(data Object) int64 {
pos := int64(-1)
node := (*list).head
if node.Data == data {
return 0
}
for j := uint64(1); j < (*list).size; j++ {
if node != nil {
node = (*node).next
if node != nil && node.Data == data {
pos = int64(j)
break
}
}
}
return pos
}
// 取得链表长度
func (list *List) GetSize() uint64 {
return (*list).size
}
// 取得链表头
func (list *List) GetHead() *Node {
return (*list).head
}
// 取得链表尾
func (list *List) GetTail() *Node {
return (*list).tail
}
func main() {
var l List
l.Init()
node1 := &Node{Data: 11111}
l.Append(node1)
node2 := &Node{Data: 22222}
l.Append(node2)
node3 := &Node{Data: 33333}
l.Append(node3)
node4 := &Node{Data: "insert"}
l.Insert(1, node4)
node5 := &Node{Data: "head"}
l.Insert(0, node5)
node6 := &Node{Data: "tail"}
l.Append(node6)
l.Remove(0)
l.Remove(1)
l.Remove(3)
pos1 := l.IndexOf(22222)
pos2 := l.IndexOf(44444)
fmt.Println(pos1, pos2)
fmt.Println(l.GetHead(), l.GetTail(), l.GetSize())
fmt.Println()
//l.RemoveAll()
for i := uint64(0); i < l.size; i++ {
fmt.Println(l.Get(i))
}
}