认识达内从这里开始

认识链表和学习使用链表是每一位软件编程开发程序员都需要熟练掌握的一个编程知识点，而本文我们就通过案例分析来简单了解一下，链表结构与类型分享。

链表结构

链表和数组一样，也是一个线性表结构，但有一点与数组不同，链表不使用连续的内存空间进行存储，而是通过串联的方式连接元素。

因此，链表克服了数组需要预先知道数据大小的缺点，并且能充分利用计算机内存空间，实现灵活的内存动态管理。

但链表也失去了高效存取的优点，同时，由于增加了结点的指针域，空间开销相较于数组会更大。

链表的概念

链表通过指针将零散的内存块串联在一起，这里的内存块被称为链表的结点。

结点除了存储数据之外，还会存储下一个结点的地址，这个记录下一个结点地址的指针被称为后继指针。在双向链表中，结点还会存储上一个结点的地址，这个记录上一个结点地址的指针被称为前驱指针。

链表中存在两个比较特殊的结点，分别是一个结点和后一个结点。因此也给这两个结点取了名称，一个结点被称为头结点，后一个结点被称为尾结点。

低效存取

将链表和数组作比较，数组具有高效存取的优点，而链表是是存取效率非常低的数据结构。

这里的存取指的是通过下标的方式去访问数据，链表无法像数组一样使用寻址公式，只能通过头结点作为入口，根据指针一个结点一个结点地依次遍历，直到找到对应的结点。

综合计算下来，链表做随机访问的时间复杂度为O(n)，效率比数组低得多。

高效增删

虽然链表在随机存取方面没有数组高效，但在插入、删除结点的时候，效率比数组高很多。

链表的插入和删除

假设，要在链表中插入一个结点，在知道插入位置的前后两个相邻结点的前提下，只需将新结点的后继指针指向下一个结点，然后将上一个结点的后继指针指向这个新结点，即可完成插入结点的操作。删除结点也是类似的操作，非常方便。

但是，链表插入、删除结点的高效率依靠于知道操作位置的相邻结点，否则仍需要从头结点开始寻找到对应位置，这样的效率会非常低。

五花八门的链表

链表有很多不同的类型，在上面说的都是简单的单向链表，复杂一点的还有双向链表、循环链表等等。

单向链表

单向链表是简单的链表结构，它包含两个域，一个信息域和一个指针域。

信息域存储实际的数据，指针域存储下一个结点位置。

在实际编码中，为了方便，会使用哨兵结点占据头结点的位置，其信息域是空的，指针域存储实际的头结点所在位置，尾结点的指针域一般会是NULL地址。

双向链表

双向链表在单向链表的基础上多增加了一个指针域，这个新增加的指针域会存储上一个结点所在位置。

也就是说，在双向链表中，除头结点外，任意结点都可以访问到上一个结点，因此称为双向链表。

双端链表

双端链表与双向链表是完全不同的两个概念。

双端链表是在单向链表的基础上，增加了尾结点的引用。拥有这个引用的双端链表在尾部插入结点时特别方便，因此常被用作实现链式队列。

虽然双端链表可以很方便地在尾部插入结点，但由于无法快捷地获取倒数二个结点，因此仍然不能方便地删除尾结点，若需要此功能可以靠双向链表实现。

循环链表

循环链表是一个头结点和尾结点连接在一起的特殊链表，通过单向链表或双向链表都能够实现。

循环链表的优点就是从链表的尾结点到头结点非常方便，也方便处理具有环形结构特点的数据，如约瑟夫问题。

【免责声明】：本内容转载于网络，转载目的在于传递信息。文章内容为作者个人意见，本平台对文中陈述、观点保持中立，不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。更多内容请加danei0707学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。