Go实现双向链表的示例代码-创新互联

本文介绍什么是链表，常见的链表有哪些，然后介绍链表这种数据结构会在哪些地方可以用到，以及 Redis 队列是底层的实现，通过一个小实例来演示 Redis 队列有哪些功能，最后通过 Go 实现一个双向链表。

目录

1、链表

• 1.1 说明
• 1.2 单向链表
• 1.3 循环链表
• 1.4 双向链表

2、redis队列

• 2.1 说明
• 2.2 应用场景
• 2.3 演示

3、Go双向链表

• 3.1 说明
• 3.2 实现

4、总结

5、参考文献

• 1、链表
• 1.1 说明

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

优势:

可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。链表允许插入和移除表上任意位置上的节点。

劣势:

由于链表增加了节点指针，空间开销比较大。链表一般查找数据的时候需要从第一个节点开始每次访问下一个节点，直到访问到需要的位置，查找数据比较慢。

用途:

常用于组织检索较少，而删除、添加、遍历较多的数据。

如：文件系统、LRU cache、Redis 列表、内存管理等。

1.2 单向链表

链表中最简单的一种是单向链表，

一个单向链表的节点被分成两个部分。它包含两个域，一个信息域和一个指针域。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址，而最后一个节点则指向一个空值。单向链表只可向一个方向遍历。

单链表有一个头节点head，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问哪个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。

1.3 循环链表

循环链表是与单向链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

循环链表的运算与单链表的运算基本一致。所不同的有以下几点：

1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是像单链表那样置为NULL。

2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域的值等于表头指针时，说明已到表尾。而非象单链表那样判断链域的值是否为NULL。

1.4 双向链表

双向链表其实是单链表的改进，当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。

在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域（当此“连接”为最后一个“连接”时，指向空值或者空列表）；一个存储直接前驱结点地址，一般称之为左链域（当此“连接”为第一个“连接”时，指向空值或者空列表）。

2、redis队列

2.1 说明

Redis 列表是简单的字符串列表，按照插入顺序排序。你可以添加一个元素到列表的头部（左边）或者尾部（右边）

Redis 列表使用两种数据结构作为底层实现：双端列表(linkedlist)、压缩列表(ziplist)

通过配置文件中(list-max-ziplist-entries、list-max-ziplist-value)来选择是哪种实现方式

在数据量比较少的时候，使用双端链表和压缩列表性能差异不大，但是使用压缩列表更能节约内存空间

redis 链表的实现源码 redis src/adlist.h

2.2 应用场景

消息队列，秒杀项目

秒杀项目:

提前将需要的商品码信息存入 Redis 队列，在抢购的时候每个用户都从 Redis 队列中取商品码，由于 Redis 是单线程的，同时只能有一个商品码被取出，取到商品码的用户为购买成功，而且 Redis 性能比较高，能抗住较大的用户压力。

2.3 演示

如何通过 Redis 队列中防止并发情况下商品超卖的情况。

假设：

网站有三件商品需要卖，我们将数据存入 Redis 队列中

1、 将三个商品码(10001、10002、10003)存入 Redis 队列中

# 存入商品
RPUSH commodity:queue 10001 10002 10003

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。