2014年软考程序员常考知识点复习笔记第七章

 数组和链表的优缺点

　　数组，在内存上给出了连续的空间。链表，内存地址上可以是不连续的，每个链表的节点包括原来的内存和下一个节点的信息(单向的一个，双向链表的话，会有两个)。

　　数组优于链表的:

　　A. 内存空间占用的少，因为链表节点会附加上一块或两块下一个节点的信息。

　　但是数组在建立时就固定了。所以也有可能会因为建立的数组过大或不足引起内存上的问题。

　　B. 数组内的数据可随机访问，但链表不具备随机访问性。这个很容易理解，数组在内存里是连续的空间，比如如果一个数组地址从100到200，且每个元素占用两个字节，那么100-200之间的任何一个偶数都是数组元素的地址，可以直接访问。

　　链表在内存地址可能是分散的。所以必须通过上一节点中的信息找能找到下一个节点。

　　C. 查找速度上。这个也是因为内存地址的连续性的问题，不罗索了。

　　链表优于数组的:

　　A. 插入与删除的操作。如果数组的中间插入一个元素，那么这个元素后的所有元素的内存地址都要往后移动。删除的话同理。只有对数据的最后一个元素进行插入删除操作时，才比较快。链表只需要更改有必要更改的节点内的节点信息就够了。并不需要更改节点的内存地址。

　　B. 内存地址的利用率方面。不管你内存里还有多少空间，如果没办法一次性给出数组所需的要空间，那就会提示内存不足，磁盘空间整理的原因之一在这里。而链表可以是分散的空间地址。

　　C. 链表的扩展性比数组好。因为一个数组建立后所占用的空间大小就是固定的，如果满了就没法扩展，只能新建一个更大空间的数组;而链表不是固定的，可以很方便的扩展。