golang基本数据结构与算法之如何使用链表
这篇文章主要介绍“golang基本数据结构与算法之如何使用链表”,在日常操作中,相信很多人在golang基本数据结构与算法之如何使用链表问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”golang基本数据结构与算法之如何使用链表”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
链表
链表是数据结构之一,其中的数据呈线性排列。 每个数据节点都有1个“指针”,它指向下一个数据的内存地址。 访问数据时,我们需要从链表头部开始查找(线性查找), 如果目标数据在链表最后的话,需要的时间就是O(n)。 另外,添加数据只需要更改两个指针的指向,所以耗费的时间与n无关。 如果已经到达了添加数据的位置,那么添加操作只需花费O(1)的时间。 删除数据同样也只需O(1)的时间。 摘自 <<我的第一本算法书>>(【日】石田保辉;宫崎修一)
目标
实现一个链表, 提供与数组类似的线性访问接口
设计
ILinkedList: 链表接口
IListIterator: 链表迭代器接口
tLinkedList: 链表, 实现ILinkedList接口
tListIterator: 链表迭代器, 实现IListIterator接口
单元测试
linked_list_test.go
package data_structure import ( "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) PASS ok command-line-arguments 0.002s
ILinkedList.go
链表接口
package linked_list type 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_list type IListIterator interface { More() bool Next() (error,interface{}) }
tLinkedList.go
链表, 实现ILinkedList接口
package linked_list import ( "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_list type 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] }
到此,关于“golang基本数据结构与算法之如何使用链表”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注网站,小编会继续努力为大家带来更多实用的文章!