链表是一种物理存储结构上非连续、非顺序的线性存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表中的元素（节点）中记录了与其他元素的连接关系，链表的存储方式相比于顺序表更加灵活。
链表结构多样，分带头/不带头、单向/双向和循环/不循环，相互组合可以有8种结构。本文实现不带头单向不循环链表。
链表的逻辑结构是线性和连续的，各个节点通过指针进行连接。
链表的物理结构是离散的，存储链表的内存空间是非连续的。
链表的每个节点包含两部分信息：有效数据(Value)和指向下一节点的指针(Next)。其中尾节点的指针为。
通常用指针维护一个链表，这个指针通常指向一个链表的头结点，即phead->list。事实上，我们通常将头结点作为一个链表的代称，例如头结点head和链表head实际上是同义的。
建立一个链表通常分为两步，第一步是初始化各个节点，第二是在各个节点之间建立连接关系。完成后，即可从头结点出发，访问其余所有节点。
在下面的接口中往往需要申请一个新节点，此处将创建节点的功能单独封装成一个函数，返回新节点的地址。
打印链表便于调试和直观显示数据。从头结点开始向后遍历链表以实现链表数据的打印。
在尾部插入数据时，首先要创建一个新节点，再寻找尾节点并将尾节点的Next修改为新节点的地址以实现链表和新节点的链接。
另外，需要额外考虑空表情况。当链表为空时，需要将新节点的地址赋值给plist，所以在传参时需要传plist的地址以顺利修改链表的头结点。另外，为了检查使用者的传参错误，需要对进行断言。
一种常见的错误实现如下：
出现上面错误的原因是对链表的物理结构理解不透彻，当循环停止时，的值为，当赋值新节点的指针给时，尾节点的并未被改变，即这个操作不能将新节点链接起来。
注意深刻理解链表的物理结构：临时指针变量的地址不变，临时指针变量存储的地址在变。
空表情况和只有一个节点的情况需要额外考虑。
可以注意到，上述实现中间插入和删除数据都是在指定位置的后方进行操作，这是因为由于在单向不循环链表中，无法直接找到一个节点的前驱节点和后继节点，若要实现删除指定位置和在指定位置的前面插入一个节点，需要从头遍历链表找到位置的前驱节点，效率较低。STL库中对单向链表这种接口的实现的原因也是如此。
STL中单向链表中的部分接口:
链表具有以下缺点：
- 链表的随机访问效率较低。当需要寻找一个节点时，要从链表的头结点开始遍历寻找。
- 链表占用的内存较多。因为每个链表节点不仅要存储有效数据，还要额外存储指针。不过这些额外的内存在如今已经不值一提，所以这个缺点几乎可以忽略不计。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/sjkxydsj/14546.html