一文详解Golang单链表

单向链表的实现形式就是由多个节点的集合共同构成一个线性序列．

• Ｇｏｌａｎｇ单链表实现栈
  入栈的时候往链表尾部添加数据，出栈的时候从链表尾部删除数据，先进后出属性．

package main
import (
   "errors"
   "fmt"
)

// node 单向链表
type node struct {
   Next  *node
   Value int
   Size  int
}
type listNode struct {
   Head *node // ｈｅａｄ作为操作节点，不参与到栈中
}

// newListNode 新建一个链表
func newListNode() (ret *listNode) {
   return &listNode{Head: &node{}}
}

// push 往栈顶添加数据
func (n *listNode) Push(nd interface{}) {
   var (
      d       = nd.(*node)
      current = n.Head
   )

   for current != nil {
      if current.Next == nil {
         d.Size = current.Size + 1
         current.Next = d
         break
      }
      current = current.Next
   }

}

// Pop 删除栈顶元素，并返回
func (n *listNode) Pop() (ret interface{}, err error) {
   var (
      d *node
   )
   if n.IsEmpty() {
      err = errors.New("stack is null")
      return
   }

   var (
      current = n.Head
   )
   for current.Next != nil {
      if current.Next.Next == nil {
         d = current.Next
         current.Next = nil
         break
      }
      current = current.Next
   }

   ret = d
   return
}

// Top 获取栈顶元素
func (n *listNode) Top() (ret interface{}, err error) {
   if n.IsEmpty() {
      err = errors.New("stack is null")
      return
   }
   var (
      d       *node
      current = n.Head
   )
   for current.Next != nil {
      if current.Next.Next == nil {
         d = current.Next
         break
      }
      current = current.Next
   }

   ret = d
   return
}

// IsEmpty()
func (n *listNode) IsEmpty() bool {
   return n.Head.Next == nil
}

// Len()
func (n *listNode) Len() int {
   var (
      data    *node
      current = n.Head.Next
   )
   if n.Head.Next == nil {
      return 0
   }
   for current != nil {
      if current.Next != nil {
         current = current.Next
      } else {
         data = current
         break
      }
   }

   return data.Size
}

// stackL 栈
type stackL interface {
   Push(n interface{})
   Pop() (interface{}, error)
   Top() (interface{}, error)
   IsEmpty() bool
   Len() int
}

func main() {
 var s = newListNode()
   l := stackL(s)
   l.Push(&node{
      Value: 2,
   })
   l.Push(&node{
      Value: 3,
   })
   l.Push(&node{
      Value: 4,
   })
   fmt.Println("len", l.Len())
   fmt.Println(l.Pop())
   fmt.Println("len", l.Len())
   fmt.Println(l.Top())

}

• 单向链表实现队列

入队的时候往链表尾部插入数据，出队的时候在链表头部删除数据，先进先出的属性．

package main
import (
   "errors"
   "fmt"
)

// node 单向链表
type node struct {
   Next  *node
   Value int
   Size  int
}
type listNode struct {
   Head *node // ｈｅａｄ作为操作节点，不参与到栈中
}

// newListNode 新建一个链表
func newListNode() (ret *listNode) {
   return &listNode{Head: &node{}}
}

// Enqueue 往队列添加数据
func (n *listNode) Enqueue(nd interface{}) {
   var (
      d       = nd.(*node)
      current = n.Head
   )

   for current != nil {
      if current.Next == nil {
         d.Size = current.Size + 1
         current.Next = d
         break
      }
      current = current.Next
   }

}

// Dequeue 删除队头元素，返回删除的数据
func (n *listNode) Dequeue() (ret interface{}, err error) {
   var (
      d *node
   )
   if n.IsEmpty() {
      err = errors.New("stack is null")
      return
   }

   // 获取第一个进入队列的数据
   d = n.Head.Next
   // 把剩下的队列数据接到ｈｅａｄ
   n.Head.Next = d.Next
   d.Next = nil
   // 遍历节点，减去一个长度
   current := n.Head.Next
   for current != nil {
      current.Size -= 1
      current = current.Next
   }
   ret = d
   return
}

// First 获取队头元素
func (n *listNode) First() (ret interface{}, err error) {
   if n.IsEmpty() {
      err = errors.New("stack is null")
      return
   }
   var (
      temp = n.Head.Next
      d    *node
   )

   // 复制数据
   d = temp
   d.Next = nil
   ret = d
   return
}

// IsEmpty()
func (n *listNode) IsEmpty() bool {
   return n.Head.Next == nil
}

// Len()
func (n *listNode) Len() int {
   var (
      data    *node
      current = n.Head.Next
   )
   if n.Head.Next == nil {
      return 0
   }
   for current != nil {
      if current.Next != nil {
         current = current.Next
      } else {
         data = current
         break
      }
   }

   return data.Size
}

// queueL 队列
type queueL interface {
   Enqueue(interface{})           // 添加一个元素
   Dequeue() (interface{}, error) // 删除一个元素
   IsEmpty() bool
   First() (interface{}, error)
   Len() int
}

func main() {
   // 初始化 1 节点
   var s = newListNode()
   l := queueL(s)
   l.Enqueue(&node{
      Value: 2,
   })
   l.Enqueue(&node{
      Value: 3,
   })
   l.Enqueue(&node{
      Value: 4,
   })
   l.Enqueue(&node{
      Value: 5,
   })
   fmt.Println("len: ", l.Len())
   fmt.Println(l.Dequeue())
   fmt.Println("len: ", l.Len())
   fmt.Println(l.Dequeue())
   fmt.Println("len: ", l.Len())
   fmt.Println(l.First())

}

转自：Golang基础教程