本文共 4744 字，大约阅读时间需要 15 分钟。

目录

    

    

    

    

    

    

    

    

    

 

一、线性表

线性表：数据元素排成一条线的一种逻辑结构。

特点：元素最多只有前后两个方向，即，数据之间是简单的前后关系（数据之间的关系）

为了实现这种可以描述现实事物的逻辑的结构，我们有两种实现方式，一种是物理结构上也连续的顺序表（数组），一种是物理上没有关系的链式表（链表）。

二、数组

1、数组的定义

数组：一种线性表的数据结构，用一段连续的内存空间，存储一组相同类型的数据+利用物理的连续型表达数据之间的前后关系。

数组的常见操作有：插入、删除、按位查找、修改、按值查找。

其中，注意数组一旦创建，它的最大容量就确定下来了，不管你怎么操作，数组的空间大小都不会变。比如，当插入一个元素时，数组并没有增加一个单位的内存空间。但是，数组的元素个数会变，元素个数和数组大小不是一回事。

其次，数组的其他空间是存在值的，只不过是我们忽略它们而已。我们会有个隐藏的边界（或者说逻辑上的边界），边界之内的数据才是数组元素，边界之外的尽管在我们申请的空间之内，但是我们认为它们不存在。

2、数组随机访问特性的实现

总的来说，数组之所以可以随机访问，有两个原因：连续的内存空间+相同类型的数据。

我们知道，计算机会给每个内存单元都分配一个地址，然后计算机通过地址访问内存中的数据。

当计算机要随机访问数组的某个元素时，会通过寻址公式，计算出该元素的内存地址：

address of a[i] = base_address + i * data_type_size

这也就是数组的内存模型，可以看到，连续的内存空间让计算机知道要找下一个元素往哪里走；相同类型的数据让计算机知道，走到哪里算一个数据。而这就是数组可以随机访问的原因。

3、为什么数组不是从1开始，从1开始不是更符合人类的思维吗？

关于这个问题，可能有2个原因。

其一是历史原因。很多高级语言都是模仿C语言的设计，而C语言的数组就是从0开始的。当然，有些语言不是，像MATLAB就不是从0开始，Python则支持负数的下标（这个下标好像可以理解成偏移，Python的正数下标理解成从首元素正向偏移多少个元素？负数下标理解成从尾元素逆向偏移多少个元素？）。

其二从数组存储的内存模型来看。若用a表示数组a的首地址，则a[0]的地址为偏移为0的位置，即首地址；a[k]的地址为偏移为k个data_type_size内存的位置。所以，我们计算a[k]内存地址只需用：address of a[k] = base_address + k * data_type_size

但是，如果是从1开始的话，计算a[k]的内存地址就变成：address of a[k] = base_address + (k-1) * data_type_size

这么一来，每次随机访问数组元素就多了一次减法运算，对CPU来说就多了一次减法操作的指令。而数组作为非常基础的数据结构，又是经常用到随机访问的操作，所以效率问题应该尽可能的做到极致。这大概就是从0开始的原因吧。

4、数组的访问越界问题

计算机通过上面讲的数组内存模型，访问数组元素。访问数组的本质是访问一段连续的内存。

在C语言中，只要不是访问受限的内存，所有的内存空间都可以自由访问。当数组越界时，C的编译器没有被指示怎么处理。只要数组通过偏移计算得到的内存地址是可用的，那么程序就很可能不会报错。

而在Java中，Java编译器会帮开发人员做数组越界检查。看下面例子。

#include 
   
    int main(){   int i = 0;   int arr[3] = {0};	   for (; i<=3; i++) {      arr[i] = 5;      printf("hello world\n");   }       return 0;}
   

在某些环境下，这段程序会打印出4个hello world，而第四次执行时，尽管arr数组没有arr[3]这个元素，但是编译却通过，运行也没有出现一些明显的问题。这样一来，在实际开发中，就很可能出现这样的情况：看似程序运行正常，但其中有个致命的bug，只是还没有爆发严重问题而已。

此外，如果arr[3]恰恰是变量i的地址，而循环中的arr[i]=5  改成  arr[i]=0，就可能出现这种情况：当控制循环的变量 i 增加到3的时候，由于arr[3]=0这句代码，将 i 的值重新赋为0，这就导致死循环的出现了。

public class Array {	public static void main(String[] args) {		int[] arr = new int[3];		arr[3] = 10;	}}

在Java中，编译时不会检查出问题，但是运行时会报出数组越界的异常：

关于C语言数组的操作可以再看看下面这个例子。

#include 
   
    int main(){   int a[5] = {1, 2, 3, 4, 5};   int *ptr = (int*)(&a + 1);   printf("%d, %d", *(a+1), *(ptr-1));      return 0;}
   

这个例子的输出是：

C语言的取值符号&有这么一个特点，它取的地址进行加1减1操作的效果，取决于取地址值的对象。像上面&a对数组a进行取地址，当地址加1时，是在所取的地址的基础上偏移一个数组长度的内存大小。而(int *)将单位长度为一个数组大小的地址 强制转化为单位长度为一个数组元素大小的地址，所以当ptr减1时，反方向偏移一个数组元素长度的内存大小，即指向a[4]。故*(ptr-1)打印出来的值是5。

三、链表

1、单链表

单链表：数据元素分为两部分的线性表结构，一部分存放数据——数据域，一部分存放下一个元素的地址——地址域（C中用指针，Java中用引用）。因为单链表的元素是（物理上）离散地分布在内存中，所以要找到某元素的下一个元素，就要依靠存放地址的那一部分了。

单链表（带头结点的单链表）的2个特殊结点：

（1）头结点：记录链表的基地址，从而可以逐一遍历得到整条链的元素。

这里的逐一是说每次都只关注两个结点，后面的结点“接过”前者的接力棒，通过地址域找到它的下一个结点，然后就不管了，接力棒传给下一个结点，这样一步一步直到传不下去为止。这个有点像网络通信中路由的某个协议：内网的边界路由只负责把数据包传给自己边界的某个路由，后面怎么传它一概不管。数据包在一个个网络两两之间逐一传递，最终到达目标的网络。

（2）尾结点：它的地址域指向的不是一个结点，而是一个空地址NULL。

2、循环链表

循环链表：在单链表的基础上，尾指针的地址域指向链表的头结点（与单链表的唯一区别）

适合处理的数据：带有环形结构的特点，如，约瑟夫问题

3、双向链表

双向链表：在单链表的基础上，数据结点多了个指向前面结点的地址域，也就是说，双向链表有2个方向，每个元素既可以往后走，又可以向前走。

4、循环双向链表

循环双向链表：在双向链表的基础上，让尾结点的next地址域指向头结点，让头结点的prev地址域指向尾结点。

5、各种链表的对比

循环链表vs单链表：循环链表适合多次遍历链表的场景。头指针遍历到尾结点时可以重新回到头结点，而单链表则只能重新创造一个指针把链表指针的地址值赋给它，作为头指针，才能开始新一轮遍历。

双向链表vs单链表：

双向链表在实际开发中执行插入、删除操作时更高效。

删除操作无非两种情况：（1）删除结点中值等于某个给定值的结点；（2）删除给定指针指向的结点。

对于第一种情况，无论是单链表还是双向链表都需要从头结点开始进行遍历，遍历到待删除结点时，就变成（2）这种情况了，这时头指针指向待删除结点。

但是，链表要想删除某个结点，必须借助该结点的前一个结点。而单链表不支持直接找到前驱结点，仍要从头再遍历一次（O(n)）。而双向链表只需通过待删除结点的prev地址域就可以找到它的前驱结点了(O(1))。

同理，在链表的某个结点前面插入一个结点的场景中，双向链表也是有优势。

在一些特殊情况下的查找，双向链表的查找的效率也是高一些。

比如有一个有序链表，要按值查找某个结点。采用双向链表的话，可以记录上次查找的位置p结点，每次进行查找时，根据待查找的值与p结点的值的大小关系，决定是往后找or向前找。平均情况下，这种查找方式，只需查找一半的数据。

四、数组和链表（单链表）的对比

单链表不再像数组那样，采用物理内存的连续性来表示线性表元素之间的一一对应关系，从而优化了插入、删除操作（优势）。但是，与此同时，在访问第k个元素的时候，单链表也无法像数组那样，根据首地址和下标通过寻址公式直接求出对应的内存地址，再由地址访问得到元素值（弊端）。

此外，数组的另一个缺点是大小固定，一经声明就要占用整块连续内存空间，如果声明的数组过大，可能造成浪费；如果过小，则可能不够用，只能通过重新申请一块内存、再把原数组的内容拷贝过去的方式扩容，而数据的拷贝一般比较费时。链表则没有大小的限制，天生支持动态扩容。

而链表的另一个缺点是比较耗空间：链表的每个结点需要额外的存储空间来存放地址值。而且，对链表的频繁删除、插入，容易造成内存碎片。在Java语言中，这将导致频繁的垃圾回收操作。

两种结构在进行增删改查等操作时，时间复杂度如下所示：

	数组	链表
插入、删除	O(n)	O(1)
查询、修改（按位）	O(1)	O(n)

这个是各种教材给出的。不过我觉得这里链表插入、删除的O(1)应该加个前提，那就是已经找到要插入、删除的位置的前一个结点。否则，由于链表只有一个头指针（引用）和一个固定不动的链表指针（引用），链表在进行这两种操作时，要靠头指针移动到待处理位置上的前一个结点，这个过程是线性的，算上该过程的话，链表在插入、删除时，还是O(n)。只不过这个O(n)与数组进行插入、删除操作时的O(n)效率要高一点：数组是移动操作，链表只是遍历，不做移动运算，而移动操作是比较耗时间的。比如说一个是执行了2*n条机器指令，一个则执行了10*n条，同样是O(n)，显然系数小的快。

此外，数组的插入操作一定是O(n)吗？不一定，具体情况还需具体分析。上面的O(n)其实应该有个隐藏的前提条件——在插入某个位置的时候，要保持已有的元素的位置相对不变（稳定性）。但如果我们不用管这个，只管插入就行，则可以这样做：直接把第k位（插入位置）的元素搬到最后面，新元素放入第k位即可。这么一来，就不用执行大量移动操作了，复杂度就降为O(1)。快排好像体现的就是这种思想。

还有，在某些特殊场景，数组的删除操作也可能这样提高效率：每次进行删除操作时，不要马上搬移元素，而是做个标记表示该数据已经被删除。当数组没有更多的空间存储数据时，再触发一次搬移元素的操作。这么一来就大大减少了删除操作导致的数据搬移。JVM的垃圾回收机制，用的貌似也是这种思想：当一些对象没有了引用时，它们不会被马上销毁，而是在一段时间之后，由垃圾回收器统一回收内存。

总之，若运行代码的地方内存十分有限，则采用数组（时间换取空间）；若线性表是通过在高端进行插入操作建成的，且建成之后只发生对数组的访问操作，那么就适合采用数组的顺序结构的实现方式；若线性表经常涉及增、删等操作，且在发生变动时知道将要发生的地方，那么采用链表则无需执行大量的移动操作，所以采用链表的离散结构更合适；后面两条原则只适合普遍情况，一些特殊的场景可能不一定是这样。

 

转载地址：http://pbnii.baihongyu.com/