Go數據結構:鍊錶

Go中鍊錶數據結構的分析與實現

鍊錶提供了類似於數組的數據結構,但具有的一大優勢是,與在數組中插入元素相比,在列表中間插入元素非常便宜,在數組中我們需要將所有元素移到當前位置之後。

數組將所有元素都保留在同一塊內存中時,彼此相鄰,而鏈接列表可以通過存儲指向下一個元素的指針來包含散佈在內存中的元素。

另一方面,相對於數組的缺點是,如果我們想在列表中間選擇一個元素,我們不知道其地址,因此我們需要從列表的開頭開始,並在列表上進行迭代,直到我們找到了。

執行

鍊錶將提供以下方法:

  • Append(t)將項目t添加到鏈接列表的末尾
  • Insert(i, t)在位置i上添加項目t
  • RemoveAt(i)刪除位置i處的節點
  • IndexOf()返回項目t的位置
  • IsEmpty()如果列表為空,則返回true
  • Size()返回鍊錶的大小
  • String()返回列表的字符串表示形式
  • Head()返回第一個節點,因此我們可以對其進行迭代

我將創建一個ItemLinkedList泛型類型,並發安全,可以通過使用生成包含任何類型的鏈接列表genny,以創建特定於類型的鍊錶實現,封裝包含數據的實際特定於值的數據結構。

// Package linkedlist creates a ItemLinkedList data structure for the Item type
package linkedlist

import ( “fmt” “sync”

<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>

)

// Item the type of the linked list type Item generic.Type

// Node a single node that composes the list type Node struct { content Item next *Node }

// ItemLinkedList the linked list of Items type ItemLinkedList struct { head *Node size int lock sync.RWMutex }

// Append adds an Item to the end of the linked list func (ll *ItemLinkedList) Append(t Item) { ll.lock.Lock() node := Node{t, nil} if ll.head == nil { ll.head = &node } else { last := ll.head for { if last.next == nil { break } last = last.next } last.next = &node } ll.size++ ll.lock.Unlock() }

// Insert adds an Item at position i func (ll *ItemLinkedList) Insert(i int, t Item) error { ll.lock.Lock() defer ll.lock.Unlock() if i < 0 || i > ll.size { return fmt.Errorf(“Index out of bounds”) } addNode := Node{t, nil} if i == 0 { addNode.next = ll.head ll.head = &addNode return nil } node := ll.head j := 0 for j < i-2 { j++ node = node.next } addNode.next = node.next node.next = &addNode ll.size++ return nil }

// RemoveAt removes a node at position i func (ll ItemLinkedList) RemoveAt(i int) (Item, error) { ll.lock.Lock() defer ll.lock.Unlock() if i < 0 || i > ll.size { return nil, fmt.Errorf(“Index out of bounds”) } node := ll.head j := 0 for j < i-1 { j++ node = node.next } remove := node.next node.next = remove.next ll.size return &remove.content, nil }

// IndexOf returns the position of the Item t func (ll *ItemLinkedList) IndexOf(t Item) int { ll.lock.RLock() defer ll.lock.RUnlock() node := ll.head j := 0 for { if node.content == t { return j } if node.next == nil { return -1 } node = node.next j++ } }

// IsEmpty returns true if the list is empty func (ll *ItemLinkedList) IsEmpty() bool { ll.lock.RLock() defer ll.lock.RUnlock() if ll.head == nil { return true } return false }

// Size returns the linked list size func (ll *ItemLinkedList) Size() int { ll.lock.RLock() defer ll.lock.RUnlock() size := 1 last := ll.head for { if last == nil || last.next == nil { break } last = last.next size++ } return size }

// Insert adds an Item at position i func (ll *ItemLinkedList) String() { ll.lock.RLock() defer ll.lock.RUnlock() node := ll.head j := 0 for { if node == nil { break } j++ fmt.Print(node.content) fmt.Print(" ") node = node.next } fmt.Println() }

// Head returns a pointer to the first node of the list func (ll ItemLinkedList) Head() Node { ll.lock.RLock() defer ll.lock.RUnlock() return ll.head }

測驗

這些測試描述了上述實現的用法。

package linkedlist

import ( “fmt” “testing” )

var ll ItemLinkedList

func TestAppend(t *testing.T) { if !ll.IsEmpty() { t.Errorf(“list should be empty”) }

<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"first"</span>)
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">IsEmpty</span>() {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"list should not be empty"</span>)
}

<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">1</span> {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 1 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}

<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"second"</span>)
<span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Append</span>(<span style="color:#e6db74">"third"</span>)

<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">3</span> {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 3 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}

}

func TestRemoveAt(t *testing.T) { _, err := ll.RemoveAt(1) if err != nil { t.Errorf(“unexpected error %s”, err) }

<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">ll</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">2</span> {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 2 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}

}

func TestInsert(t *testing.T) { //test inserting in the middle err := ll.Insert(2, “second2”) if err != nil { t.Errorf(“unexpected error %s”, err) } if size := ll.Size(); size != 3 { t.Errorf(“wrong count, expected 3 and got %d”, size) }

<span style="color:#75715e">//test inserting at head position

err = ll.Insert(0, “zero”) if err != nil { t.Errorf(“unexpected error %s”, err) } }

func TestIndexOf(t *testing.T) { if i := ll.IndexOf(“zero”); i != 0 { t.Errorf(“expected position 0 but got %d”, i) } if i := ll.IndexOf(“first”); i != 1 { t.Errorf(“expected position 1 but got %d”, i) } if i := ll.IndexOf(“second2”); i != 2 { t.Errorf(“expected position 2 but got %d”, i) } if i := ll.IndexOf(“third”); i != 3 { t.Errorf(“expected position 3 but got %d”, i) } }

func TestHead(t *testing.T) { ll.Append(“zero”) h := ll.Head() if “zero” != fmt.Sprint(h.content) { t.Errorf(“Expected zero but got %s”, fmt.Sprint(h.content)) } }

創建一個具體的鍊錶數據結構

您可以使用以下通用實現來生成特定於類型的鏈接列表,方法是:

//generate a `IntLinkedList` linked list of `int` values
genny -in linkedlist.go -out linkedlist-int.go gen "Item=int"

//generate a </span>StringLinkedList<span style="color:#e6db74"> linked list of </span>string<span style="color:#e6db74"> values genny -in linkedlist.go -out linkedlist-string.go gen “Item=string”


更多教程: