/ Go 语言列表 List 使用指南 /
Go 语言中并没有内置的列表 List 类型,但可以通过 slice、数组或链表实现列表功能。合理实现列表可以解决很多实际编码问题。
本文将全面介绍如何在 Go 语言中实现列表,内容涵盖
- 数组实现列表
- 切片实现列表
- 链表实现灵活列表
- 列表基本操作实现
- 线程安全列表
- 常见算法实现
- 列表与切片区别
- 应用场景
1
1. 数组实现列表
可以使用数组来实现简单的列表:
// 定义一个最大长度为100的int列表 var list [100]int // 加入两个元素 list[0] = 1 list[1] = 2 // 读取第一个元素 v := list[0] // 遍历数组列表 for i := 0; i < len(list); i++ { v := list[i] fmt.Println(v) }
数组实现的列表长度是固定的,删除元素后会留下空洞,无法动态缩容。
再来看一个例子:
// 定义一个最大长度为3的字符串列表 var strList [3]string // 尾部追加元素 strList[0] = "foo" strList[1] = "bar" // 头部插入元素 strList[2] = strList[1] strList[1] = "baz" // 读取第2个元素 v := strList[1] // 遍历列表 for i := 0; i < len(strList); i++ { fmt.Println(strList[i]) } // 删除第1个元素 strList[1] = ""
数组实现列表主要特点是简单直接,但是不够灵活。
2
2. 切片实现列表
切片实现的列表功能更加完整:
// 定义一个字符串切片 var strList []string // 尾部追加元素 strList = append(strList, "foo") strList = append(strList, "bar") // 读取第一个元素 v := strList[0] // 遍历切片列表 for i := range strList { fmt.Println(strList[i]) } // 删除第1个元素 strList = append(strList[:1], strList[2:]...)
切片列表可以动态增长,并且可以很方便地在尾部快速添加元素。
再来看一个例子:
// 定义一个数值切片 var numList []float64 // 尾部添加元素 numList = append(numList, 1.2) // 头部添加元素 numList = append([]float64{2.3}, numList...) // 中间位置添加元素 numList = append(numList[:1], append([]float64{3.4}, numList[1:]...)...) // 读取第2个元素 v := numList[1] // 删除第1个元素 numList = append(numList[:1], numList[2:]...)
切片允许很容易在头部或中间位置添加元素。
3
3. 链表实现灵活列表
可以通过自定义链表结构实现功能更加完备的列表:
// 链表节点 type Node struct { Value int Next *Node } // 初始化一个空链表 var list List // 尾部插入元素 node := &Node{Value: 1} list.Append(node) node = &Node{Value: 2} list.Append(node) // 读取第1个节点 node := list.Head.Next // 遍历链表 for n := list.Head; n != nil; n = n.Next { fmt.Println(n.Value) } // 删除第2个节点 list.Remove(node.Next)
链表需要自己实现相关的插入、删除、遍历逻辑,但是可以非常灵活地管理元素。
再举一个详细例子:
// 定义链表节点 type Node struct { Value int Next *Node } // 初始化链表 list := new(List) // 头插法建立链表 header := &Node{} list.Append(header) p := header for i := 1; i <= 5; i++ { tmp := &Node{Value: i} p.Next = tmp p = tmp } // 尾插法插入元素 tail := &Node{Value: 6} p.Next = tail // 删除第2个节点 list.Remove(header.Next.Next) // 查找节点 n := list.Find(2) // 反转链表 list.Reverse(header) // 遍历链表 for n := header.Next; n != nil; n = n.Next { fmt.Println(n.Value) }
链表需要自己实现各种算法,但是可以非常灵活。
4
4. 列表基本操作实现
下面实现列表的一些基本操作:
尾部添加元素
对数组或切片使用 append 直接追加:
list = append(list, v)
对链表可以用尾插法:
node := &Node{Value: v} tail.Next = node tail = node
头部添加元素
对切片可使用 append 向前追加:
list = append([]int{v}, list...)
对链表可用头插法:
node := &Node{Value: v} node.Next = head.Next head.Next = node
中间位置添加元素
对切片,需要创建新切片并复制元素:
list = append(list[:i], append([]int{v}, list[i:]...)...)
对链表直接修改指针完成插入:
node := &Node{Value:v} node.Next = p.Next p.Next = node
读取元素
数组和切片直接索引定位:
v := list[i]
删除元素
数组切片创建新切片完成删除:
list = append(list[:i], list[i+1:]...)
链表修改指针完成删除:
p.Next = p.Next.Next
5
5. 线程安全列表
上述列表都不是线程安全的,可以使用同步原语实现线程安全:
import "sync" // 定义一个互斥锁 var mutex sync.Mutex // 加锁保护列表 mutex.Lock() list = append(list, v) mutex.Unlock() // 使用读写锁分别保护读写 var rw sync.RWMutex rw.RLock() v = list[0] rw.RUnlock() rw.Lock() list = append(list, v) rw.Unlock()
加锁可以实现线程安全,但是需要权衡锁带来的性能损耗。
6
6. 常见算法实现
列表可以实现各种常见算法:
排序
切片列表可以使用 sort 包排序:
sort.Ints(list)
链表可以实现 sort 接口排序:
sort.Sort(list)
查找
顺序查找:
for i := 0; i < len(list); i++ { if list[i] == v { return i } } return -1
二分查找需要列表已排序:
func binarySearch(list []int, v int) int { // 二分查找算法 return index }
翻转
数组可以复制反序写入:
for i := 0; i < len(list); i++ { reversed[len(list)-i-1] = list[i] }
链表修改指针顺序:
var prev *Node for cur := head.Next; cur != nil; { nxt := cur.Next cur.Next = prev prev = cur cur = nxt } head.Next = prev
7
7. 列表与切片区别
列表与切片的区别主要是:
- 列表强调顺序性,切片可无序
- 列表可以快速插入删除,切片更适合追加
- 列表长度固定,切片动态大小
8
8. 应用场景
列表常见使用场景包括:
- 待办任务列表
// 待办任务队列 var taskQueue []*Task // 添加任务 taskQueue = append(taskQueue, NewTask(params)) // 获取执行任务 task := taskQueue[0] taskQueue = taskQueue[1:] // 已完成任务列表 var doneList []*Task
商品列表
// 商品列表 var productList []*Product // 添加商品 productList = append(productList, NewProduct(name, desc)) // 删除下架商品 for i := 0; i < len(productList); i++ { if !productList[i].OnSale { productList = append(productList[:i], productList[i+1:]...) } }
LRU 缓存淘汰
// 双向链表 type Node struct { Prev, Next *Node Key, Value interface{} } // Get时将节点移到表头 lru.Evict(node) lru.Add(node) // 淘汰链表尾节点 tail := lru.tail lru.Remove(tail)
列表还可以用来实现栈、队列等数据结构。
9
总结
本文全面介绍了 Go 语言实现高效列表的方法,包含数组、切片和链表实现,分析它们的特点,使用示例代码演示各种操作的实现,并对比了列表与切片的区别,以及举例列出了使用场景。希望可以帮助您深入理解 Go 语言中的列表实现和应用。如果有任何问题,非常欢迎您提出讨论。
