数组与链表

一、数组

数组是一种线性表数据结构，有一组连串的存储空间，来存储相同数据类型的数据。

1、存储结构

2、时间复杂度

插入、删除操作：插入到的Index后的所有元素需要挪动位置，所以时间复杂度为O(n)。
如果刚好插入最后一个元素则为O(1)，插入到最前面则需要移动所有元素O(n)。
查询操作：根据index直接返回，时间复杂度为O(1)。

3、注意

3.1 为什么数组查询速度快？

由于数组的数据在内存中是连续存储的，计算机会给每个内存单元分配一个地址，通过地址访问内存中存储的数据。所以数组每存储的数据单元都拥有自己唯一的地址。计算机寻址计算公式：
data_type_size为每个元素的大小，例如int结构则为4个字节。并不是数组查询快，所有的复杂度都为O(1)，准确说法应该是数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。

3.2 并不是所有的插入操作时间复杂度都为O(n)

插入操作：数组的一般插入操作，为了保证内存的连续性需要将插入到的位置之后的所有元素向后移动，或者要删除的位置元素向前移动。但是在快排中有一种做法，可以将数组插入时间复杂度降为O(1)，前提是该数组无排序要求，可以将要插入的元素与原元素位置进行互换，将原元素放到末尾。
删除操作：可以参考JVM中标记清除原理，将要删除的元素进行记录，数组中并不是真正的删除，当数组存储空间不够时，再将删除的元素一起全部删除。

3.3 数组越界问题

由于数组在内存中的大小是固定的，所以在操作过程中会出现越界问题。

3.4 数组和容器ArrayList等区别？

ArrayList对于数组的优点：支持动态扩容，每次内存不够时将会自动扩大1.5倍，可以封装数组。
容器对比数组的缺点：每次动态扩容时需要不断的搬移数据，比较耗时，建议创建时指定大小；java 容器无法存储基本数据类型，需要进行封箱消耗性能，存储基本数据类型建议使用数组

二、链表

解决数组结构插入和删除时间复杂度问题。适用于插入和删除操作，自动扩容的操作。

1、存储结构

1.1单链表：

将零散的内存串联起来，每个结点不仅存储数据，还需要存储指向下一个结点的地址，此结点称为后继指针。

1.2 双向链表：

和单链表的区别：单链表只有一个指针指向下一个结点，双向链表一个结点分别有前驱指针（指向前一结点）、后继指针（指向后一结点）。
优点：双向指针，操作灵活
缺点：内存需要多存储两个指针，较其他链表内存消耗高；
适用：由于双向指针，插入和删除更适合，更常用

1.3 循环链表

和单链表的区别是，尾指针不是指向空，而是指向头结点。
优点：链尾到链头比较方便，例如约瑟夫问题。

2、时间复杂度

插入和删除操作：只需要将新节点的指针指向进行改变，时间复杂度为O(1)，
查找操作：需要从头进行遍历，时间复杂度为O(n)。

3、与数组的区别

3.1 内存申请

1. 数组存储是连续的内存空间，如果此时需要100M的空间，即使内存中有100M但是不连续依旧无法使用；链表使用指针将零散的内存块串联，可以很好的利用内存空间。

4、链表练习推荐

单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第 n 个结点
求链表的中间结点