D2 认识链表结构

  • 链表和数组一样，可以用于存储一些元素，但链表和数组的实现机制不一样
  • 链表：一种用于存储数据的线性结构（py）
  • 数组：可存储多个元素，最常见
  • 每一种编程语言，都有默认实现数组结构

  • 数组缺点：

    • 数组的创建需要申请一段连续的内存空间（一整块内存），并且大小是固定的，（大多编程语言数组都是固定的），所以数组不能满足容量需求时，需要扩容，非常消耗性能（一般申请更大的数组，比如2倍。然后将原数组的元素复制过去）
    • 在数组的开头/中间插入元素成本很高，需要大量元素位移
    • 尽管JS数组API可以实现，但背后的原理依旧是这样。

  • 链表：

    • 要存储多个元素，另一种选择就是链表。类似火车节，节点上有乘客（数据），节点连接节点
    • 不同于数组，链表的存储空间，不必是连续的空间
    • 链表的每个元素由一个存储元素本身的节点，和指向下一个元素的引用（有的语言称为指针，或者连接）组成
    • 相对数组的优势
    • 内存空间不必是连续的，可以充分利用计算机的内存，实现灵活的内存动态管理
    • 链表不必在创建的时候，就确定大小，并且可以无限的延伸下去
    • 链表在插入和删除数据时，时间复杂度可以达到O（1），相对数组效率高很多，

  • 相对数组的缺点

    • 链表访问任何一个位置的元素时，都要从头开始访问，（无法跳过第一个元素访问任何一个元素）
    • 无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素

  • 选链表/数组

    • 频繁的插入，删除元素—-》链表
    • 通过下标访问元素—-》数组