Go实战--实现一个单向链表(The way to go)

生命不止，继续 go go go !!!

今天跟大家分享一下数据介绍相关的实现吧，那就已链表为例吧。

golang中为我们提供了一个list，我们先了解一下container/list。

container/list

功能：
Package list implements a doubly linked list.

看清楚了吧，是双向链表。

一些方法：
func (e *Element) Next() *Element
返回该元素的下一个元素，如果没有下一个元素则返回nil

func (e *Element) Prev() *Element
返回该元素的前一个元素，如果没有前一个元素则返回nil。

func New() *List
返回一个初始化的list

func (l *List) Back() *Element
获取list l的最后一个元素

func (l *List) Front() *Element
获取list l的第一个元素

func (l *List) Init() *List
list l初始化或者清除list l

func (l *List) InsertAfter(v interface{},mark *Element) *Element
在list l中元素mark之后插入一个值为v的元素，并返回该元素，如果mark不是list中元素，则list不改变。

func (l *List) InsertBefore(v interface{},mark *Element) *Element
在list l中元素mark之前插入一个值为v的元素，并返回该元素，如果mark不是list中元素，则list不改变。

func (l *List) Len() int
获取list l的长度

func (l *List) MoveAfter(e,mark *Element)
将元素e移动到元素mark之后，如果元素e或者mark不属于list l，或者e==mark，则list l不改变。

func (l *List) MoveBefore(e,mark *Element)
将元素e移动到元素mark之前，如果元素e或者mark不属于list l，或者e==mark，则list l不改变。

func (l *List) MoveToBack(e *Element)
将元素e移动到list l的末尾，如果e不属于list l，则list不改变。

func (l *List) MoveToFront(e *Element)
将元素e移动到list l的首部，如果e不属于list l，则list不改变。

func (l *List) PushBack(v interface{}) *Element
在list l的末尾插入值为v的元素，并返回该元素。

func (l *List) PushBackList(other *List)
在list l的尾部插入另外一个list，其中l和other可以相等。

func (l *List) PushFront(v interface{}) *Element
在list l的首部插入值为v的元素，并返回该元素。

func (l *List) PushFrontList(other *List)
在list l的首部插入另外一个list，其中l和other可以相等。

func (l *List) Remove(e *Element) interface{}
如果元素e属于list l，将其从list中删除，并返回元素e的值。

简单的应用：

package main

 import (
    "container/list"
    "fmt"
 )

 func main() {
    // 创建一个链表
    alist := list.New()

    fmt.Println("Size before : ",alist.Len())

    //向链表中添加元素
    alist.PushBack("a")
    alist.PushBack("b")
    alist.PushBack("c")

    fmt.Println("Size after insert(push): ",alist.Len())

    // 遍历
    for e := alist.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value.(string))
    }

    //移除元素
    alist.Remove(alist.Front())
    alist.Remove(alist.Front())
    alist.Remove(alist.Front())

    fmt.Println("Size after remove(pop) : ",alist.Len())

 }

输出：
Size before : 0
Size after insert(push): 3
a
b
c
Size after remove(pop) : 0

实现一个单向链表

go为我们提供的list是一个双向链表，那么我们自己实现一个单向链表吧。

声明节点

package singly_linked_list

type Node struct {
  Value interface{}

  next *Node
}

func (n *Node) Next() *Node {
  return n.next
}

type SinglyLinkedList struct {
  front *Node
  length int
}

初始化
这个不是main中的init

func (s *SinglyLinkedList) Init() *SinglyLinkedList {
  s.length = 0
  return s
}

New一个链表

func New() *SinglyLinkedList {
  return new(SinglyLinkedList).Init()
}

返回头结点

func (s *SinglyLinkedList) Front() *Node {
  return s.front
}

返回尾结点

func (s *SinglyLinkedList) Back() *Node {
  currentNode := s.front
  for currentNode != nil && currentNode.next != nil {
    currentNode = currentNode.next
  }
  return currentNode
}

添加尾结点

func (s *SinglyLinkedList) Append(n *Node) {
  if s.front == nil {
    s.front = n
  } else {
    currentNode := s.front

    for currentNode.next != nil {
      currentNode = currentNode.next
    }

    currentNode.next = n
  }

  s.length++
}

添加头结点

func (s *SinglyLinkedList) Prepend(n *Node) {
  if s.front == nil {
    s.front = n
  } else {
    n.next = s.front
    s.front = n
  }

  s.length++
}

在指定结点前添加结点

func (s *SinglyLinkedList) InsertBefore(insert *Node,before *Node) {
  if s.front == before {
    insert.next = before
    s.front = insert
    s.length++
  } else {
    currentNode := s.front
    for currentNode != nil && currentNode.next != nil && currentNode.next != before {
      currentNode = currentNode.next
    }

    if currentNode.next == before {
      insert.next = before
      currentNode.next = insert
      s.length++
    }
  }
}

在指定结点后添加结点

func (s *SinglyLinkedList) InsertAfter(insert *Node,after *Node) {
  currentNode := s.front
  for currentNode != nil && currentNode != after && currentNode.next != nil {
    currentNode = currentNode.next
  }

  if currentNode == after {
    insert.next = after.next
    after.next = insert
    s.length++
  }
}

删除指定结点

func (s *SinglyLinkedList) Remove(n *Node) {
  if s.front == n {
    s.front = n.next
    s.length--
  } else {
    currentNode := s.front

    // search for node n
    for currentNode != nil && currentNode.next != nil && currentNode.next != n {
      currentNode = currentNode.next
    }

    // see if current's next node is n
    // if it's not n,then node n wasn't found in list s
    if currentNode.next == n {
      currentNode.next = currentNode.next.next
      s.length--
    }
  }
}