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