数据结构，也就是 Data Structure，是一种存储数据的结构体，数据与数据之间存在着一定的关系，这样的关系有数据的逻辑关系、数据的存储关系和数据的运算关系。

在 Java 中，数据结构一般可以分为两大类：线性数据结构和非线性数据结构。

数组

数组这种数据结构最大的好处，就是可以根据下标（或者叫索引）进行操作，插入的时候可以根据下标直接插入到具体的位置，但与此同时，后面的元素就需要全部向后移动，需要移动的数据越多，就越累。

像 ArrayList，内部就对数组进行了封装。

假设现在已经有了一个 ArrayList 了，准备在第 4 个位置（下标为 3）上添加一个元素 55。

此时 ArrayList 中第 5 个位置以后的元素将会向后移动。

准备把 23 从 ArrayList 中移除。

此时下标为 7、8、9 的元素往前挪。

1）通过下标（也就是 get(int index)）访问一个元素的时间复杂度为 O(1)，因为是直达的，无论数据增大多少倍，耗时都不变。

2）添加一个元素（也就是 add()）的时间复杂度为 O(1)，因为直接添加到末尾。

3）删除一个元素的时间复杂度为 O(n)，因为要遍历列表，数据量增大几倍，耗时也增大几倍。

4）查找一个未排序的列表时间复杂度为 O(n)，因为要遍历列表；查找排序过的列表时间复杂度为 O(log n)，因为可以使用二分查找法，当数据增大 n 倍时，耗时增大 logn 倍（这里的 log 是以 2 为底的，每找一次排除一半的可能）。

链表