【数组】

  • 数组是存放在连续内存空间上的相同类型数据的集合；

    数组下标都是从0开始的；

    数组内存空间的地址是连续的；

    因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，难免要移动其元素的地址；

    数组的元素是不能删的，只能覆盖；

  • 常见的解题方法：

    • 二分法 ： 循环不变量，左闭右开，左闭右闭

    • 双指针法（快慢指针）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作

    • 滑动窗口：主要理解滑动窗口如何移动窗口的起始位置，达到动态更新窗口的大小，从而得出长度最小的符合条件的长度。

      精妙之处在于根据当前子序列的大小的情况，不断调节子序列的起始位置。从而降低时间复杂度

    • 模拟行为：螺旋数组再一次介绍了循环不变量原则，

【链表】

  • 种类：单链表，双链表，循环链表

    • 存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。

    • 增删改查的方式：

    • 数组和链表在不同场景的性能分析

  • 常见方法：

    • 虚拟头结点：
      • 链表的一大问题就是操作当前节点必须要找到前一个节点才能操作。每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题
    • 链表的基本操作（常见的五个操作）：
      • 获取链表第index个节点的数组
      • 在链表的最前面插入一个节点
      • 在链表的最后面插入一个节点
      • 在链表第index个节点前面插入一个节点
      • 删除链表的第index个节点的数值
    • 反转链表：迭代法；递归法；
    • 删除倒数第N个节点：结合虚拟头结点和双指针法来移除
    • 链表相交：使用双指针来找到两个链表的交点（引用完全相同，即：内存地址完全相同的交点）
    • 环形链表：在链表中如何找环、如何找环的入口位置