Go中鍊錶數據結構的分析與實現
鍊錶提供了類似於數組的數據結構,但具有的一大優勢是,與在數組中插入元素相比,在列表中間插入元素非常便宜,在數組中我們需要將所有元素移到當前位置之後。
數組將所有元素都保留在同一塊內存中時,彼此相鄰,而鏈接列表可以通過存儲指向下一個元素的指針來包含散佈在內存中的元素。
另一方面,相對於數組的缺點是,如果我們想在列表中間選擇一個元素,我們不知道其地址,因此我們需要從列表的開頭開始,並在列表上進行迭代,直到我們找到了。
執行
鍊錶將提供以下方法:
Append(t)
將項目t添加到鏈接列表的末尾Insert(i, t)
在位置i上添加項目tRemoveAt(i)
刪除位置i處的節點IndexOf()
返回項目t的位置IsEmpty()
如果列表為空,則返回trueSize()
返回鍊錶的大小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”
更多教程:
- 使用NGINX反向代理服務Go服務
- 在Go中復制結構
- Go Web服務器的基礎
- 在Go中對地圖類型進行排序
- 簡而言之去指針
- 轉到標籤說明
- 開始日期和時間格式
- 使用Go進行JSON處理
- 可變參數函數
- 去弦備忘單
- 轉到空界面說明
- 使用VS Code和Delve調試Go
- 命名為Go返回參數
- 在Go中生成隨機數和字符串
- Go項目的文件系統結構
- Go中的二進制搜索算法
- 在Go中使用命令行標誌
- GOPATH解釋
- 使用Go構建一個命令行應用程序:lolcat
- 使用Go構建CLI命令:Cowsay
- 在Go中使用殼管
- Go CLI教程:財富克隆
- 使用Go列出文件夾中的文件
- 使用Go從GitHub獲取存儲庫列表
- 去,將一小段字符串附加到文件中
- 去,將字符串轉換為字節片
- 使用Go可視化您本地的Git貢獻
- Go CPU和內存分析入門
- 解決Go程序中的“不支持索引”錯誤
- 測量Go程序中的執行時間
- 使用Go構建Web爬網程序以檢測重複的標題
- 最佳實踐:指針還是價值接收者?
- 最佳實踐:您應該使用方法還是函數?
- Go數據結構:集
- 前往地圖備忘單
- 在Go中生成泛型類型的實現
- Go數據結構:字典
- Go數據結構:哈希表
- 在“通過通道”中實現事件偵聽器
- Go數據結構:堆棧
- Go數據結構:隊列
- Go數據結構:二進制搜索樹
- Go數據結構:圖形
- Go數據結構:鍊錶
- Go數據結構的完整指南
- 比較Go值
- Go是面向對象的嗎?
- 在Go中使用SQL數據庫
- 在Go中使用環境變量
- 上篇教程:PostgreSQL支持的REST API
- 在Go Web服務器上啟用CORS
- 在Docker容器中部署Go應用程序
- 為什麼Go是作為PHP開發人員學習的功能強大的語言
- 去,刪除io.Reader.ReadString換行符
- 開始,如何觀看更改並重建程序
- 去算一下自約會以來的月份
- 在Go中訪問HTTP POST參數