golang基本數(shù)據(jù)結(jié)構(gòu)與算法之如何使用鏈表

這篇文章主要介紹“golang基本數(shù)據(jù)結(jié)構(gòu)與算法之如何使用鏈表”，在日常操作中，相信很多人在golang基本數(shù)據(jù)結(jié)構(gòu)與算法之如何使用鏈表問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”golang基本數(shù)據(jù)結(jié)構(gòu)與算法之如何使用鏈表”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

鏈表

鏈表是數(shù)據(jù)結(jié)構(gòu)之一，其中的數(shù)據(jù)呈線性排列。
每個(gè)數(shù)據(jù)節(jié)點(diǎn)都有1個(gè)“指針”，它指向下一個(gè)數(shù)據(jù)的內(nèi)存地址。

訪問數(shù)據(jù)時(shí)，我們需要從鏈表頭部開始查找（線性查找），
如果目標(biāo)數(shù)據(jù)在鏈表最后的話，需要的時(shí)間就是O(n)。

另外，添加數(shù)據(jù)只需要更改兩個(gè)指針的指向，所以耗費(fèi)的時(shí)間與n無關(guān)。
如果已經(jīng)到達(dá)了添加數(shù)據(jù)的位置，那么添加操作只需花費(fèi)O(1)的時(shí)間。
刪除數(shù)據(jù)同樣也只需O(1)的時(shí)間。

摘自 <<我的第一本算法書>>(【日】石田保輝；宮崎修一)

目標(biāo)

• 實(shí)現(xiàn)一個(gè)鏈表, 提供與數(shù)組類似的線性訪問接口

設(shè)計(jì)

• ILinkedList: 鏈表接口

• IListIterator: 鏈表迭代器接口

• tLinkedList: 鏈表, 實(shí)現(xiàn)ILinkedList接口

• tListIterator: 鏈表迭代器, 實(shí)現(xiàn)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

鏈表, 實(shí)現(xiàn)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

鏈表迭代器, 實(shí)現(xiàn)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]
}

到此，關(guān)于“golang基本數(shù)據(jù)結(jié)構(gòu)與算法之如何使用鏈表”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！