我很好奇为什么从双链表中删除节点比从单个链接列表中删除节点更快。 根据我的讲座，双链表需要 O(1(，而单链表需要 O(n(。根据我的思考过程，我认为它们都应该是O(n(，因为您必须遍历可能的所有元素，因此这取决于大小。
我知道它将与每个节点都有一个前一个指针和一个指向下一个节点的下一个指针这一事实相关联，我只是无法理解它如何在 O(1( 的意义上是一个常量操作
这部分取决于您如何解释设置。 这里有两个不同的版本。
版本 1：假设您要从单链表或双向链表中删除包含特定值 x 的链表节点，但您不知道它在列表中的哪个位置。 在这种情况下，您必须遍历列表，从开头开始，直到找到要删除的节点。 在单链和双链表中，您可以在 O(1( 时间内将其删除，因此整个运行时为 O(n(。 也就是说，在单向链表中执行删除步骤比较困难，因为您需要更新前一个单元格中的指针(该指针不是要删除的单元格指向的(，因此您需要在执行此操作时存储两个指针。
版本2：现在，假设您有一个指向要删除的单元格的指针，并且需要将其删除。 在双向链表中，可以使用下一个和上一个指针来标识要删除的单元格周围的两个单元格，然后重新连接它们以将单元格拼接出列表。 这需要时间 O(1(。 但是单链表呢？ 若要从列表中删除此单元格，必须更改要删除的单元格之前显示的单元格的下一个指针，使其不再指向要删除的单元格。 遗憾的是，您没有指向该单元格的指针，因为该列表仅是单链接的。 因此，您必须从列表的开头开始，向下走过节点，然后找到紧挨着要删除的节点之前的节点。 这需要时间 O(n(，因此在最坏的情况下，删除步骤的运行时间为 O(n(，而不是 O(1(。 (也就是说，如果您知道两个指针 - 要删除的单元格和它之前的单元格，那么您可以在 O(1( 时间内删除该单元格，因为您不必扫描列表来查找前面的单元格。
简而言之：如果您事先知道要删除的单元格，则双向链表允许您在时间 O(1( 内删除它，而单向链表则需要时间 O(n(。 如果您事先不知道单元格，那么在这两种情况下都是 O(n(。
希望这有帮助！
遍历该列表即可将前一个节点连接到双链表中的下一个节点。你只需指出
curr.Prev.Next = curr.Next和 curr.Next.Prev = curr.Prev .
在单链表中，您必须遍历列表才能找到前一个节点。遍历可以是非排序列表中的 O(n(。
另一种方法似乎是使用双指针，如这个优秀的资源：https://github.com/mkirchner/linked-list-good-taste。这意味着您不需要跟踪当前和以前的指针，因为您只使用可以直接就地修改的指向指针的单个指针。如果这不准确，请告诉我，因为我刚刚了解到这一点。