# Go數據結構：鍊錶

## 執行

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

``````// Package linkedlist creates a ItemLinkedList data structure for the Item type
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
}
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}
} else {
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”)
}
if i == 0 {
return nil
}
j := 0
for j < i-2 {
j++
node = node.next
}
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”)
}
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()
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()
return true
}
return false
}
// Size returns the linked list size
func (ll *ItemLinkedList) Size() int {
ll.lock.RLock()
defer ll.lock.RUnlock()
size := 1
for {
if last == nil || last.next == nil {
break
}
last = last.next
size++
}
return size
}
// Insert adds an Item at position i
ll.lock.RLock()
defer ll.lock.RUnlock()
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
ll.lock.RLock()
defer ll.lock.RUnlock()
}``````

## 測驗

``````package linkedlist
import (
“fmt”
“testing”
)
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)
}
}
ll.Append(“zero”)
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