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

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

数组

数组（Array） 是一种很常见的数据结构。它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。

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

时间复杂度

• 通过下标（index）访问一个元素的时间复杂度为 O(1)，因为是直达的，无论数据增大多少倍，耗时都不变
• 数组末尾添加一个元素，时间复杂度为 O(1)
• 删除一个元素的时间复杂度为 O(n)，因为要遍历数组，数据量增大几倍，耗时也增大几倍
• 查找一个未排序的数组时间复杂度为 O(n)，因为要遍历数组；查找排序过的数组时间复杂度为 O(log n)，因为可以使用二分查找法，当数据增大 n 倍时，耗时增大 logn 倍（这里的 log 是以 2 为底的，每找一次排除一半的可能）

数组长度固定，不支持动态扩容。可以随机访问元素。

链表