加载中…
个人资料
第三只眼
第三只眼
  • 博客等级:
  • 博客积分:0
  • 博客访问:9,691
  • 关注人气:1
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

单向链表,双向链表,循环链表,数组之间的比较(理论)

(2013-06-08 17:28:58)
标签:

it

分类: 软件开发

链表:

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必按顺序存储,链表在插入的时候可以达到O⑴的复杂度,比另一种线性表:顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O⑴。使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。在计算机科学中,链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成,每个节点包含任意的实例数据(data fields)和一或两个用来指向上一个/或下一个节点的位置的链接("links")。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针(链接)。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。链表可以在多种编程语言中实现。像LispScheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言,如C,C++Java依靠易变工具来生成链表

 

循环链表:

循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。循环链表的运算与单链表的运算基本一致。所不同的有以下几点:

  1、在建立一个循环链表时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。

  2、在判断是否到表尾时,是判断该结点链域的值是否是表头结点,当链域值等于表头指针时,说明已到表尾。而非象单链表那样判断链域值是否为NULL

 

 

双向链表

  双向链表其实是单链表的改进。当我们对单链表进行操作时,有时你要对某个结点的直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域,那么能不能定义一个既有存储直接后继结点地址的链域,又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢?这就是双向链表。在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点地址,一般称之为右链域;一个存储直接前驱结点地址,一般称之为左链域。

 

优缺点:

单向链表:

 优点:单向链表增加删除节点简单。遍历时候不会死循环。(双向也不会死循环,循环链表忘了进行控制的话很容易进入死循环)

 缺点:只能从头到尾遍历。只能找到后继,无法找到前驱,也就是只能前进。

 

双向链表:

 优点:可以找到前驱和后继,可进可退。

 缺点:增加删除节点复杂(其实就复杂一点点)


实现上的主要区别:

单向链表和双向循环链表最大的不同就是头结点是否是哑元。双向循环链表由于head是哑元,因此取元素从head的下一个结点取。单向链表:head不是哑元,第一次必须取head头结点的元素,因此循环上和双向循环链表不同。也就是第一次get并没有进入for循环,直接返回了头结点,从第二次才开始进入for循环,这里要特别注意。


一般应用中单向链表或循环链表居多,双向链表不常用。当然特殊条件下双向链表很方便。尤其是需要查询到某个节点后再查其前驱的工作中。


 

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有