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

介绍

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

实现

逻辑方法

我们定义链表的结构体：

// LinkedList the linked list struct
type LinkedList struct {
   sync.RWMutex
   head *Node
   size int
}

// Node a single node that composes the list
type Node struct {
   content T
   next    *Node
}
1
2
3
4
5
6
7
8
9
10
11
12

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

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

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

// Add adds t to the end of the linked list
func (l *LinkedList) Add(t T) {
   l.Lock()
   defer l.Unlock()

   node := NewNode(t)
   if l.head == nil {
      l.head = node
   } else {
      last := l.head
      for {
         if last.next == nil {
            break
         }
         last = last.next
      }
      last.next = node
   }
   l.size++
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

// Insert adds t at position pos
func (l *LinkedList) Insert(t T, pos int) error {
   l.Lock()
   defer l.Unlock()

   // validate position
   if pos < 0 || pos > l.size {
      return fmt.Errorf("insert position must be larger than 0 and smaller than linked list size")
   }

   node := NewNode(t)
   if pos == 0 {
      node.next = l.head
      l.head = node
      return nil
   }

   head := l.head
   idx := 0
   for idx < pos-2 {
      idx++
      head = head.next
   }

   node.next = head.next
   head.next = node
   l.size++
   return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

// RemoveAt removes a node at position pos
func (l *LinkedList) RemoveAt(pos int) (*T, error) {
   l.Lock()
   defer l.Unlock()

   // validate position
   if pos < 0 || pos > l.size {
      return nil, fmt.Errorf("insert position must be larger than 0 and smaller than linked list size")
   }

   head := l.head
   idx := 0
   for idx < pos-1 {
      idx++
      head = head.next
   }
   next := head.next
   head.next = next.next
   l.size--
   return &next.content, nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

// IndexOf returns the position of the t
func (l *LinkedList) IndexOf(t T) int {
   l.RLock()
   defer l.RUnlock()

   head := l.head
   idx := 0
   for {
      if head.content == t {
         return idx
      }
      if head.next == nil {
         return -1
      }
      head = head.next
      idx++
   }
}

// IsEmpty returns true if the list is empty
func (l *LinkedList) IsEmpty() bool {
   l.RLock()
   defer l.RUnlock()

   return l.head == nil
}

// Size returns the linked list size
func (l *LinkedList) Size() int {
   l.RLock()
   defer l.RUnlock()

   return l.size
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

// Traverse traverses linked list
func (l *LinkedList) Traverse() {
   l.RLock()
   defer l.RUnlock()

   head := l.head
   for {
      if head == nil {
         break
      }

      head.Print()
      head = head.next
   }
   fmt.Println()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

单元测试

单元测试如下：

import "testing"

var (
   t1 T = 1
   t2 T = 2
   t3 T = 3
   t4 T = 4
)

func InitLinkedList() *LinkedList {
   list := NewLinkedList()
   list.head = NewNode(t1)
   list.head.next = NewNode(t2)
   list.head.next.next = NewNode(t3)
   list.size = 3

   return list
}

func TestLinkedList_Add(t *testing.T) {
   linkedList := InitLinkedList()
   size := linkedList.Size()

   if size != 3 {
      t.Errorf("linked list size should be 3 but got %d", size)
   }

   linkedList.Add(4)
   size = linkedList.Size()
   if size != 4 {
      t.Errorf("linked list size should be 4 but got %d", size)
   }
}

func TestLinkedList_Insert(t *testing.T) {
   linkedList := InitLinkedList()

   err := linkedList.Insert(t4, 1)
   if err != nil {
      t.Errorf("insert into linked list err %v", err)
   }

   idx1 := linkedList.IndexOf(t2)
   idx2 := linkedList.IndexOf(t4)
   if idx1 != 2 || idx2 != 1 {
      t.Errorf("linked list position is not expected.")
   }
}

func TestLinkedList_RemoveAt(t *testing.T) {
   linkedList := InitLinkedList()

   ret, err := linkedList.RemoveAt(2)
   if err != nil {
      t.Errorf("linked list err %v", err)
   }
   if *ret != t3 {
      t.Errorf("removed item expect 3 but got %d", *ret)
   }

   size := linkedList.Size()
   if size != 2 {
      t.Errorf("linked list size should be 2 but got %d", size)
   }
}

func TestLinkedList_IsEmpty(t *testing.T) {
   linkedList := InitLinkedList()

   empty := linkedList.IsEmpty()
   if empty {
      t.Errorf("linked list is not empty.")
   }

   linkedList = &LinkedList{}
   empty = linkedList.IsEmpty()
   if !empty {
      t.Errorf("linked list is empty.")
   }
}

func TestLinkedList_Traverse(t *testing.T) {
   linkedList := InitLinkedList()

   linkedList.Traverse()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86