golang基本数据结构与算法之如何使用链表

这篇文章主要介绍"golang基本数据结构与算法之如何使用链表"，在日常操作中，相信很多人在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.002s

ILinkedList.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]}

到此，关于"golang基本数据结构与算法之如何使用链表"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！