本文共 7164 字，大约阅读时间需要 23 分钟。
A linked list provides a data structure similar to an array, but with the big advantage that inserting an element in the middle of the list is very cheap, compared to doing so in an array, where we need to shift all elements after the current position.
链表提供了类似于数组的数据结构，但具有的一大优势是，与在数组中插入元素相比，在列表中间插入元素非常便宜，在数组中我们需要将所有元素移到当前位置之后。
While arrays keep all the elements in the same block of memory, next to each other, linked lists can contain elements scattered around memory, by storing a pointer to the next element.
数组将所有元素都保留在同一块内存中时，彼此相邻，而链接列表可以通过存储指向下一个元素的指针来包含分散在内存中的元素。
A disadvantage over arrays on the other hand is that if we want to pick an element in the middle of the list, we don’t know its address, so we need to start at the beginning of the list, and iterate on the list until we find it.
另一方面，相对于数组的缺点是，如果我们想在列表的中间选择一个元素，我们不知道其地址，因此我们需要从列表的开头开始，并在列表上进行迭代直到我们找到了。
A linked list will provide these methods:
链表将提供以下方法：
Append(t) adds an Item t to the end of the linked list
Append(t)将Item t添加到链接列表的末尾
Insert(i, t) adds an Item t at position i
Insert(i, t)在位置i添加项t
RemoveAt(i) removes a node at position i
RemoveAt(i)删除位置i处的节点
IndexOf() returns the position of the Item t
IndexOf()返回Item t的位置
IsEmpty() returns true if the list is empty
如果列表为空，则IsEmpty()返回true
Size() returns the linked list size
Size()返回链接列表的大小
String() returns a string representation of the list
String()返回列表的字符串表示形式
Head() returns the first node, so we can iterate on it
Head()返回第一个节点，因此我们可以对其进行迭代
I’ll create an ItemLinkedList generic type, concurrency safe, that can generate linked lists containing any type by using genny, to create a type-specific linked list implementation, encapsulating the actual value-specific data structure containing the data.
我将创建一个ItemLinkedList泛型类型，并发安全的，可以生成包含任何类型的使用链表genny ，创造一种特定的链表实现，封装包含数据的实际值特定的数据结构。
// Package linkedlist creates a ItemLinkedList data structure for the Item typepackage linkedlistimport ( "fmt" "sync" "github.com/cheekybits/genny/generic")// Item the type of the linked listtype Item generic.Type// Node a single node that composes the listtype Node struct { content Item next *Node}// ItemLinkedList the linked list of Itemstype ItemLinkedList struct { head *Node size int lock sync.RWMutex}// Append adds an Item to the end of the linked listfunc (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 ifunc (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 ifunc (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 tfunc (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 emptyfunc (ll *ItemLinkedList) IsEmpty() bool { ll.lock.RLock() defer ll.lock.RUnlock() if ll.head == nil { return true } return false}// Size returns the linked list sizefunc (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 ifunc (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 listfunc (ll *ItemLinkedList) Head() *Node { ll.lock.RLock() defer ll.lock.RUnlock() return ll.head} The tests describe the usage of the above implementation.
这些测试描述了上述实现的用法。
package linkedlistimport ( "fmt" "testing")var ll ItemLinkedListfunc TestAppend(t *testing.T) { if !ll.IsEmpty() { t.Errorf("list should be empty") } ll.Append("first") if ll.IsEmpty() { t.Errorf("list should not be empty") } if size := ll.Size(); size != 1 { t.Errorf("wrong count, expected 1 and got %d", size) } ll.Append("second") ll.Append("third") if size := ll.Size(); size != 3 { t.Errorf("wrong count, expected 3 and got %d", size) }}func TestRemoveAt(t *testing.T) { _, err := ll.RemoveAt(1) if err != nil { t.Errorf("unexpected error %s", err) } if size := ll.Size(); size != 2 { t.Errorf("wrong count, expected 2 and got %d", size) }}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) } //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)) }} You can use this generic implemenation to generate type-specific linked lists, using
您可以使用以下通用实现来生成特定于类型的链接列表，方法是：
//generate a `IntLinkedList` linked list of `int` valuesgenny -in linkedlist.go -out linkedlist-int.go gen "Item=int"//generate a `StringLinkedList` linked list of `string` valuesgenny -in linkedlist.go -out linkedlist-string.go gen "Item=string"
翻译自:
转载地址：http://yeqgb.baihongyu.com/