【基本数据结构】链表

链表通过指针将一组零散的内存串联在一起，也是一种非常基础、非常常用的数据结构。

一、常见的3种链表

从内存的角度来看，数组需要一块连续的内存空间，对内存的要求比较高。但是，链表并不需要连续的内存空间，而是通过“指针”将一组零散的内存串联起来。

如果我们申请一个 100M 大小的数组，当内存中没有连续的 100M 存储空间时，即便剩余的总内存空间大于 100M，仍然会申请失败。但是，如果我们申请的是 100M 大小的链表，就不会有问题。

1.1 单向链表

链表通过指针将一组零散的内存块串联在一起。被串起来的内存块称为链表的结点。为了将所有的结点串起来，每个结点除了存储数据之外，还需要记录下一个结点的地址，这个记录下个结点地址的指针叫作后继指针 next。

从图中可以发现，链表的第一个结点和最后一个结点比较特殊。通常把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址，可以根据它遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 null，表示这是链表上最后一个结点。

数据插入和删除

数组在插入、删除元素时，为了保持内存的连续性，需要做大量的数据搬移，所以时间复杂度是 O(n)。而链表在插入或删除一个元素时，并不需要搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个元素，只需要考虑相邻结点的指针改变，速度很快。

数据访问

有利就有弊，链表要想访问第 k 个元素，就无法像数组那样，根据首地址和下标，通过寻址公式直接计算出对应的内存地址，必须要根据指针一个结点一个结点依次遍历，直到找到相应的结点。所以，链表访问的性能没有数组好，需要 O(n) 的时间复杂度。

1.2 双向链表

单向链表的每个结点只有一个后继指针 next 指向下一个结点。而双向链表，每个结点不止有后继指针 next ，还有前驱指针 prev 指向上一个结点。

如图所示，双向链表需要两个额外的空间来存储前驱指针和后继指针。所以，存储同样多的数据，双向链表比单向链表占用更多的内存空间，但它支持双向遍历，带来了链表操作的灵活性。

双向链表的优势

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，使双向链表在某些情况下的插入、删除等操作要比单向链表简单高效。

我们先来看删除操作。在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：

删除结点中“值等于某个给定值”的结点；
删除给定指针指向的结点。

对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始依次遍历对比，直到找到值等于给定值的结点，然后再通过指针操作将其删除。尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 node 需要知道其前驱结点，而单向链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p.next=node，说明 p 是 node 的前驱结点。但是对于双向链表来说，就不需要像单链表那样遍历。所以，针对第二种情况，单向链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要 O(1) 的时间复杂度。

同理，如果我们在链表的某个指定结点前面插入一个结点，双向链表比单向链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。

对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

现在，你应该已经发现了，双向链表要比单向链表更加高效。这就是为什么在实际的软件开发中，尽管双向链表比较费内存，但还是比单向链表应用更加广泛。Java 语言的 LinkedList、LinkedHashMap 都用到了双向链表这种数据结构。

实际上，这里有一个更加重要的知识点需要掌握，那就是用 空间换时间 的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，就可以选择空间复杂度相对较高，但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用 时间换空间 的设计思路。缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，比较慢。但如果我们通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。总结一下，对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。

1.3 循环链表

循环链表是一种特殊的单链表。我们知道，单链表的尾结点指针指向空地址，而循环链表的尾结点指向头结点。相比单链表，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构时，就特别适合采用循环链表，比如著名的约瑟夫问题。

二、链表与数组的性能对比

数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别，它们插入、删除、随机访问操作的时间复杂度正好相反。

不过，数组和链表的对比，并不能仅仅考虑时间复杂度。事实上，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。需要考虑：

随机访问：数组使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以随机访问效率更高；而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
动态扩容：数组大小固定，一旦声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容。
内存苛刻用数组：因为链表中的每个结点都需要消耗额外的存储空间去存储指向下一个结点的指针，所以内存消耗会更多。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。

所以，在实际的开发中，针对不同类型的项目，要根据具体情况，权衡究竟是选择数组还是链表。

三、写链表代码的注意点

3.1 警惕指针丢失和内存泄漏

如果我们希望在结点 b 和相邻的结点 c 之间插入结点 x，下面代码实现，就会发生指针丢失和内存泄露。

b.next = x;  // 将b的next指针指向x结点；
x.next = b.next;  // 将x的结点的next指针指向c结点；

这是因为，第一行代码 b.next = x 执行之后，b 节点指向了 x 节点，第二行代码相当于将 x 赋值给 x.next，自己指向自己。因此，整个链表也就断成了两半，从结点 c 往后的所有结点都无法访问到了。

所以，我们插入结点时，一定要注意操作的顺序，要先将结点 x 的 next 指针指向结点 c，再把结点 b 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。所以，对于刚刚的插入代码，我们只需要把第 1 行和第 2 行代码的顺序颠倒一下就可以了。

3.2 重点留意边界值处理

软件开发中，代码在一些边界或者异常情况下，最容易产生 bug，链表代码也不例外。要实现没有 bug 的链表代码，一定要在编写的过程中以及编写完成之后，检查边界条件是否考虑全面，以及代码在边界条件下是否能正确运行。

可以用以下几个边界条件进行考虑：

如果链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？
如果链表只包含两个结点时，代码是否能正常工作？
代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

实际上，不光光是写链表代码，在写任何代码时，我们千万不要只是实现业务正常情况下的功能，一定要多想想，我们的代码在运行的时候，可能会遇到哪些边界情况或者异常情况。遇到了应该如何应对，这样写出来的代码才够健壮！

3.3 利用哨兵简化实现难度

首先，我们来回顾一下单向链表的插入和删除操作，如果需要在结点 p 后面插入一个新的结点，只需要下面两行代码就可以搞定。

new_node.next = p.next;
p.next = new_node;

但是，当我们要向一个空链表中插入第一个结点时，就需要进行下面这样的特殊处理，其中 head 表示链表的头结点。从这段代码，我们可以发现，对于单向链表的插入操作，第一个结点和其他结点的插入逻辑是不一样的。

 if (head == null) {
     head = new_node;
 }

再来看看单向链表的结点删除操作，如果要删除结点 p 的后继结点，我们只需要一行代码就可以搞定。

p.next = p.next.next;

但是，如果我们要删除的链表只有最后一个结点时，前面的删除代码就不对了。跟插入类似，我们也需要对于这种情况特殊处理。写成代码是这样子的：

if (head.next == null) {
    head = null;
}

从前面的代码可以看出，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，而且也容易因为考虑不全而出错，这时候就可以使用哨兵简化代码。

哨兵，解决的是国家之间的边界问题。同理，这里说的哨兵也是解决“边界问题”的，不直接参与业务逻辑。还记得如何表示一个空链表吗？head=null 表示链表中没有结点了。其中 head 表示头结点指针，指向链表中的第一个结点。如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。

实际上，这种利用哨兵简化编程难度的技巧，在很多代码实现中都有用到，比如插入排序、归并排序、动态规划等。

哨兵举例，代码 2 比代码 1 执行效率更高。

代码 1：

// 在数组a中，查找key，返回key所在的位置
// 其中，n表示数组a的长度
int find(char[] a, int n, char key) {
    // 边界条件处理，如果a为空，或者n<=0，说明数组中没有数据，就不用while循环比较了
    if(a == null || n <= 0) {
        return -1;
    }

    int i = 0;
    // 这里有两个比较操作：i<n和a[i]==key.
    while (i < n) {
        if (a[i] == key) {
            return i;
        }
        ++i;
    }
    return -1;
}

代码 2：

// 在数组a中，查找key，返回key所在的位置
// 其中，n表示数组a的长度
int find(char[] a, int n, char key) {
    if(a == null || n <= 0) {
        return -1;
    }

    // 这里因为要将a[n-1]的值替换成key，所以要特殊处理这个值
    if (a[n-1] == key) {
        return n-1;
    }

    // 把a[n-1]的值临时保存在变量tmp中，以便之后恢复。
    // 之所以这样做的目的是：希望find()代码不要改变a数组中的内容
    char tmp = a[n-1];
    // 把key的值放到a[n-1]中
    a[n-1] = key;

    int i = 0;
    // while 循环比起代码1，少了i<n这个比较操作
    while (a[i] != key) {
        ++i;
    }

    // 恢复a[n-1]原来的值
    a[n-1] = tmp;

    if (i == n-1) {
        // 如果i == n-1说明，在0...n-2之间都没有key，所以返回-1
        return -1;
    } else {
        // 否则，返回i，就是等于key值的元素的下标
        return i;
    }
}

3.4 举例画图，辅助思考

对于稍微复杂的链表操作，比如前面我们提到的单链表反转，指针一会儿指这，一会儿指那，一会儿就被绕晕了。总感觉脑容量不够，想不清楚，这个时候就要使用举例法和画图法。

我们可以找一个具体的例子，把它画在纸上，释放一些脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。比如往单链表中插入一个数据，我们可以把各种情况都举一个例子，画出插入前和插入后的链表变化，如图所示：

标签：基本,结点,代码,next,链表,内存,数据结构,指针
From： https://www.cnblogs.com/luwei0424/p/17166336.html