手撸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]
}
(end)
