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

介绍

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

实现

逻辑方法

我们定义链表的结构体：

// LinkedList the linked list struct
type LinkedList struct {sync.RWMutexhead *Nodesize int
}// Node a single node that composes the list
type Node struct {content Tnext    *Node
}

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

• 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.headfor {if last.next == nil {break}last = last.next}last.next = node}l.size++
}

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

// Insert adds t at position pos
func (l *LinkedList) Insert(t T, pos int) error {l.Lock()defer l.Unlock()// validate positionif 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.headl.head = nodereturn nil}head := l.headidx := 0for idx < pos-2 {idx++head = head.next}node.next = head.nexthead.next = nodel.size++return nil
}

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

// RemoveAt removes a node at position pos
func (l *LinkedList) RemoveAt(pos int) (*T, error) {l.Lock()defer l.Unlock()// validate positionif pos < 0 || pos > l.size {return nil, fmt.Errorf("insert position must be larger than 0 and smaller than linked list size")}head := l.headidx := 0for idx < pos-1 {idx++head = head.next}next := head.nexthead.next = next.nextl.size--return &next.content, nil
}

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

// IndexOf returns the position of the t
func (l *LinkedList) IndexOf(t T) int {l.RLock()defer l.RUnlock()head := l.headidx := 0for {if head.content == t {return idx}if head.next == nil {return -1}head = head.nextidx++}
}// 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
}

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

// Traverse traverses linked list
func (l *LinkedList) Traverse() {l.RLock()defer l.RUnlock()head := l.headfor {if head == nil {break}head.Print()head = head.next}fmt.Println()
}

单元测试

单元测试如下：

import "testing"var (t1 T = 1t2 T = 2t3 T = 3t4 T = 4
)func InitLinkedList() *LinkedList {list := NewLinkedList()list.head = NewNode(t1)list.head.next = NewNode(t2)list.head.next.next = NewNode(t3)list.size = 3return 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()
}