重识数据结构－链表重识数据结构－链表

1. 链表种类链表基本元素是结点，它里面包含数据域与指针域，结点之间用指针连接起来，形成一个简单的链，不同种类的链表只不过是结点内部指针的结构不同而已。常见的链表数据结构有单向链表、双向链表、环形单向链表、环形双向链表这四种结构：
单向链表：单链表是指每一个结点只包含一个指针域的链表，这个指针指向当前节点的逻辑上的下一个节点，即该指针存储着下一个节点的地址。
双向链表：与单链表不同，双向链表是指在链表的节点中设置两个指针域，一个指向当前节点的直接前驱，另一个指向它的直接后继。
环形单向链表：环单链表与单链表的区别就在于它的最后一个节点的指针项指向该链表的头结点。（而非循环的单链表则的最后一个节点指针为null）
环形双向链表：循环双链表也是一个环形的链表。将头结点的前驱设置为尾节点，而尾节点的后继设置为头结点。
2. 链表结构优缺点链表插入删除效率极高，达到O(1)。对于不需要搜索但变动频繁且无法预知数量上限的数据，比如内存池、操作系统的进程管理、网络通信协议栈的trunk管理等等，缺了它是绝对玩不转的。甚至就连很多脚本语言都有内置的链表、字典等基础数据结构支持。
这里拿JDK中的ArrayList和LinkedList进行说明，相对于ArrayList，LinkedList插入是更快的。因为LinkedList不像ArrayList，不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是ArrayList最坏的一种情况，时间复杂度是O(n)，而LinkedList中插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据时还需要更新索引（除了插入数组的尾部）。
链表结构最大的缺点在于链表数据的随机读写性能非常弱，需要先顺序遍历结点，找到插入点后再修改链表指针指向。
在以下场景LinkedList比ArrayList有优势：1) 你的应用不会随机访问数据。因为如果你需要LinkedList中的第n个元素的时候，你需要从第一个元素顺序数到第n个数据，然后读取数据。2) 你的应用更多的插入和删除元素，更少的按索引读取数据（如果只是遍历，区别不大）。因为插入和删除元素不涉及重排数据，所以它要比ArrayList要快。
3. 链表用在哪链表结构对于很多开发同学来说感觉没有地方能够用到，其实这是一种错觉，我们日常用到的很多地方都涉及到链表数据结构，只不过我们平时没有注意到而已，链表数据结构一般用在需要快速插入数据又没有需要经常随机读的场景，下面我们就举几个用到链表数据结构的例子。
1）文件系统。最显著的应用就是文件系统。你格式化硬盘时会让你选择fat32、ntfs格式，其实就是让你选择存储链表空间规模及格式。为提高系统效率，你有时需要做文件碎片整理，这说明一个文件的数据不一定是连续存放的，那么操作系统是如何知道把不连续的数据合成一个文件提供给你的呢？其实就是通过访问一个指向文件数据区的链表得到的。操作系统通常会把一个硬盘的文件区域划分为3个部分：簇链表空间（FAT）/根目录区（Root）、数据区，而数据区是按指定空间大小分为一簇簇，并编号，假如一个文件数据分布在1/3/5簇，那么目录区该文件目录后面会跟随一个指针指向1，接着在FAT编号为1的指针指向3,3指向5,5没有指向，通常链表是以NULL结束，但文件系统是以-1结束。所以文件系统通过访问目录（头指针head）、FAT区（链表区相当去申请到的堆空间）得到一个完整的链表1-3-5，再通过计算获取文件数据所在的簇，最后得到数据。由于链表属于环环相扣的串行数据，任何一环断开，这个链条就坏了，所以文件系统通常会有一个备份FAT，确保一个损坏可以恢复。
2）LinkedList。上面其实也说到了LinkedList，LinkedList是日常经常被使用到的链表结构，非常适合用在需要连续读和快速插入的场景下。

文章图片
Screenshot 2018-03-14 15.31.09
通过Linklist数据结构我们能够看出，这是一个标准的单向链表数据结构，链表中定义的成员变量包含了头结点和尾结点、还有整个链表的结点数，同时还包含了很多链表常用操作方法。
3）disruptor
disruptor是我们用的比较多的并发框架，之前也写过文章介绍过disruptor，disruptor能够做到高速并行读的核心原理就是底层的环形链表数据结构。

文章图片
disruptor环形链表
生产者消费者模式－java原生、Disruptor实现方案
4. 链表代码实现其实除了上面说的这些数据结构还有很多地方用到了链表结构，这里就不一一列举了，下面我们就来说下如何实现这些常见的链表结构。
单向链表结点

public class LinkNode {public int value; public LinkNode next; }

【重识数据结构－链表】双向链表结点

public class DLinkNode {public int data; public DLinkNode prior; public DLinkNode next; }

单向链表插入
在p结点后面插入q结点

//创建数据项为x的新结点 LinkNode q = new LinkNode(); q.value = https://www.it610.com/article/x; q.next = null; //插入开始 q.next = p.next; //设置q的后继为p当前的后继 p.next = q; //更新p的后继为q

单向链表删除

int x = p.next.value; //保存要删除的节点内容 p.next = p.next.next; //直接更新p的后继为它当前后继的后继

双向链表插入

//创建数据项为x的新结点 DLinkNode q = new DLinkNode(); q.value = https://www.it610.com/article/x; q.prior = null; q.next = null; //插入开始 q.prior = p; //设置q的前驱为p q.next = p.next; //设置q的后继为p当前的后继 p.next.prior = q; //更新p的后继节点的前驱为q（之前是p） p.next = q; //更新p的后继为q

双向链表删除

int x = p.next.value; //保存要删除的节点内容 p.next.next.prior = p; //更新要删除的节点的后继节点的前驱为p p.next = p.next.next; //更新p的后继为要删除的节点的后继

其他的链表操作，例如向某个位置插入元素、某个位置删除元素、查找元素等，其实都是一边遍历一边找到药操作的位置进行插入或者删除操作，这类操作对于链表来说性能较差，如果有这类操作的使用场景不建议使用链表数据结构。
总结链表的数据结构还是比较简单的，基本就是顺序结点的操作，目前主流语言基本都有现成的链表结构，可以直接使用，在看了上面介绍的链表的使用场景和链表的数据结构实现，应该能够比较好的理解，为什么链表更加适合快速顺序插入数据和顺序读取数据而不适合于随机读写数据了吧。链表就介绍到这，下一篇介绍下队列和栈。