单链表与双链表
链表是一种用于存储数据集合的线性数据结构。链表在它自己的内存块中将内存分别分配给它的元素,通过将这些元素作为链中的链接链接来获得整体结构。单链表由一系列节点组成,每个节点都有对序列中下一个节点的引用。双链接列表包含一个节点序列,其中每个节点都包含对下一个节点和上一个节点的引用。
单链表
单链链表中的每个元素都有两个字段,如图1所示。数据字段保存存储的实际数据,下一个字段保存对链中下一个元素的引用。链接列表的第一个元素的头被存储为链表的第一个元素。
图2描述了一个包含三个元素的单链表。每个元素存储其数据,除最后一个元素外的所有元素都存储对下一个元素的引用。最后一个元素的下一个字段中包含一个空值。列表中的任何元素都可以通过从开头开始并跟随下一个指针来访问,直到满足所需的元素为止。
双链表
双链接列表中的每个元素都有三个字段,如图3所示。下一个数据链保存与下一个单独链接的字段的数据,而下一个数据链则保存与实际数据链相类似的数据。另外,previous字段保存对链中上一个元素的引用。链接列表的第一个元素的头被存储为链表的第一个元素。
图4描述了一个包含三个元素的双链接列表。所有中间元素都存储对第一个和前一个元素的引用。列表中的最后一个元素在其下一个字段中保留空值,而列表中的第一个元素在其上一个字段中保留空值。双链表可以通过跟随每个元素中的下一个引用向前遍历,同样可以使用每个元素中的前一个引用向后遍历。
单链表和双链表有什么区别?