一学一记:链表

发表于   |   更新于 | | 阅读数
字数统计 1.7k 字 | 阅读时长 6 分钟

链表

概念

  • 在数据结构中，链表也是常用的基本数据结构，节点持有指向其他节点的前后引用，一次来定位和查找元素，这种特性也导致链表在访问指定元素时，需要进行一次O(n)遍历；根据存储方式的不同，可以简单划分为三类基础链表:单链表，双链表，循环链表。
  • 单链表：
    • 每个节点只具备向后的指针引用，最后一个节点指向null
  • 双链表:
    • 每个节点都具备向前，向后的引用，指向各自的前驱，后继节点；头节点的前驱节点指向null；尾节点的后继节点指向null
  • 循环链表：
    • 循环单链表： 在单链表的基础上，尾节点的next指向头节点
    • 循环双链表：在双链表的基础上，头节点的前驱节点指向尾节点；尾节点的后继节点指向头节点；

链表的存储特点

  • 和数组不同，链表由于通过节点之间的引用来进行定位，所以并不要求使用物理连续的内存空间进行数据存储，可以比较好地利用碎片空间；
  • 在对链表中的数据进行插入和删除操作时，只需要改变相邻节点的引用，插入删除的复杂度都是O(1)
  • 而在遍历上，三种结构的链表最坏时间复杂度都是O(n）

链表结构之间的对比

  • 单链表与双链表：

    • 单链表只能进行向后查找，与之相比，再进行查找指定元素再进行删除这样的操作场景上，单链表定位到指定元素进行删除时，还需要重新遍历一次定位被删除元素的前驱节点，将该节点的引用指向被删除节点的后继节点；而双链表虽然在定位元素的时间复杂度上和单链表一样，但是进行删除时，可以通过被删除节点的向前指针找到前驱节点，直接改变相邻节点的引用，不需要再进行一次遍历

    • 双链表使用更多的内存空间为每个节点存储了向前引用，是一种以空间换时间的思路，在特定应用场景上，比单链表更加适合。

    • 而且对于有序双链表，因为同时支持向前和向后索引，支持折半查找这种定位元素位置的方式

  • 链表与数组：

    • 查找：
      • 数组支持通过索引的随机访问，查找的时间复杂度是O(1)；
      • 链表只能通过节点引用之间循环地遍历，定位元素的时间复杂度是O(n)
    • 插入删除:
      • 数组为了维护内存空间的完整性，需要在删除和插入元素时，将部分甚至整体数据进行移动，时间复杂度是O(n)；
      • 而链表的插入，删除操作，是改变被删除/插入节点的相邻节点引用，时间复杂度是O(1)

链表实现LRU缓存策略

  • LRU : Least Recently Used , 最近最少使用策略；是一种常用的缓存淘汰策略，可以用链表实现：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32

    class Node {
            Object value;
            Node next;
        }

        LinkedList<Node> caches = new LinkedList<>();

        public void LRUClear(Object obj) {

            Node head = caches.getFirst();
            Node last = caches.getLast();
            Node prev = head;;
            Node temp = head;
            Node in = new Node();
            in.value = obj;
            while (temp.next != null) {
                //将已存在缓存中的对象移到链表的头部
                if (temp.value.equals(obj)) {
                    prev.next = temp.next;
                    temp.next=null;
                    in.next = head;
                    break;
                }
                prev = temp;
                temp = temp.next;
            }
            if (!temp.next.equals(head)) {
                last.next = in;
                in.next = null;
            }
        }

  • 粗糙地实现了一下，就是在判断数据是否已缓存的情况下，决定将它插入到头部还是尾部，越靠前代表热门数据。

快慢指针定位链表中点:

  • 快慢指针算法:

    • 可以参考物理的相对运动来理解，在一条环状道路上，从同一起点出发，速度不同的两辆汽车最终肯定会相遇，速度快的那辆会追上速度慢的那辆；快慢指针定位链表是否有环也是一样的思路：两个运动步长不一致的指针，最终相遇的话证明链表有环

    • 也可以通过快慢指针定位奇数长度链表的中点:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      class Node {
              Object value;
              Node next;
      }

      public static int midpoint(Node head){
          int midCount = 0;
          Node slow = head;
          Node fast = head.next;

          while(fast!=null){
              midCount++;
              slow = slow.next;
              if(null!=fast && null != fast.next) {
                  fast = fast.next.next;
              }else{
                  return midCount;
              }
          }
          return midCount;
      }

    • 针对于奇数长度的链表，当快指针到达末尾，慢指针则在中点位置

    • 快慢指针的步长为什么是两倍:

      • 如果是寻找链表中点，取一倍步长差是合适的，慢指针在位置 n 的话，快指针在 2n+1 位置， 长度为 L 的链表，当 2n+1 = L , n = (L-1)/2 , 因为索引从 0 开始，因此 n 是链表的中点
      • 如果是定位链表环，当快指针追上慢指针的时候，链表存在环；又因为快慢指针之间的速度差，在第一次环状遍历的时候是无法相遇的，取快指针步长为两倍，可以保证在快指针的第二次遍历时一定与慢指针相遇，这个时间是较优的。

小结:

  • 链表的存储结构是逻辑连续的内存空间，节点之间通过引用相连接，因此具备高效的插入，删除操作；而在遍历上则不如数组那样高效，定位某个节点需要将整个链表都遍历一次

  • 双链表在插入和删除操作上要优于单链表，从链表中查找某个节点它们的时间复杂度相同；但是进行节点插入/删除时，需要改变相邻节点的引用，单链表需要再进行一次遍历以确定该位置的前驱节点，这里需要的最坏时间复杂度是O(n)；而双链表因为具备向前索引的能力，可以直接修改前关联节点的引用，这一步操作的时间复杂度是O(1)

  • 单链表实现LRU算法思路是：使用一个有序链表维护数据，当插入数据已存在于单链表链表中，将原本位置数据删除，重新插入到链表头部，如果不存在则插入到链表尾部