Go的数据结构与实现【LinkedList】

先容

所谓链表（Linked List），就是按线性序次分列的一组数据节点。每个节点都是一个对象，它通过一个引用指向对应的数据元素，同时还通过一个引用next指向下一节点。
实现

逻辑方法

我们界说链表的结构体：

1. // LinkedList the linked list struct
2. type LinkedList struct {
3.    sync.RWMutex
4.    head *Node
5.    size int
6. }
8. // Node a single node that composes the list
9. type Node struct {
10.    content T
11.    next    *Node
12. }

复制代码

此中包罗头节点和链表长度，在这里我们重要实现以下方法：

• Add：添加一个元素到链表末端
  
• Insert：向链表指定位置插入元素
  
• RemoveAt：移除指定索引位置的元素
  
• IndexOf：取指定索引位置的元素
  
• IsEmpty：判定链表是否为空
  
• Size：获取链表长度
  
• Traverse：遍历链表并输出
  

起首是Add方法，判定链表头节点是否为空，若空则设置头节点为插入的元素，若非空，找到链表末端节点，再插入元素。

1. // Add adds t to the end of the linked list
2. func (l *LinkedList) Add(t T) {
3.    l.Lock()
4.    defer l.Unlock()
6.    node := NewNode(t)
7.    if l.head == nil {
8.       l.head = node
9.    } else {
10.       last := l.head
11.       for {
12.          if last.next == nil {
13.             break
14.          }
15.          last = last.next
16.       }
17.       last.next = node
18.    }
19.    l.size++
20. }

复制代码

Insert方法，注意判定索引位置是否合法，再插入指定位置。

1. // Insert adds t at position pos
2. func (l *LinkedList) Insert(t T, pos int) error {
3.    l.Lock()
4.    defer l.Unlock()
6.    // validate position
7.    if pos < 0 || pos > l.size {
8.       return fmt.Errorf("insert position must be larger than 0 and smaller than linked list size")
9.    }
11.    node := NewNode(t)
12.    if pos == 0 {
13.       node.next = l.head
14.       l.head = node
15.       return nil
16.    }
18.    head := l.head
19.    idx := 0
20.    for idx < pos-2 {
21.       idx++
22.       head = head.next
23.    }
25.    node.next = head.next
26.    head.next = node
27.    l.size++
28.    return nil
29. }

复制代码

RemoveAt方法与之类似，判定索引位置是否合法再移除。

1. // RemoveAt removes a node at position pos
2. func (l *LinkedList) RemoveAt(pos int) (*T, error) {
3.    l.Lock()
4.    defer l.Unlock()
6.    // validate position
7.    if pos < 0 || pos > l.size {
8.       return nil, fmt.Errorf("insert position must be larger than 0 and smaller than linked list size")
9.    }
11.    head := l.head
12.    idx := 0
13.    for idx < pos-1 {
14.       idx++
15.       head = head.next
16.    }
17.    next := head.next
18.    head.next = next.next
19.    l.size--
20.    return &next.content, nil
21. }

复制代码

剩下的方法直接取相应数据即可。

1. // IndexOf returns the position of the t
2. func (l *LinkedList) IndexOf(t T) int {
3.    l.RLock()
4.    defer l.RUnlock()
6.    head := l.head
7.    idx := 0
8.    for {
9.       if head.content == t {
10.          return idx
11.       }
12.       if head.next == nil {
13.          return -1
14.       }
15.       head = head.next
16.       idx++
17.    }
18. }
20. // IsEmpty returns true if the list is empty
21. func (l *LinkedList) IsEmpty() bool {
22.    l.RLock()
23.    defer l.RUnlock()
25.    return l.head == nil
26. }
28. // Size returns the linked list size
29. func (l *LinkedList) Size() int {
30.    l.RLock()
31.    defer l.RUnlock()
33.    return l.size
34. }

复制代码

遍历方法Traverse还会输出元素内容。

1. // Traverse traverses linked list
2. func (l *LinkedList) Traverse() {
3.    l.RLock()
4.    defer l.RUnlock()
6.    head := l.head
7.    for {
8.       if head == nil {
9.          break
10.       }
12.       head.Print()
13.       head = head.next
14.    }
15.    fmt.Println()
16. }

复制代码

单位测试

单位测试如下：

1. import "testing"
3. var (
4.    t1 T = 1
5.    t2 T = 2
6.    t3 T = 3
7.    t4 T = 4
8. )
10. func InitLinkedList() *LinkedList {
11.    list := NewLinkedList()
12.    list.head = NewNode(t1)
13.    list.head.next = NewNode(t2)
14.    list.head.next.next = NewNode(t3)
15.    list.size = 3
17.    return list
18. }
20. func TestLinkedList_Add(t *testing.T) {
21.    linkedList := InitLinkedList()
22.    size := linkedList.Size()
24.    if size != 3 {
25.       t.Errorf("linked list size should be 3 but got %d", size)
26.    }
28.    linkedList.Add(4)
29.    size = linkedList.Size()
30.    if size != 4 {
31.       t.Errorf("linked list size should be 4 but got %d", size)
32.    }
33. }
35. func TestLinkedList_Insert(t *testing.T) {
36.    linkedList := InitLinkedList()
38.    err := linkedList.Insert(t4, 1)
39.    if err != nil {
40.       t.Errorf("insert into linked list err %v", err)
41.    }
43.    idx1 := linkedList.IndexOf(t2)
44.    idx2 := linkedList.IndexOf(t4)
45.    if idx1 != 2 || idx2 != 1 {
46.       t.Errorf("linked list position is not expected.")
47.    }
48. }
50. func TestLinkedList_RemoveAt(t *testing.T) {
51.    linkedList := InitLinkedList()
53.    ret, err := linkedList.RemoveAt(2)
54.    if err != nil {
55.       t.Errorf("linked list err %v", err)
56.    }
57.    if *ret != t3 {
58.       t.Errorf("removed item expect 3 but got %d", *ret)
59.    }
61.    size := linkedList.Size()
62.    if size != 2 {
63.       t.Errorf("linked list size should be 2 but got %d", size)
64.    }
65. }
67. func TestLinkedList_IsEmpty(t *testing.T) {
68.    linkedList := InitLinkedList()
70.    empty := linkedList.IsEmpty()
71.    if empty {
72.       t.Errorf("linked list is not empty.")
73.    }
75.    linkedList = &LinkedList{}
76.    empty = linkedList.IsEmpty()
77.    if !empty {
78.       t.Errorf("linked list is empty.")
79.    }
80. }
82. func TestLinkedList_Traverse(t *testing.T) {
83.    linkedList := InitLinkedList()
85.    linkedList.Traverse()
86. }

复制代码