c++ 单向链表和双向链表有什么区别?各自有什么优缺点?

如题所述

一、指代不同

1、双向链表:也叫双链表,是链表的一种,每个数据结点中都有两个指针,分别指向直接后继和直接前驱

2、单向链表:是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

二、优点不同

1、双向链表:从双向链表中的任意一个结点开始,都可以很方便地访问前驱结点和后继结点。

2、单向链表:单个结点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小,结点的访问方便,可以通过循环或者递归的方法访问到任意数据。


三、缺点不同

1、双向链表:增加删除节点复杂,需要多分配一个指针存储空间。

2、单向链表:结点的删除非常方便,不需要像线性结构那样移动剩下的数据,但是平均的访问效率低于线性表

参考资料来源:百度百科-双向链表

参考资料来源:百度百科-单向链表

温馨提示:内容为网友见解,仅供参考
第1个回答  推荐于2019-10-16

单向链表和双向链表的区别:

一、方向不同

1、单向链表:只有一个指向下一结点的指针,也就是只能next。

2、双向链表:除了有一个指向下一结点的指针外,还有一个指向前一结点的指针,可以通过prev()快速找到前一结点。

二、使用情况不同

1、单向链表:适用于节点的增加删除。

2、双向链表:适用于需要双向查找节点值的情况。

三、读取不同

1、单向链表:只能单向读取。

2、双向链表:可以双方向读取。

单向链表和双向链表的区别可看下图:

单向链表的优点和缺点:

1、单向链表:只有一个指向下一个节点的指针。

2、优点:单向链表增加删除节点简单。遍历时候不会死循环;

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

4、适用于节点的增加删除。

双向链表的优点和缺点:

1、双向链表:有两个指针,一个指向前一个节点,一个后一个节点。

2、优点:可以找到前驱和后继,可进可退;

3、缺点:增加删除节点复杂,多需要分配一个指针存储空间。

4、适用于需要双向查找节点值的情况。

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;

列表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向nuLL的指针。

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

参考资料:百度百科-单向链表

参考资料:百度百科-双向链表

本回答被网友采纳
第2个回答  推荐于2019-09-28

1、指向不同:单向链表只有一个指向下一结点的指针,双向链表除了有一个指向下一结点的指针外,还有一个指向前一结点的指针。

2、功能不同:单向链表只能next ,双向链表可以return。

3、单双向不同:单链表只能单向读取,双向链表可以通过prev()快速找到前一结点。

单向链表优缺点:

1、优点:单向链表增加删除节点简单。遍历时候不会死循环;

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

双向链表优缺点:

1、优点:可以找到前驱和后继,可进可退;

2、缺点:增加删除节点复杂,多需要分配一个指针存储空间。

扩展资料:

单向链表和双向链表适用的情况:

单向链表适用于节点的增加删除。

双向链表适用于需要双向查找节点值的情况。

循环链表:

循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。

参考资料:百度百科-单向链表

百度百科-双向链表

本回答被网友采纳
第3个回答  2019-07-08

区别:

一、意思不同

单向链表包含两个域,一个是信息域,一个是指针域。也就是单向链表的节点被分成两部分,一部分是保存或显示关于节点的信息,第二部分存储下一个节点的地址,而最后一个节点则指向一个空值。

双向链表是每个节点有2个链接,一个是指向前一个节点(当此链接为第一个链接时,指向的是空值或空列表),另一个则指向后一个节点(当此链接为最后一个链接时,指向的是空值或空列表),意思就是说双向链表有2个指针,一个是指向前一个节点的指针,另一个则指向后一个节点的指针。

二、使用场景不同

单向链表适用于节点的增加删除,双向链表适用于需要双向查找节点值的情况。

三、用法不同

每个双链表的节点要比单链表的节点多一个指针,而长度为n就需要 n*length(这个指针的length在32位系统中是4字节,在64位系统中是8个字节) 的空间,这在一些追求时间效率不高应用下并不适应,因为它占用空间大于单链表所占用的空间;这时设计者就会采用以时间换空间的做法,这时一种工程总体上的衡量。

优缺点:

一、单向链表

优点:单向链表增加删除节点简单。遍历时候不会死循环。

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

二、双向链表

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

缺点:增加删除节点复杂,需要多分配一个指针存储空间。

本回答被网友采纳
第4个回答  2019-07-07

一、结构不一样

1、单向链表:每个节点由一个数据域和一个指针域构成。

2、双向链表:每个节点由一个数据域和两个指针域构成。

二、方向不一样

1、单向链表:只能单向进行读取,也就是只能找到下一个节点。

2、双向链表:可以双向进行读取,既可以找到下一个节点,也可以找到上一个节点。

三、适用不一样

1、单向列表:适用于单向遍历,存储空间小的数据。

2、双向列表:适用于双向遍历数据。

单向链表的优缺点:

1、优点:存储空间小,增加删除节点简单。

2、缺点:只能从头到尾遍历。只能找到后继节点,无法找到前驱节点。

双向链表的优缺点:

1、优点:可以双向遍历,既能找到后继节点,也能找到前驱节点。从任一节点都可以访问到其他所有节点。

2、缺点:存储空间大,增加删除节点较复杂。

扩展资料

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点组成,每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

参考资料来源:百度百科-单向链表

参考资料来源:百度百科-双向链表

本回答被网友采纳
相似回答