链表是数据元素的线性集合,其顺序不是由它们在内存中的物理位置给出的。相反,每个元素指向下一个元素。它是一个由节点集合组成的数据结构,这些节点一起表示一个序列。在其最基本的形式中,每个节点包含:数据和引用(换句话说,链接)到序列中的下一个节点。该结构允许在迭代期间从序列中的任何位置有效地插入或移除元素。更复杂的变体添加了额外的链接,允许在任意位置更有效地插入或移除节点。链表的缺点是访问时间是线性的(并且难以管道化)。更快的访问,例如随机访问,是不可行的。与链表相比,数组具有更好的缓存局部性。

实现

链表将提供以下方法:

  • Append(t) 将项目t添加到链接列表的末尾
  • Insert(i, t) 在位置i添加项目t
  • RemoveAt(i) 删除位置i的节点
  • IndexOf() 返回Item t的位置
  • IsEmpty() 如果列表为空,则返回true
  • Size() 返回链表大小
  • String() 返回列表的字符串表示形式
  • Head() 返回第一个节点,因此我们可以迭代它

我将创建一个LinkedList通用类型,并发安全,可以生成包含任何类型的链表,创建特定于类型的链表实现,封装包含数据的实际值特定数据结构。

// 队列中Item的类型
type Type interface{}

// 队列中的Item
type Item Type
import (
    "fmt"
    "sync"
)

//存放当前content和下一个Node信息
type Node struct {
    content Item
    next    *Node
}

// 一个存放元素Items的LinkedList
type LinkedList struct {
    head *Node
    size int
    lock sync.RWMutex
}

// 添加元素到队尾
func (ll *LinkedList) Append(t Item) {
    ll.lock.Lock()
    node := Node{t, nil}
    if ll.head == nil { //空链表
        ll.head = &node
    } else {
        last := ll.head
        for { //找到最后一个Node
            if last.next == nil {
                break
            }
            last = last.next
        }
        last.next = &node
    }
    ll.size++
    ll.lock.Unlock()
}

// 插入元素到索引位置为i的位置
func (ll *LinkedList) 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 { //找到索引位置为i-1的Node
        j++
        node = node.next
    }
    addNode.next = node.next
    node.next = &addNode
    ll.size++
    return nil
}

// 删除并返回索引位置为i的元素
func (ll *LinkedList) 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 { //找到位置为i上的Node
        j++
        node = node.next
    }
    remove := node.next
    node.next = remove.next
    ll.size--
    return &remove.content, nil
}

// 获取指定元素在链表中的索引
func (ll *LinkedList) 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 { //找到最后一个Node还是未找到
            return -1
        }
        node = node.next
        j++
    }
}

// 返回链表是否为空
func (ll *LinkedList) IsEmpty() bool {
    ll.lock.RLock()
    defer ll.lock.RUnlock()
    if ll.head == nil {
        return true
    }
    return false
}

// 返回链表的大小
func (ll *LinkedList) 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
}

// 打印列表的字符串表示形式
func (ll *LinkedList) 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()
}

// 返回链表中头结点的Node
func (ll *LinkedList) Head() *Node {
    ll.lock.RLock()
    defer ll.lock.RUnlock()
    return ll.head
}

测试

测试上面公开的方法

import (
    "fmt"
    "testing"
)

var ll LinkedList


func 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)
    }
    ll.String()
}

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)
    }
    ll.String()
}

func TestInsert(t *testing.T) {
    //test inserting in the middle
    ll.Insert(0, "zero")
    ll.Insert(1, "first")
    ll.Insert(2, "second")
    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)
    }
    ll.String()
}

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)
    }
    ll.String()
}

func TestHead(t *testing.T) {
    h := ll.Head()
    if "zero" != fmt.Sprint(h.content) {
        t.Errorf("Expected `zero` but got %s", fmt.Sprint(h.content))
    }
    ll.String()
}