2011年软考程序员考试复习笔试知识点整理(7)

来源:软件水平考试    发布时间:2012-11-05    软件水平考试视频    评论

  11、数组和链表的优缺点

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

  数组优于链表的:

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

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

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

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

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

  链表优于数组的:

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

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

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

视频学习

我考网版权与免责声明

① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;

② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。

最近更新

社区交流

考试问答