leetcode推前leetcode_Q-As数据结构是一种在计算机中存储和组织数据的方法，以便可以有效地使用它。我们将数据结构称为数学/逻辑模型或抽象数据类型（ADT），执行ADT定义数据和操作，但没有实现。我们需要研究它们的：逻辑视图、操作、运营成本。如何决定使用哪种数据结构？这取决于：需要存储什么、运营成本、内存使用情况、易于实施。

列表为抽象数据类型可分为：

  • 静态的：存储给定数据类型的固定数量的元素，允许在某个位置写入/修改、读取元素。

  • 动态的：列表的大小可以为0，可以插入、删除、读取/修改某个位置的元素。

数组实现：

  • 数组在静态列表中定义后，可以在恒定时间内计算长度。

  • 当数组已满时，创建一个新的双倍大小的数组，将旧数组复制到新数组，并释放旧数组内存。

  • 在索引处读/写元素 - O(1)

  • 插入 - O(n)

  • 删除 - O(n)

  • 推送 - 最坏O(n)，摊销O(1)（在C中，旧数组可以扩展为新数组，否则将分配新的内存块）。

链表介绍：

每个节点包含值和指向下一个节点的指针。