单链表和双链表的区别

单链表：单链表是一组节点，其中每个节点有两个字段“数据”和“链接”。 “数据”字段存储实际信息，“链接”字段用于指向下一个节点。基本上，“链接”字段存储下一个节点的地址。

双向链表： 双向链表(DLL)包含一个额外的指针，通常称为前一个指针，以及单链表中的下一个指针和数据。

单链表 (SLL)	双链表 (DLL)
SLL 节点包含 2 个字段 – 数据字段和下一个链接字段。	DLL 节点包含 3 个字段 – 数据字段、前一个链接字段和一个下一个链接字段。
在 SLL 中，只能使用下一个节点链接来完成遍历。因此，只能在一个方向上遍历。	在 DLL 中，可以使用前一个节点链接或下一个节点链接来完成遍历。因此，可以在两个方向(向前和向后)进行遍历。
SLL 占用的内存比 DLL 少，因为它只有 2 个字段。	DLL 比 SLL 占用更多的内存，因为它有 3 个字段。
在给定位置插入和删除的复杂度是 O(n)。	在给定位置插入和删除的复杂性是 O(n / 2) = O(n)，因为可以从头开始或从尾端进行遍历。
给定节点的删除复杂度为 O(n)，因为需要知道前一个节点，遍历需要 O(n)	给定节点的删除复杂度为 O(1)，因为可以轻松访问前一个节点。
最喜欢使用单链表来执行堆栈。	可以使用双向链表来执行堆和栈，二叉树。
当不需要执行任何搜索操作并且想要节省内存时，更喜欢单链表。	为了更好的实现，在搜索时，更喜欢使用双向链表。
与双链表相比，单链表消耗的内存更少。	与单链表相比，双向链表消耗更多的内存。

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/264247.html