壹｜什么是数组

数组是线性表数据结构，用一组连续内存空间，存储一组具有相同类型数据。
数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
数组查找的时间复杂度不是 O(1)，即使是排好序的数组，二分查找时间复杂度也是 O(logn)。
因为数组的内存空间地址是连续的，所以插入和删除元素的时候，难免需要移动其他元素的地址。

贰｜数组的属性方法

属性

  • arr

    方法

  • unshift(value)：在头部新增值，向后移动原来数组，返回数组长度。

  • push(value)：在尾部新增值，返回数组长度。
  • pop()：在尾部删除值，返回该值。
  • shift()：在头部删除值，返回该值。
  • find(value)：遍历找到值，返回该值。

  • reverse()：遍历数组，交换头和尾的值，返回数组。

    叁｜数组问题拓展

    数组插入操作优化

    数组插入操作 O(n) → O(1)，将插入替换的数据插入到最后。前提：数组存储之间没有关联。

    数组删除操作优化

    数组删除操作在没有更多的内存空间后再统一进行删除，因为删除后需要重新进行数据调整。
    应用于 JVM 标记清除垃圾回收。

    数组从 0 开始编号

    C 语言设计者用 0 开始计数数组下标，之后的 Java 和 JavaScript 等高级语言都效仿了 C 语言。
    下标确切的定义是偏移。

    肆｜数组的题目

  • 移除元素：https://leetcode-cn.com/problems/remove-element/

  • 有序数组的平方：https://leetcode-cn.com/problems/squares-of-a-sorted-array/

  • 长度最小的子数组：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

    伍｜什么是链表

    链表通过指针将一组零散的内存块串联在一起。
    链表中的节点在内存中不是连续分布的，而是散乱分布在内存中。
    链表删除和插入的时间复杂度是 O(1)，但查找的时间复杂度是 O(n)。

    陆｜链表的属性方法

    属性

  • head

  • tail

    方法

  • prepend(value)：新增节点，next 指向原来头节点，头节点设为新增节点。

  • apend(value)：新增节点，尾节点的 next 指向新增节点。
  • delete(value)：遍历找到需要删除节点，通过 next 指针指向 next.next，删除节点，返回删除的节点。
  • find(value)：遍历找到节点，返回该节点。
  • deleteTail：遍历找到节点的 next.next 为 null，将该节点 next 设为 null。
  • deleteHead：把头节点设为头节点的 next。

  • reverse：遍历链表，记录 next，遍历的节点指针指向新节点，新节点值为遍历的节点。

    柒｜链表问题拓展

    链表有什么特征

  • 插入和删除操作是非常快速的「不需要为了保持内存连续性而搬移结点」。

  • 随机访问第 k 个元素就没有那么高效「链表的数据并非连续存储，无法像数组根据首地址和下标通过寻址公式直接得出内存地址」。

    写链表代码技巧

  • 理解指针或引用的含义

  • 警惕指针丢失和内存泄漏
  • 利用哨兵简化实现难度
  • 重点留意边界条件处理
  • 举例画图，辅助思考

  • 多写多练，没有捷径

    捌｜链表的题目

  • 移除链表元素：https://leetcode-cn.com/problems/remove-linked-list-elements/

  • 设计链表：https://leetcode-cn.com/problems/design-linked-list/
  • 链表逆序：https://leetcode-cn.com/problems/reverse-linked-list/description/
  • 链表求交点：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/
  • 链表求环：https://leetcode-cn.com/problems/linked-list-cycle-ii/description/