单链接列表和双重链接列表之间的区别

单链接列表与双重链接列表

链接列表是一种线性数据结构，用于存储数据集合。链接列表将内存分别分别在其自己的内存块中分别分配给其元素，并且通过将这些元素链接为链中的链接来获得整体结构。单个链接的列表由一个节点序列组成，每个节点都会引用序列中的下一个节点。双重链接列表包含一个节点序列，其中每个节点包含对下一个节点以及上一个节点的引用。

单链接列表

单个链接列表中的每个元素都有两个字段，如图1所示。数据字段保存了存储的实际数据，下一个字段保留对链中下一个元素的引用。链接列表的第一个元素存储为链接列表的头部。

图2描绘了一个单独的链接列表，其中包含三个元素。每个元素都存储其数据和所有元素，除了最后一个存储一个对下一个元素的引用。最后一个元素在其下一个字段中具有空值。列表中的任何元素都可以通过从头部开始并遵循下一个指针来访问，直到您满足所需的元素为止。

双链接列表

双链接列表中的每个元素都有三个字段，如图3所示。类似于单链接的列表，数据字段保存了存储的实际数据，下一个字段将其引用对链中的下一个元素。此外，上一个字段保留对链中先前元素的引用。链接列表的第一个元素存储为链接列表的头部。

图4描绘了一个双重链接的列表，其中包含三个元素。所有中间元素存储了对第一个和上一个元素的引用。列表中的最后一个元素在其下一个字段中具有空值，并且列表中的第一个元素在其上一个字段中具有空值。可以通过遵循每个元素中的下一个引用来向前穿越双重链接列表，并可以使用每个元素中的先前参考文献向后遍历。

单链接列表和双重链接列表之间有什么区别？

单链接列表中的每个元素都包含对列表中下一个元素的引用，而双重链接列表中的每个元素都包含对下一个元素以及列表中的上一个元素的引用。双重链接列表需要列表中每个元素的更多空间，并且基本操作（例如插入和删除）更为复杂，因为它们必须处理两个参考。但是双重链接列表可以更轻松地操作，因为它允许在向前和向后的方向上穿越列表。