Go 实现链表
2018-12-01 本文已影响0人
小码侠
链表
链表是一种物理结构上非连续、非顺序的存储结构。链表包含元素的一系列链接。每个链接都包含与另一个链接的连接。
链表结构
image
结构分析
-
链接列表包含一个名为first的链接元素。
-
每个链路都带有一个数据字段和一个名为next的链接字段。
-
每个链接使用其下一个链接与其下一个链接链接。
-
最后一个链接带有一个null链接以标记列表的结尾。
代码实现
package linked
import (
"bytes"
"fmt"
"sync"
)
// Node struct
type Node struct {
Value interface{}
next *Node
linked *Linked
id int64
}
func (n *Node) String() string {
return fmt.Sprint(n.Value)
}
//链表
type Linked struct {
head *Node //头
last *Node //尾
current *Node //当前
length int //长度
mux sync.Mutex
ident int64 //自id
}
func NewLinked() *Linked {
return &Linked{}
}
// String 数据方便输出
func (l *Linked) String() string {
bf := bytes.Buffer{}
bf.WriteByte('[')
current := l.head
sp := []byte{
' ',
',',
' ',
}
if !l.IsEmpty() {
bf.WriteByte(' ')
}
for current != nil {
bf.WriteString(current.String())
if current.next != nil {
bf.Write(sp)
}
current = current.next
}
if !l.IsEmpty() {
bf.WriteByte(' ')
}
bf.WriteByte(']')
return bf.String()
}
// GetLength 获取链表长度
func (l *Linked) GetLength() int {
return l.length
}
// GetHead 获取头
func (l *Linked) GetHead() *Node {
return l.head
}
// GetLast 获取尾
func (l *Linked) GetLast() *Node {
return l.last
}
// GetLast 获取当前节点
func (l *Linked) GetCurrent() *Node {
if l.current == nil {
return l.head
}
return l.current
}
//IsEmpty 判断是否为空
func (l *Linked) IsEmpty() bool {
return l.length == 0
}
// Append 添加节点到最后
func (l *Linked) Append(value interface{}) *Linked {
l.mux.Lock()
defer l.mux.Unlock()
//实例化node
node := &Node{
Value: value,
id: l.ident,
linked: l,
}
l.ident ++
//判断长度
if l.IsEmpty() {
l.head = node
} else {
l.last.next = node
}
//更新最后位置
l.last = node
l.length++
return l
}
// AppendMulti 一次性添加多个
func (l *Linked) AppendMulti(values ...interface{}) *Linked {
if len(values) < 1 {
return l
}
//多个添加
l.mux.Lock()
defer l.mux.Unlock()
for _, value := range values {
//实例化node
node := &Node{
Value: value,
id: l.ident,
linked: l,
}
l.ident ++
//判断长度
if l.IsEmpty() {
l.head = node
} else {
l.last.next = node
}
//更新最后位置
l.last = node
l.length++
}
return l
}
// Prepend 添加到最开始位置
func (l *Linked) Prepend(value interface{}) *Linked {
l.mux.Lock()
defer l.mux.Unlock()
//实例化node
node := &Node{
Value: value,
id: l.ident,
linked: l,
}
l.ident ++
//判断是否是第一次
if l.IsEmpty() {
l.last = node
} else {
node.next = l.head
}
l.head = node
l.length++
return l
}
// Pop 删除并返回最后一个节点
func (l *Linked) Pop() *Node {
if l.IsEmpty() {
return nil
}
l.mux.Lock()
defer l.mux.Unlock()
node := l.last
if l.length == 1 {
l.last = nil
l.head = nil
} else {
current := l.head
last := l.head
for current != nil {
if current.next != nil && current.next.next != nil {
//不是最后一个节点
last = current.next
}
current = current.next
}
last.next = nil
l.last = last
}
l.length--
return node
}
//Shift 删除并返回第一个元素
func (l *Linked) Shift() *Node {
if l.IsEmpty() {
return nil
}
l.mux.Lock()
defer l.mux.Unlock()
node := l.head
if l.length == 1 {
l.head = nil
l.last = nil
} else {
l.head = node.next
}
node.next = nil
return node
}
// Find 查找并返回节点
func (l *Linked) Find(value interface{}) *Node {
if l.IsEmpty() {
return nil
}
current := l.head
//查找到的节点
var node *Node
for current != nil {
if current.Value == value {
//找到节点后退出
node = current
break
} else {
current = current.next
}
}
return node
}
// FindAll 查找所有
func (l *Linked) FindAll(value interface{}) []*Node {
// 为空返回空
if l.IsEmpty() {
return nil
}
//查找到的节点
var nodes []*Node
//查找节点
current := l.head
for current != nil {
if current.Value == value {
nodes = append(nodes, current)
} else {
current = current.next
}
}
//判断是否找到对应节点
if len(nodes) < 1 {
return nil
}
return nodes
}
// Delete 删除节点（找到的第一个节点。）
func (l *Linked) Delete(value interface{}) *Node {
if l.IsEmpty() {
return nil
}
l.mux.Lock()
defer l.mux.Unlock()
var node *Node
//头节点就是被删除数据
if l.head.Value == value {
node = l.head
l.head = l.head.next
} else {
//查找并删除节点。
//查找节点
current := l.head.next
prevNode := l.head
for current != nil {
if current.Value == value {
//断开当前节点和下级节点的链接
prevNode.next = current.next
node = current
//下级节点为空，那么表示 current 为last。删除以后，current的上一级即为last
if current.next == nil {
l.last = prevNode
}
break
} else {
prevNode = current
current = current.next
}
}
}
l.length--
return node
}
// DeleteAll 删除所有
func (l *Linked) DeleteAll(value interface{}) []*Node {
// 为空返回空
if l.IsEmpty() {
return nil
}
l.mux.Lock()
defer l.mux.Unlock()
//查找到的节点
var nodes []*Node
//查找节点
current := l.head
var prevNode *Node
for current != nil {
if current.Value == value {
nodes = append(nodes, current)
//删除的是头
if prevNode == nil {
l.head = current.next
} else {
//断开当前节点关联
prevNode.next = current.next //跳过current
}
//下级节点为空，那么表示 current 为last。删除以后，current的上一级即为last
if current.next == nil {
l.last = prevNode
}
} else {
prevNode = current
}
current = current.next
}
//判断是否找到对应节点
ns := len(nodes)
if ns < 1 {
return nil
}
//处理长度
l.length = l.length - ns
return nodes
}
// Reset 充值并清空链表
func (l *Linked) Reset() {
l.mux.Lock()
defer l.mux.Unlock()
l.length = 0
l.head = nil
l.last = nil
}
// Next 获取下一个节点
func (l *Linked) Next() *Node {
if l.IsEmpty() {
return nil
}
if l.current == nil {
l.current = l.head
} else {
l.current = l.current.next
}
return l.current
}
使用示例
//实例化节点
l := linked.NewLinked()
//追加一个节点
fmt.Println("追加一个节点：")
l.Append(1)
fmt.Println(l) //[ 1 ]
//追加一个节点
fmt.Println("\n追加一个节点：")
l.Append(2)
fmt.Println(l) //[ 1 , 2 ]
//添加一个节点到开头
fmt.Println("\n添加一个节点到开头：")
l.Prepend(3) //[ 3 , 1 , 2 ]
fmt.Println(l)
fmt.Println("\n删除尾：")
fmt.Println(l.Pop()) //删除最后一个节点 ==>2
fmt.Println(l) //[ 3 , 1 ]
fmt.Println("\n删除头：")
fmt.Println(l.Shift()) //删除第一个节点 ==>3
fmt.Println(l) //[ 1 ]
//再插入多个节点
fmt.Println("\n批量插入：")
l.AppendMulti(1, 2, 3, 4, 5, 3, 1, 2)
fmt.Println(l) //[ 1 , 1 , 2 , 3 , 4 , 5 , 3 , 1 , 2 ]
fmt.Println("\n删除节点值为2的一个节点：")
l.Delete(2)
fmt.Println(l) //[ 1 , 1 , 3 , 4 , 5 , 3 , 1 , 2 ]
fmt.Println("\n删除节点值为3的所有节点：")
l.DeleteAll(3)
fmt.Println(l) //[ 1 , 1 , 4 , 5 , 1 , 2 ]
//遍历节点
fmt.Print("\n\n")
i := 0
for true {
node := l.Next()
if node == nil {
break
}
i++
fmt.Printf("第 %d 个节点值为：%v \n", i, node)
}
执行输出
//追加一个节点：
//[ 1 ]
//
//追加一个节点：
//[ 1 , 2 ]
//
//添加一个节点到开头：
//[ 3 , 1 , 2 ]
//
//删除尾：
//2
//[ 3 , 1 ]
//
//删除头：
//3
//[ 1 ]
//
//批量插入：
//[ 1 , 1 , 2 , 3 , 4 , 5 , 3 , 1 , 2 ]
//
//删除节点值为2的一个节点：
//[ 1 , 1 , 3 , 4 , 5 , 3 , 1 , 2 ]
//
//删除节点值为3的所有节点：
//[ 1 , 1 , 4 , 5 , 1 , 2 ]
//
//
//第 1 个节点值为：1
//第 2 个节点值为：1
//第 3 个节点值为：4
//第 4 个节点值为：5
//第 5 个节点值为：1
//第 6 个节点值为：2
长按二维码关注我们
