在日常开发中,我们常常需要处理动态数据集合。Go语言提供了多种数据结构,其中container/list包实现的双向链表和内置的切片(slice)是最常用的两种线性结构。但何时该选择链表而非切片呢?这篇文章分享一下我的理解。
切片是基于数组的动态序列,元素在内存中连续存储。这种结构使得随机访问效率极高(O(1)时间复杂度),但在中间位置插入或删除元素时需要移动后续所有元素,时间复杂度为O(n)。
链表(双向链表)的元素在内存中非连续存储,每个元素通过指针连接前后元素。链表在任意位置插入和删除元素的时间复杂度都是O(1),但随机访问需要遍历,时间复杂度为O(n)。