数据结构

1   数组和字符串

1.1   数组

• 集合的定义：由一个或多个确定的元素所构成的整体。
• 集合的特性：
  • 集合里的元素类型不一定相同
  • 集合里的元素没有顺序
• 列表（又称线性列表）的定义：是一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。
  • 列表的概念是在集合的特征上形成的，它具有顺序，且长度是可变的。
  • 列表最常见的表现形式：数组和链表
    • C++和Java中，数组中的元素类型必须保持一致。
    • Python数组叫list，元素类型可以不同，具有更多高级功能。
  • 特殊类型的列表：栈和队列
• 列表和数组的区别
  • 数组
    • 数组有索引，用来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从 0 算起的。
    • 数组中的元素在内存中是连续存储，且每个元素占用的相同大小内存。
  • 列表
    • 列表没有索引。
    • 列表中的元素在内存中可能彼此相邻，也可能不相邻。例如链表。

1.2   数组的操作

对于数组，计算机会在内存中为其申请一段连续的空间，并且会记下索引为 0 处的内存地址。

• 读取元素：读取数组中的元素，是通过访问索引的方式来读取的，索引一般从 0 开始。寻找索引为2的元素，实际就是在索引为0的元素内存地址上偏移+2得到新地址的元素。
  • 时间复杂度：O(1)
• 查找元素：由于只保存了索引为 0 处的内存地址，因此需要从数组开头逐步向后查找。
  • 时间复杂度：O(N)
• 插入元素
  • 末尾插入：只需要一步（根据数组的长度和位置计算出需插入元素的内存地址插入即可）。
  • 中间插入：需要在数组中腾出空间，才能继续操作插入（这种操作，更推荐使用链表）。
• 删除元素：与插入元素类似
  • 末尾删除：只需要一步
  • 中间删除：删除中间元素后，后面的元素需要对该位置进行操作
  • 时间复杂度：O(N)。数组长度N，例如删除第一个元素，总步骤数：1+(N-1)=N。（1为删除操作，N-1为移动操作）

1.3   字符串

字符串是由字符串数组形成的。

2   参考文献

[1] 数组和字符串[EB/OL]. https://leetcode.cn/leetbook/detail/array-and-string/.