数据结构与算法 线性表-列表
列表
数组长度不可变导致实用性降低。在许多情况下，我们事先无法确定需要存储多少数据，这使数组长度的选择变得困难。若长度过小，需要在持续添加数据时频繁扩容数组；若长度过大，则会造成内存空间的浪费。
为解决此问题，出现了一种被称为「动态数组 Dynamic Array」的数据结构，即长度可变的数组，也常被称为「列表 List」。列表基于数组实现，继承了数组的优点，并且可以在程序运行过程中动态扩容。在列表中，我们可以自由添加元素，而无需担心超过容量限制。
列表常用操作
初始化列表。通常我们会使用“无初始值”和“有初始值”的两种初始化方法。
访问与更新元素。由于列表的底层数据结构是数组，因此可以在O(1) 时间内访问和更新元素，效率很高。
在列表中添加、插入、删除元素。相较于数组，列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为O(1) ，但插入和删除元素的效率仍与数组相同，时间复杂度为O(N) 。
遍历列表。与数组一样，列表可以根据索引遍历，也可以直接遍历各元素。
拼接两个列表。给定一个新列表 list1 ，我们可以将该列表拼接到原列表的尾部。
排序列表。排序也是常用的方法之一。完成列表排序后，我们便可以使用在数组类算法题中经常考察的「二分查找」和「双指针」算法。
列表实现
- 初始容量：选取一个合理的数组初始容量。如选择 10 作为初始容量。
- 数量记录：声明一个变量 size，用于记录列表当前元素数量，并随着元素插入和删除实时更新。根据此变量，我们可以定位列表尾部，以及判断是否需要扩容。
- 扩容机制：插入元素时可能超出列表容量，此时需要扩容列表。扩容方法是根据扩容倍数创建一个更大的数组，并将当前数组的所有元素依次移动至新数组。