这篇文章主要介绍“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
链表接口
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
}链表迭代器接口
package linked_list
type IListIterator interface {
More() bool
Next() (error,interface{})
}链表, 实现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, ",")
}链表迭代器, 实现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基本数据结构与算法之如何使用链表”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
