介绍
所谓链表（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()
}
)
