数据结构源头——数组和链表

一、数组

定义：是一种线性表结构数据，它用一组连续的内存空间来存储具有相同数据结构的数据。

线性表结构：数据排成一条线的数据结构，只有前后两种方法可以操作，常见的线性表结构数据有：数组、链表、栈、队列。

连续的内存空间：数组在申请内存地址时，内存空间必须是连续的，这样数组在随机访问某个数据的时间复杂度为O（1），但因为为了保存连续的内存结构其新增、修改时，存在挪动数据，性能低效。

如何提供随机访问一个数组中的元素的时间复杂度为O（1）？如下图所示，一个int需要占用4字节来存储，每个存储空间都会被分配一个地址，计算机通过访问内存地址来获取对应的数据，其寻址公式如下：

a[i]_address = base_address + i * data_type_size

# data_type_size 为每个元素的大小。所以说数组可以提供随机访问，并且随机访问的时间复杂度为O（1）

为什么插入和删除时，数组的性能低效呢？我们有一个大小为n的数组时， 当我们向第k（k < n）个位置插入一条数据时，为了保证数组的特性（连续的内存空间），这个时候需要将k～n位的数据都向后移动一位。所以当我们在数组的尾部插入一条数据，其时间复杂为O（1），当我们在第一位插入一条数据时，需要移动n个元素位置，时间复杂度为O（n），因为我们数据插入的位置是随机的，平均复杂度为（1 + 2 + 3 ...... + n）/ n,即为O（n），删除数组同理。

优化插入操作：就是我们在插入到在第k位时，只要将第k位的数据移动后最后面的位置，将插入的元素放到k位置即可，那么插入的时间复杂度为O（1）。

优化删除操作：就是我们在删除的时候，并不是真正的删除数据，而是将数据标记为删除，只有当数组空间不足时，再去执行真正的删除操作，这样可以避免频繁的进行数据搬移工作。类似java的JVM垃圾收集中的标记清除算法。

使用数组的注意事项：数组在使用时，需要指定数组的大小，当我们在使用过程中，添加的数组超过数组的初始容量时，会发生数组越界异常。

数组的一些实现：比如java中的Arraylist，其底层数据结构就是数组，Arraylist容器封装了一些对数组的操作，同时支持其动态扩容，可以防止发生数组越界问题，但是容器的扩容需要重新分配内存地址和移动数据，是一个比较耗时的操作，所以我们在使用容器时，可以根据需要存放的容量大小，预先设置一个合理的初始化值，防止容器频繁的进行扩容操作。

二、链表

定义：是一组非连续的内存空间串联起来的数据结构，通过指针将一组零散的内存空间串联起来，常见的链表结构为单链表、双向链表和循环链表。

单链表：保存数据块的位置我们称之为“结点”，单链表中的结点除了存储数据外，还需要额外存储一个指针，用来指向下一个结点的地址，这个记录下个结点地址称为后续指针，在链表结构中有两个特殊的结点，就是头部结点和尾部结点，头部结点没有next指针指向这个节点，头部结点中需要保存这个数据的基地址，尾部结点的next指向的是一个null结点，用来表示链表的结尾。

双向链表：相比于单链表，增加了一个prev结点用来指向上一级结点，提供了前后查找的能力。但是因为需要保存前后指针，需要占用更多的内存空间。并且在某些场景下，双向链表的插入和删除的性能比单向链表更快。

循环链表：就是一种特殊的单链表，与单链表的唯一区别就是，循环链表的尾部链表指向的不是一个null结点，而是指向头部结点。循环链表的特点就是从尾部结点到头部结点非常方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。

链表的插入，删除操作为什么性能高？链表在插入、删除数据时，只需要考虑其前后结点的变化，所以时间复杂度为O（1）。

链表的查找为什么性能慢？当访问链表中某个节点时，需要从头部结点依次遍历才能找到访问的节点，所以查找的时间复杂度为O（n）。

为什么双向链表的插入、删除操作性能优于单向链表？们要删除一个结点的数据，我们需要将删除节点的上一个节点的next修改为删除节点的下一个结点地址；因为单向链表无法从自身删除的节点直接插到自己的上层节点，需要从头开始遍历查找，当找到节点的next是自身地址时，才能确认上层节点；而双向链表直接定位上层节点，时间复杂度为O（1）。新增操作与删除操作类似。

基于LinkedList实现的双向链表代码解析：