链表（第一周）

链表的基础知识

  • 节点
  • 数据域
    • 指针域
  • 链表结构
    • 通过指针域的值形成的线性结构
  • 访问链表的时间复杂度
    • 查找结点 O(n)
    • 插入节点 O(1)
    • 删除节点 O(1)
  • 几种链表的经典实现方式
    • 传统方法（节点+指针）
    • 使用数组模拟
      • 指针域和数据域分离
      • 利用数组存放下标进行搜索
      • 。。。

链表和数组的区别

类型 访问 添加 删除
链表 慢 O(n) 快 O(1) 快 O(1)
数组 快 O(1) 慢 O(n) 慢 O(n)

链表的应用场景

  • 操作系统内的动态内存分配
  • LRU 淘汰缓存算法
  • 缓存算法是一种高速的数据结构
  • 设备间存在速度差异，可以通过较多的数据存放在高速区域，而将较少的内存区域放在相对低速的区域方式，来对系统进行优化

单向链表的实现

  1. // 单向链表
  2. let LinkedList = function () {
  3.     // 链表元素
  4.     let Node = function (element) {
  5.         this.element = element;
  6.         this.next = null;
  7.     };
  9.     let length = 0; // 链表长度
  10.     let head = null; //  链表头节点
  12.     // 链表末尾添加元素
  13.     this.append = function (element) {
  14.         let node = new Node(element);
  15.         let cur = undefined;
  16.         if (head === null) {
  17.             head = node;
  18.         } else {
  19.             cur = head;
  20.             while (cur.next) {
  21.                 cur = cur.next;
  22.             }
  23.             cur.next = node;
  24.         }
  25.         length += 1;
  26.     };
  28.     // 链表中插入元素
  29.     this.insert = function (element, index) {
  30.         let cur = head;
  31.         let node = new Node(element);
  32.         // 向链表头部添加
  33.         if (index <= 0) {
  34.             node.next = cur;
  35.             head = node;
  36.         }
  37.         // 链表尾部添加
  38.         if (index >= length) {
  39.             this.append(element);
  40.         }
  41.         // 链表中间添加
  42.         while (index-- > 1) {
  43.             cur = cur.next;
  44.         }
  45.         node.next = cur.next;
  46.         cur.next = node;
  48.         length += 1;
  49.     };
  51.     // 移出链表中指定的项
  52.     this.removeAt = function (index) {
  53.         let cur = head;
  54.         if (index >= 0 && index <= length) {
  55.             if (index === 0) head = head.next;
  56.             while (index-- > 1) {
  57.                 cur = cur.next;
  58.             }
  59.             cur.next = cur.next.next;
  60.             length -= 1;
  61.         } else {
  62.             return false;
  63.         }
  64.     };
  66.     // 移出值为element的项
  67.     this.remove = function (element) {
  68.         this.removeAt(this.indexof(element));
  69.     };
  71.     // 返回 元素在链表中的索引，没有则返回-1
  72.     this.indexof = function (element) {
  73.         let cur = head;
  74.         let len = 0;
  75.         while (cur) {
  76.             if (cur.element == element) {
  77.                 return len;
  78.             }
  79.             cur = cur.next;
  80.             len += 1;
  81.         }
  82.         return -1;
  83.     };
  85.     // 判断链表是否为空
  86.     this.isEmpty = function () {
  87.         return len === 0;
  88.     };
  90.     // 链表的长度
  91.     this.size = function () {
  92.         let len = 0;
  93.         let cur = head;
  94.         while (cur) {
  95.             cur = cur.next;
  96.             len += 1;
  97.         }
  98.         return length || len;
  99.     };
  101.     // 清空链表
  102.     this.clear = function () {
  103.         let cur = head;
  104.         for (let i = 0; i < length; i++) {
  105.             this.removeAt(i);
  106.         }
  107.         head = null;
  108.         length = 0;
  109.     };
  111.     // 输出整个链表
  112.     this.print = function () {
  113.         return head;
  114.     };
  115. };
  117. let linkedList = new LinkedList();
  118. linkedList.append(0);
  119. linkedList.append(1);
  120. linkedList.append(2);
  121. linkedList.append(4);
  122. linkedList.insert(3, 3);
  123. linkedList.remove(1);
  124. // linkedList.clear()
  126. console.log(linkedList.print(), "print");
  127. console.log(linkedList.size(), "size");
  128. console.log(linkedList.indexof(3), "indexof");

双向链表的实现

  • 暂无

经典面试题

  • 141 环形链表
  • 142 环形链表 ||
  • 202 快乐数
  • 206 反转链表
  • 92 反转链表 II
  • 25 K 个一组翻转链表 *
  • 61 旋转链表
  • 24 两两交换链表中的节点
  • 19 删除链表的倒数第 N 个结点
  • 83 删除排序链表中的重复元素
  • 82 删除排序链表中的重复元素 II
  • 707 设计链表