好玩的网站列表

1. 链表结构

• 数组需要一块连续的内存空间来存储，对内存的要求比较高

• 链表，通过指针将一组零散的内存块串联起来使用

• 链表经典应用场景 - LRU缓存淘汰算法

  • 缓存是一种提高数据读取性能的技术
    • CPU缓存
    • 数据库缓存
    • 浏览器缓存

1.1 单链表

• 每个链表的节点

  • 存储的数据
  • 记录链的下一个结点的地址(后继指针next)

• 头结点用来记录链表的基地址

• 尾结点的指针指向一个空地址NULL

• 插入和删除结点都非常快 O(1)

• 随机访问其中一个元素，比如按照顺序选第n个就是O(n)的复杂度

1.2 双向链表

• 双向链表支持两个方向，每个节点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。
• 双向链表可以支持O(1) 的时间复杂度的情况下找到前驱结点，这样就使得双向链表在某些情况下的插入、删除等操作都要比单链表简单高效。
• 其实就是无论单链表还是双向链表，在删除的时候都需要找到前驱结点，而单链表在这里想要找到前驱结点的话就得从头开始去找，时间复杂度还是O(n)，而双向链表就可以实现很快的找到对应的前驱节点了。
• 因为有prev next两个指针，它黄海军更占用内存的空间
• Java的LinkedHashMap就是用双向链表来实现的
• 用空间换时间的设计思想
  • 当内存空间充足的时候，如果我们更追求代码的执行速度，那么我们就可以选择空间复杂度相对较高，但时间复杂度相对很低的算法或者数据结构。
• 对于有序链表来说，双向链表的按值查询效率也要比单链表高。因为我们可以通过记录上次查找的位置p，每次查询的时候，根据要查找的值和p的大小关系决定是往前还是往后来查找。

1.3 循环链表

• 循环链表的尾结点指针是指向链表的头结点，像一个环一样首尾相连
• 当要处理的数据具有环形结构特点时，就特别适合采用循环链表。

2.链表数组性能对比

时间复杂度	数组	链表
插入删除	O(n)	O(1)
随机访问	O(1)	O(n)

但是在实际应用开发当中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。而链表因为不是连续内存存储，所以没办法有效预读。

数组大小固定，增大如果要做扩容拷贝是非常费时间的。链表本身没有大小的限制，天然支持动态扩容。

而且，如果代码对于内存的使用很苛刻，那数组会更加合适。因为链表中的每个结点都要消耗额外的存储空间去存储指针，所以内存的消耗会翻倍。而且，对链表进行频繁的插入，删除操作还会导致频繁的内存申请和释放，容易造成内存碎片。Java中就会导致频繁的garbage collection.

3. 写链表代码的技巧

3.1 理解指针或者引用的含义

指针，是在像C语言这样的语言当中来使用的；对于Java这种面向对象的语言，是用引用来达成存储所指对象的内存地址的目的。

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就可以找到这个变量了。

// p结点的next指针里面存储了q结点的内存地址
p->next = q

// p 结点的next指针存储了p结点的下下个结点的内存地址
p->next = p->next->next

3.2 警惕指针丢失和内存泄露

x->next = p->next;  // 将 x 的结点的 next 指针指向 b 结点；
p->next = x;  // 将 p 的 next 指针指向 x 结点；

两行代码的顺序很重要，你需要先将p的next的地址赋给x的next的地址，然后再来改p的next，改变p的next指针

3.3 利用哨兵

对于链表当中的第一个结点和最后一个结点，其实现插入删除的逻辑和其他结点是不一样的。

利用哨兵结点可以简化整个实现，让针对于第一个结点和最后一个结点的处理和其他结点的处理方式一致。

3.4 边界条件的思考与判定

• 链表为空
• 链表只包含一个结点
• 链表只包含两个结点
• 代码逻辑在处理头结点和尾结点的时候

4. 实战

4.1 LC 206 Reversed Linked List

// 遍历，重点在因为无法同时保存prev节点和next节点的信息，只有一个指针，所以需要建一个中间变量来记录
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;

        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 stone2paul@gmail.com