缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

链表

  1. 链表是数据结构之一，其中的数据呈线性排列。
  2. 每个数据节点都有1个“指针”，它指向下一个数据的内存地址。
  4. 访问数据时，我们需要从链表头部开始查找（线性查找），
  5. 如果目标数据在链表最后的话，需要的时间就是O(n)。
  7. 另外，添加数据只需要更改两个指针的指向，所以耗费的时间与n无关。
  8. 如果已经到达了添加数据的位置，那么添加操作只需花费O(1)的时间。
  9. 删除数据同样也只需O(1)的时间。
  11. 摘自 <<我的第一本算法书>>(【日】石田保辉；宫崎修一)

目标

  • 实现一个链表, 提供与数组类似的线性访问接口

设计

  • ILinkedList: 链表接口
  • IListIterator: 链表迭代器接口
  • tLinkedList: 链表, 实现ILinkedList接口
  • tListIterator: 链表迭代器, 实现IListIterator接口

单元测试

linked_list_test.go

  1. package data_structure
  3. import (
  4.     "fmt"
  5.     "learning/gooop/data_structure/linked_list"
  6.     "strings"
  7.     "testing"
  8. )
  10. func Test_LinkedList(t *testing.T) {
  11.     fnAssertTrue := func(b bool, msg string) {
  12.         if !b {
  13.             panic(msg)
  14.         }
  15.     }
  17.     list := linked_list.NewLinkedList()
  18.     state := list.String()
  19.     t.Log(state)
  20.     fnAssertTrue(state == "h=nil,t=nil,s=0", "expecting empty list")
  22.     list.Append(0)
  23.     state = list.String()
  24.     t.Log(state)
  25.     fnAssertTrue(state == "h=0,t=0,s=1,0", "expecting [0]")
  27.     list.Append(1)
  28.     state = list.String()
  29.     t.Log(state)
  30.     fnAssertTrue(state == "h=0,t=1,s=2,0,1", "expecting [0,1]")
  32.     e,it := list.Get(0)
  33.     t.Log(it)
  34.     fnAssertTrue(e == nil, "expecting e == nil")
  35.     fnAssertTrue(it == 0, "expecting 0")
  37.     e,it = list.Get(1)
  38.     t.Log(it)
  39.     fnAssertTrue(e == nil, "expecting e == nil")
  40.     fnAssertTrue(it == 1, "expecting 1")
  42.     e = list.Set(0, 10)
  43.     state = list.String()
  44.     t.Log(state)
  45.     fnAssertTrue(e == nil, "expecting e == nil")
  46.     fnAssertTrue(state == "h=10,t=1,s=2,10,1", "expecting [10,1]")
  48.     e = list.Set(1, 20)
  49.     state = list.String()
  50.     t.Log(state)
  51.     fnAssertTrue(e == nil, "expecting e == nil")
  52.     fnAssertTrue(state == "h=10,t=20,s=2,10,20", "expecting [10,20]")
  54.     e = list.Remove(1)
  55.     state = list.String()
  56.     t.Log(state)
  57.     fnAssertTrue(e == nil, "expecting e == nil")
  58.     fnAssertTrue(state == "h=10,t=10,s=1,10", "expecting [10]")
  60.     e = list.Remove(0)
  61.     state = list.String()
  62.     t.Log(state)
  63.     fnAssertTrue(e == nil, "expecting e == nil")
  64.     fnAssertTrue(state == "h=nil,t=nil,s=0", "expecting []")
  66.     e = list.Insert(0, 0)
  67.     state = list.String()
  68.     t.Log(state)
  69.     fnAssertTrue(e == nil, "expecting e == nil")
  70.     fnAssertTrue(state == "h=0,t=0,s=1,0", "expecting [0]")
  72.     e = list.Insert(1, 1)
  73.     state = list.String()
  74.     t.Log(state)
  75.     fnAssertTrue(e == nil, "expecting e == nil")
  76.     fnAssertTrue(state == "h=0,t=1,s=2,0,1", "expecting [0,1]")
  78.     e = list.Insert(3, 3)
  79.     t.Log(e)
  80.     fnAssertTrue(e != nil, "expecting e != nil")
  82.     e = list.Insert(-1, -1)
  83.     t.Log(e)
  84.     fnAssertTrue(e != nil, "expecting e != nil")
  86.     items := make([]string, 0)
  87.     for iter := list.Iterator();iter.More(); {
  88.         e,v := iter.Next()
  89.         fnAssertTrue(e == nil, "expecting e == nil")
  90.         items = append(items, fmt.Sprintf("%v", v))
  91.     }
  92.     state = strings.Join(items, ",")
  93.     t.Log(state)
  94.     fnAssertTrue(state == "0,1", "expecting [0,1]")
  95. }

测试输出

  1. $ go test -v linked_list_test.go 
  2. === RUN   Test_LinkedList
  3.     linked_list_test.go:19: h=nil,t=nil,s=0
  4.     linked_list_test.go:24: h=0,t=0,s=1,0
  5.     linked_list_test.go:29: h=0,t=1,s=2,0,1
  6.     linked_list_test.go:33: 0
  7.     linked_list_test.go:38: 1
  8.     linked_list_test.go:44: h=10,t=1,s=2,10,1
  9.     linked_list_test.go:50: h=10,t=20,s=2,10,20
  10.     linked_list_test.go:56: h=10,t=10,s=1,10
  11.     linked_list_test.go:62: h=nil,t=nil,s=0
  12.     linked_list_test.go:68: h=0,t=0,s=1,0
  13.     linked_list_test.go:74: h=0,t=1,s=2,0,1
  14.     linked_list_test.go:79: index out of bounds
  15.     linked_list_test.go:83: index out of bounds
  16.     linked_list_test.go:93: 0,1
  17. --- PASS: Test_LinkedList (0.00s)
  18. PASS
  19. ok      command-line-arguments  0.002s

ILinkedList.go

链表接口

  1. package linked_list
  3. type ILinkedList interface {
  4.     Size() int
  5.     IsEmpty() bool
  6.     IsNotEmpty() bool
  8.     Get(i int) (error,interface{})
  9.     Set(i int, it interface{}) error
  11.     Append(it interface{})
  12.     Remove(i int) error
  13.     Insert(i int, it interface{}) error
  15.     Iterator() IListIterator
  16.     String() string
  17. }

IListIterator.go

链表迭代器接口

  1. package linked_list
  3. type IListIterator interface {
  4.     More() bool
  5.     Next() (error,interface{})
  6. }

tLinkedList.go

链表, 实现ILinkedList接口

  1. package linked_list
  3. import (
  4.     "errors"
  5.     "fmt"
  6.     "strings"
  7. )
  9. type tLinkedList struct {
  10.     head *tLinkedNode
  11.     tail *tLinkedNode
  12.     size int
  13. }
  15. type tLinkedNode struct {
  16.     value interface{}
  17.     next *tLinkedNode
  18. }
  20. var gIndexOutofBoundsError = errors.New("index out of bounds")
  22. func NewLinkedList() ILinkedList {
  23.     return &tLinkedList{
  24.         head: nil,
  25.         tail: nil,
  26.         size: 0,
  27.     }
  28. }
  30. func newLinkedNode(value interface{}) *tLinkedNode {
  31.     return &tLinkedNode{
  32.         value,nil,
  33.     }
  34. }
  36. func (me *tLinkedList) Size() int {
  37.     return me.size
  38. }
  40. func (me *tLinkedList) IsEmpty() bool {
  41.     return me.size <= 0
  42. }
  44. func (me *tLinkedList) IsNotEmpty() bool {
  45.     return !me.IsEmpty()
  46. }
  48. func (me *tLinkedList) Get(i int) (error,interface{}) {
  49.     e,_,node := me.getNodeAt(i)
  50.     if e != nil {
  51.         return e, nil
  52.     }
  53.     return e,node.value
  54. }
  56. func (me *tLinkedList) getNodeAt(i int) (err error, prev *tLinkedNode, node *tLinkedNode) {
  57.     if i >= me.size || i < 0 {
  58.         return gIndexOutofBoundsError, nil, nil
  59.     }
  61.     n := 0
  62.     prev = nil
  63.     node = me.head
  65.     for {
  66.         if n >= i {
  67.             return nil, prev, node
  68.         }
  70.         if node == nil {
  71.             return gIndexOutofBoundsError, nil, nil
  72.         }
  74.         n++
  75.         prev = node
  76.         node = node.next
  77.     }
  78. }
  80. func (me *tLinkedList) Set(i int, value interface{}) error {
  81.     e,prev,node := me.getNodeAt(i)
  82.     if e != nil {
  83.         return e
  84.     }
  86.     nn := newLinkedNode(value)
  88.     if prev == nil {
  89.         me.head = nn
  90.     } else {
  91.         prev.next = nn
  92.     }
  94.     nn.next = node.next
  95.     if nn.next == nil {
  96.         me.tail = nn
  97.     }
  99.     return nil
  100. }
  102. func (me *tLinkedList) Append(value interface{}) {
  103.     nn := newLinkedNode(value)
  104.     t := me.tail
  106.     if t == nil {
  107.         me.head = nn
  108.     } else {
  109.         t.next = nn
  110.     }
  112.     me.tail = nn
  113.     me.size++
  114. }
  116. func (me *tLinkedList) Remove(i int) error {
  117.     e,prev,node := me.getNodeAt(i)
  118.     if e != nil {
  119.         return e
  120.     }
  122.     if prev != nil {
  123.         prev.next = node.next
  124.     } else {
  125.         me.head = node.next
  126.     }
  128.     if node.next == nil {
  129.         me.tail = prev
  130.     } else {
  131.         me.tail = node.next
  132.     }
  134.     me.size--
  135.     return nil
  136. }
  138. func (me *tLinkedList) Insert(i int, value interface{}) error {
  139.     nn := newLinkedNode(value)
  141.     if i == me.size {
  142.         // always allow inserting tail
  143.         t := me.tail
  144.         me.tail = nn
  145.         if t != nil {
  146.             t.next = nn
  147.         }
  149.         if me.head == nil {
  150.             me.head = nn
  151.         }
  153.         me.size++
  154.         return nil
  155.     }
  157.     e,prev,node := me.getNodeAt(i)
  158.     if e != nil {
  159.         return e
  160.     }
  162.     if prev == nil {
  163.         me.head = nn
  164.     } else {
  165.         prev.next = nn
  166.     }
  167.     nn.next = node
  169.     me.size++
  170.     return nil
  171. }
  173. func (me *tLinkedList) Iterator() IListIterator {
  174.     items := make([]interface{}, me.size)
  175.     i := 0
  176.     for node := me.head;; {
  177.         if node == nil {
  178.             break
  179.         }
  181.         items[i] = node.value
  182.         node = node.next
  183.         i++
  184.     }
  186.     return newListIterator(items)
  187. }
  189. func (me *tLinkedList) String() string {
  190.     items := make([]string, 0)
  192.     if me.head == nil {
  193.         items = append(items, "h=nil")
  194.     } else {
  195.         items = append(items, fmt.Sprintf("h=%v", me.head.value))
  196.     }
  198.     if me.tail == nil {
  199.         items = append(items, "t=nil")
  200.     } else {
  201.         items = append(items, fmt.Sprintf("t=%v", me.tail.value))
  202.     }
  204.     items = append(items, fmt.Sprintf("s=%v", me.size))
  206.     for node:=me.head;node != nil; {
  207.         items = append(items, fmt.Sprintf("%v", node.value))
  208.         node = node.next
  209.     }
  211.     return strings.Join(items, ",")
  212. }

tListIterator.go

链表迭代器, 实现IListIterator接口

  1. package linked_list
  3. type tListIterator struct {
  4.     items []interface{}
  5.     count int
  6.     pos int
  7. }
  9. func newListIterator(items []interface{}) IListIterator {
  10.     size := len(items)
  11.     copy := make([]interface{}, size)
  12.     for i,it := range items {
  13.         copy[i] = it
  14.     }
  16.     return &tListIterator{
  17.         items: copy,
  18.         count: size,
  19.         pos: 0,
  20.     }
  21. }
  23. func (me *tListIterator) More() bool {
  24.     return me.pos < me.count
  25. }
  27. func (me *tListIterator) Next() (error,interface{}) {
  28.     if me.pos >= me.count {
  29.         return gIndexOutofBoundsError, nil
  30.     }
  32.     n := me.pos
  33.     me.pos++
  34.     return nil, me.items[n]
  35. }

(end)