c++ 单向链表和双向链表有什么区别？各自有什么优缺点？
一、指代不同
1、双向链表：也叫双链表，是链表的一种，每个数据结点中都有两个指针，分别指向直接后继和直接前驱
2、单向链表：是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。
二、优点不同
1、双向链表：从双向链表中的任意一个结点开始，都可以很方便地访问前驱结点和后继结点。
2、单向链表：单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小，结点的访问方便，可以通过循环或者递归的方法访问到任意数据。
三、缺点不同
1、双向链表：增加删除节点复杂，需要多分配一个指针存储空间。
2、单向链表：结点的删除非常方便，不需要像线性结构那样移动剩下的数据，但是平均的访问效率低于线性表。
参考资料来源：百度百科-双向链表
参考资料来源：百度百科-单向链表
单向链表和双向链表的区别：
一、方向不同
1、单向链表：只有一个指向下一结点的指针，也就是只能next。
2、双向链表：除了有一个指向下一结点的指针外，还有一个指向前一结点的指针，可以通过prev()快速找到前一结点。
二、使用情况不同
1、单向链表：适用于节点的增加删除。
2、双向链表：适用于需要双向查找节点值的情况。
三、读取不同
1、单向链表：只能单向读取。
2、双向链表：可以双方向读取。
单向链表和双向链表的区别可看下图：
单向链表的优点和缺点：
1、单向链表：只有一个指向下一个节点的指针。
2、优点：单向链表增加删除节点简单。遍历时候不会死循环；
3、缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。
4、适用于节点的增加删除。
双向链表的优点和缺点：
1、双向链表：有两个指针，一个指向前一个节点，一个后一个节点。
2、优点：可以找到前驱和后继，可进可退；
3、缺点：增加删除节点复杂，多需要分配一个指针存储空间。
4、适用于需要双向查找节点值的情况。
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
参考资料：百度百科-单向链表
参考资料：百度百科-双向链表
1、指向不同：单向链表只有一个指向下一结点的指针，双向链表除了有一个指向下一结点的指针外，还有一个指向前一结点的指针。
2、功能不同：单向链表只能next ，双向链表可以return。
3、单双向不同：单链表只能单向读取，双向链表可以通过prev()快速找到前一结点。
单向链表优缺点：
1、优点：单向链表增加删除节点简单。遍历时候不会死循环；
2、缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。
双向链表优缺点：
1、优点：可以找到前驱和后继，可进可退；
2、缺点：增加删除节点复杂，多需要分配一个指针存储空间。
扩展资料：
单向链表和双向链表适用的情况：
单向链表适用于节点的增加删除。
双向链表适用于需要双向查找节点值的情况。
循环链表：
循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
参考资料：百度百科-单向链表
区别：
一、意思不同
单向链表包含两个域，一个是信息域，一个是指针域。也就是单向链表的节点被分成两部分，一部分是保存或显示关于节点的信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值。
双向链表是每个节点有2个链接，一个是指向前一个节点（当此链接为第一个链接时，指向的是空值或空列表），另一个则指向后一个节点（当此链接为最后一个链接时，指向的是空值或空列表），意思就是说双向链表有2个指针，一个是指向前一个节点的指针，另一个则指向后一个节点的指针。
二、使用场景不同
单向链表适用于节点的增加删除，双向链表适用于需要双向查找节点值的情况。
三、用法不同
每个双链表的节点要比单链表的节点多一个指针，而长度为n就需要 n*length（这个指针的length在32位系统中是4字节，在64位系统中是8个字节） 的空间，这在一些追求时间效率不高应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这时一种工程总体上的衡量。
优缺点：
一、单向链表
优点：单向链表增加删除节点简单。遍历时候不会死循环。
缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。
二、双向链表
优点：可以找到前驱和后继，可进可退。
缺点：增加删除节点复杂，需要多分配一个指针存储空间。
一、结构不一样
1、单向链表：每个节点由一个数据域和一个指针域构成。
2、双向链表：每个节点由一个数据域和两个指针域构成。
二、方向不一样
1、单向链表：只能单向进行读取，也就是只能找到下一个节点。
2、双向链表：可以双向进行读取，既可以找到下一个节点，也可以找到上一个节点。
三、适用不一样
1、单向列表：适用于单向遍历，存储空间小的数据。
2、双向列表：适用于双向遍历数据。
单向链表的优缺点：
1、优点：存储空间小，增加删除节点简单。
2、缺点：只能从头到尾遍历。只能找到后继节点，无法找到前驱节点。
双向链表的优缺点：
1、优点：可以双向遍历，既能找到后继节点，也能找到前驱节点。从任一节点都可以访问到其他所有节点。
2、缺点：存储空间大，增加删除节点较复杂。
扩展资料
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点组成，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
参考资料来源：百度百科-单向链表
参考资料来源：百度百科-双向链表
|
广告 您可能关注的内容 |
