数组与链表学习总结

一、数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

该定义几个关键词解析：

1 线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。如下图数组其下标是从 0 开始的线性表。有线性表，它相对立的概念则是非线性表。

数组示意图

非线性表比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

2 连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

那么数组插入和删除为什么低效呢？有哪些改进方法？

数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效。

插入操作：其时间复杂度是 O(n)，其计算过程如下，假设有一个数组 array[10]，有 5 个元素 a,b,c,d,e。若在开头位置插入 f，那么 a,b,c,d,e 的位置都需要往后移动，若在第 3 个位置插入也就 b 后面插入，那么 c,d,e 则需要往后移动，最好的情况，若在最后 e 后面插入，则 a,b,c,d,e 都不需要移动。因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 (1+2+...n)/n=O(n)。

改进插入：同上加入插入元素 f 到第 3 个“c”的位置，这时我们将“c”移动到最后，将“f”放进原来“c”的位置，这样其时间复杂度就可以降低为 O(1)。

删除操作：其时间复杂度是 O(n)，其计算过程如下，同样，假设有一个数组 array[10]，有 5 个元素 a,b,c,d,e。跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为 O(n)。

改进删除：同上例题假设我们要依次删除 a,b,c，为了避免 d,e 这两个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。如果你了解 JVM，你会发现，这不就是 JVM 标记清除垃圾回收算法的核心思想吗？数据结构和算法的魅力就在于此，很多时候我们并不是要去死记硬背某个数据结构或者算法，而是要学习它背后的思想和处理技巧，这些东西才是最有价值的。

二、链表

学习完数组，接下来我们看下链表。链表结构五花八门，今天我重点给你介绍三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。我们首先来看最简单、最常用的单链表。

单链表其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

循环链表是一种特殊的单链表。单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。如循环链表图所示，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。

双向链表支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。那相比单链表，双向链表适合解决哪种问题呢？

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

双向链表中的结点保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对删除给定指针指向的结点，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了。

三、数组与链表比较

时间复杂度比较

优缺点分析