链表

  • 链表的每个节点至少包含两部分：数据域 与 指针域，并且每个节点，通过指针域的值，形成的一个线性结构
    • 指针域的指在不同编程语言中有不同的概念，如 C 语言中的 地址，js/python/java 中的 引用，数组的下标，也叫相对地址，都可以作为指针域
  • 链表查找节点的复杂度为O(n)，插入/删除节点的复杂度为 O(1)
  • 链表不适合快速的定位数据，比较适合动态的插入和删除数据的应用场景

创建链表的四种方法

  1. 用构造函数创建对象的方式，比较好理解

    1. const createListNode1 = () => {
    2. function ListNode(value) {
    3.  this.value = value;
    4.  this.next = null;
    5. }
    7. const head = new ListNode(1);
    8. head.next = new ListNode(2);
    9. head.next.next = new ListNode(3);
    10. head.next.next.next = new ListNode(4);
    12. let current = head;
    13. let listNodeValue = [];
    14. while (current !== null) {
    15.  listNodeValue.push(current.value);
    16.  current = current.next;
    17. }
    18. console.log(listNodeValue.join("->"));
    19. };
    20. createListNode1(); // 1->2->3->4

  2. 创建 2 个数组，一个当作数据域，一个当作指针域，也能创建链表，不好理解，但很神奇

    1. const createListNode2 = () => {
    2. let next = []; // 指针域
    3. let data = []; // 数据域
    5. // 在 index 的位置，添加一个节点 node，其值为 value
    6. const addNode = (index, node, value) => {
    7.  // 将插入的节点的指针指向 当前插入位置的 下一个节点
    8.  next[node] = next[index]; // 这行代码是防止不按顺序插入节点
    9.  next[index] = node;
    10.  data[node] = value;
    11. };
    13. const head = 3; // 定义头节点 3，其值为 0
    14. data[3] = 0;
    16. addNode(3, 5, 1); // 在节点 3 的后面添加节点 5，其值为 1
    17. addNode(5, 2, 2);
    18. addNode(2, 7, 3);
    19. addNode(7, 9, 4); // 现在的链表为 0->1->2->3->4
    21. addNode(5, 6, 5); // 不按顺序插入节点，0->1->5->2->3->4
    23. let node = head;
    24. let listNodeValue = [];
    25. while (node) {
    26.  listNodeValue.push(data[node]);
    27.  node = next[node];
    28. }
    29. console.log(listNodeValue.join("->"));
    30. };
    31. createListNode2(); // 0->1->5->2->3->4

  3. todo

  4. todo

链表的应用场景

操作系统内的动态内存分配

  • 用于操作系统内的动态内存分配，管理剩余的内存空间
  • 如下图所示，一块 4G 的内存，被 malloc 申请 1G 内存之后，剩下的内存区在底层就是通过链表去维护的

链表 (List) - 图1

LRU 缓存淘汰算法

  • 实际的实现不是简单的链表，而是哈希链表
  • 这里简单理解缓存中存储的数据，是通过普通链表维护的
    • 假设缓存总共只能存 3 个数据，当要存第 4 个数据时，系统会将最先插入的数据 1 删除，然后在数据 3 后面添加一个数据 4

链表 (List) - 图2