关于算法:手撸golang-基本数据结构与算法-链表

4次阅读

共计 6251 个字符，预计需要花费 16 分钟才能阅读完成。

最近浏览 << 我的第一本算法书 >>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳 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]
}

(end)

正文完

算法

发表至：算法

2021-02-15

0

关于算法:ACS130-C语言算法项目题

关于算法:R语言动态可视化制作历史全球平均温度的累积动态折线图动画gif视频图

关于算法:图像倾斜校正算法的MATLAB实现图像倾斜角检测及校正

关于算法:有了这个算法图像上文字擦除再也用不上PS了

关于源码分析:react为何采用fiber架构

关于算法:手撸golang-基本数据结构与算法-链表

手撸 golang 根本数据结构与算法链表

缘起

链表

指标

设计

单元测试

测试输入

ILinkedList.go

IListIterator.go

tLinkedList.go

tListIterator.go

站内搜索

关于算法:手撸golang-基本数据结构与算法-链表

手撸 golang 根本数据结构与算法 链表

缘起

链表

指标

设计

单元测试

测试输入

ILinkedList.go

IListIterator.go

tLinkedList.go

tListIterator.go

站内搜索

手撸 golang 根本数据结构与算法链表