手撸golang 根本数据结构与算法 链表
缘起
最近浏览<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳golang练习之
链表
链表是数据结构之一，其中的数据呈线性排列。每个数据节点都有1个“指针”，它指向下一个数据的内存地址。拜访数据时，咱们须要从链表头部开始查找（线性查找），如果指标数据在链表最初的话，须要的工夫就是O(n)。另外，增加数据只须要更改两个指针的指向，所以消耗的工夫与n无关。如果曾经达到了增加数据的地位，那么增加操作只需破费O(1)的工夫。删除数据同样也只需O(1)的工夫。摘自 <<我的第一本算法书>>(【日】石田保辉；宫崎修一)指标
- 实现一个链表, 提供与数组相似的线性拜访接口
设计
- ILinkedList: 链表接口
- IListIterator: 链表迭代器接口
- tLinkedList: 链表, 实现ILinkedList接口
- tListIterator: 链表迭代器, 实现IListIterator接口
单元测试
linked_list_test.go
package data_structureimport ( "fmt" "learning/gooop/data_structure/linked_list" "strings" "testing")func Test_LinkedList(t *testing.T) { fnAssertTrue := func(b bool, msg string) { if !b { panic(msg) } } list := linked_list.NewLinkedList() state := list.String() t.Log(state) fnAssertTrue(state == "h=nil,t=nil,s=0", "expecting empty list") list.Append(0) state = list.String() t.Log(state) fnAssertTrue(state == "h=0,t=0,s=1,0", "expecting [0]") list.Append(1) state = list.String() t.Log(state) fnAssertTrue(state == "h=0,t=1,s=2,0,1", "expecting [0,1]") e,it := list.Get(0) t.Log(it) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(it == 0, "expecting 0") e,it = list.Get(1) t.Log(it) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(it == 1, "expecting 1") e = list.Set(0, 10) state = list.String() t.Log(state) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(state == "h=10,t=1,s=2,10,1", "expecting [10,1]") e = list.Set(1, 20) state = list.String() t.Log(state) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(state == "h=10,t=20,s=2,10,20", "expecting [10,20]") e = list.Remove(1) state = list.String() t.Log(state) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(state == "h=10,t=10,s=1,10", "expecting [10]") e = list.Remove(0) state = list.String() t.Log(state) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(state == "h=nil,t=nil,s=0", "expecting []") e = list.Insert(0, 0) state = list.String() t.Log(state) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(state == "h=0,t=0,s=1,0", "expecting [0]") e = list.Insert(1, 1) state = list.String() t.Log(state) fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(state == "h=0,t=1,s=2,0,1", "expecting [0,1]") e = list.Insert(3, 3) t.Log(e) fnAssertTrue(e != nil, "expecting e != nil") e = list.Insert(-1, -1) t.Log(e) fnAssertTrue(e != nil, "expecting e != nil") items := make([]string, 0) for iter := list.Iterator();iter.More(); { e,v := iter.Next() fnAssertTrue(e == nil, "expecting e == nil") items = append(items, fmt.Sprintf("%v", v)) } state = strings.Join(items, ",") t.Log(state) fnAssertTrue(state == "0,1", "expecting [0,1]")}测试输入
$ go test -v linked_list_test.go === RUN Test_LinkedList linked_list_test.go:19: h=nil,t=nil,s=0 linked_list_test.go:24: h=0,t=0,s=1,0 linked_list_test.go:29: h=0,t=1,s=2,0,1 linked_list_test.go:33: 0 linked_list_test.go:38: 1 linked_list_test.go:44: h=10,t=1,s=2,10,1 linked_list_test.go:50: h=10,t=20,s=2,10,20 linked_list_test.go:56: h=10,t=10,s=1,10 linked_list_test.go:62: h=nil,t=nil,s=0 linked_list_test.go:68: h=0,t=0,s=1,0 linked_list_test.go:74: h=0,t=1,s=2,0,1 linked_list_test.go:79: index out of bounds linked_list_test.go:83: index out of bounds linked_list_test.go:93: 0,1--- PASS: Test_LinkedList (0.00s)PASSok command-line-arguments 0.002sILinkedList.go
链表接口
package linked_listtype ILinkedList interface { Size() int IsEmpty() bool IsNotEmpty() bool Get(i int) (error,interface{}) Set(i int, it interface{}) error Append(it interface{}) Remove(i int) error Insert(i int, it interface{}) error Iterator() IListIterator String() string}IListIterator.go
链表迭代器接口
package linked_listtype IListIterator interface { More() bool Next() (error,interface{})}tLinkedList.go
链表, 实现ILinkedList接口
package linked_listimport ( "errors" "fmt" "strings")type tLinkedList struct { head *tLinkedNode tail *tLinkedNode size int}type tLinkedNode struct { value interface{} next *tLinkedNode}var gIndexOutofBoundsError = errors.New("index out of bounds")func NewLinkedList() ILinkedList { return &tLinkedList{ head: nil, tail: nil, size: 0, }}func newLinkedNode(value interface{}) *tLinkedNode { return &tLinkedNode{ value,nil, }}func (me *tLinkedList) Size() int { return me.size}func (me *tLinkedList) IsEmpty() bool { return me.size <= 0}func (me *tLinkedList) IsNotEmpty() bool { return !me.IsEmpty()}func (me *tLinkedList) Get(i int) (error,interface{}) { e,_,node := me.getNodeAt(i) if e != nil { return e, nil } return e,node.value}func (me *tLinkedList) getNodeAt(i int) (err error, prev *tLinkedNode, node *tLinkedNode) { if i >= me.size || i < 0 { return gIndexOutofBoundsError, nil, nil } n := 0 prev = nil node = me.head for { if n >= i { return nil, prev, node } if node == nil { return gIndexOutofBoundsError, nil, nil } n++ prev = node node = node.next }}func (me *tLinkedList) Set(i int, value interface{}) error { e,prev,node := me.getNodeAt(i) if e != nil { return e } nn := newLinkedNode(value) if prev == nil { me.head = nn } else { prev.next = nn } nn.next = node.next if nn.next == nil { me.tail = nn } return nil}func (me *tLinkedList) Append(value interface{}) { nn := newLinkedNode(value) t := me.tail if t == nil { me.head = nn } else { t.next = nn } me.tail = nn me.size++}func (me *tLinkedList) Remove(i int) error { e,prev,node := me.getNodeAt(i) if e != nil { return e } if prev != nil { prev.next = node.next } else { me.head = node.next } if node.next == nil { me.tail = prev } else { me.tail = node.next } me.size-- return nil}func (me *tLinkedList) Insert(i int, value interface{}) error { nn := newLinkedNode(value) if i == me.size { // always allow inserting tail t := me.tail me.tail = nn if t != nil { t.next = nn } if me.head == nil { me.head = nn } me.size++ return nil } e,prev,node := me.getNodeAt(i) if e != nil { return e } if prev == nil { me.head = nn } else { prev.next = nn } nn.next = node me.size++ return nil}func (me *tLinkedList) Iterator() IListIterator { items := make([]interface{}, me.size) i := 0 for node := me.head;; { if node == nil { break } items[i] = node.value node = node.next i++ } return newListIterator(items)}func (me *tLinkedList) String() string { items := make([]string, 0) if me.head == nil { items = append(items, "h=nil") } else { items = append(items, fmt.Sprintf("h=%v", me.head.value)) } if me.tail == nil { items = append(items, "t=nil") } else { items = append(items, fmt.Sprintf("t=%v", me.tail.value)) } items = append(items, fmt.Sprintf("s=%v", me.size)) for node:=me.head;node != nil; { items = append(items, fmt.Sprintf("%v", node.value)) node = node.next } return strings.Join(items, ",")}tListIterator.go
链表迭代器, 实现IListIterator接口
package linked_listtype tListIterator struct { items []interface{} count int pos int}func newListIterator(items []interface{}) IListIterator { size := len(items) copy := make([]interface{}, size) for i,it := range items { copy[i] = it } return &tListIterator{ items: copy, count: size, pos: 0, }}func (me *tListIterator) More() bool { return me.pos < me.count}func (me *tListIterator) Next() (error,interface{}) { if me.pos >= me.count { return gIndexOutofBoundsError, nil } n := me.pos me.pos++ return nil, me.items[n]}(end)