Jam*_*lks 10 big-o pointers linked-list time-complexity data-structures
我很好奇为什么从双链表中删除节点比单个链表更快.根据我的讲座,双链表需要O(1),单个链表需要O(n).根据我的思考过程,我认为它们都应该是O(n),因为你必须遍历所有元素,所以它取决于大小.
我理解它与每个节点都有一个前一个指针和一个指向下一个节点的下一个指针这一事实有关,我只是无法理解它是如何在O(1)意义上的常量操作
tem*_*def 19
这部分取决于您如何解释设置.这是两个不同的版本.
版本1:假设您要从单个或双向链接列表中删除包含特定值x的链接列表节点,但您不知道它在列表中的位置.在这种情况下,您必须从头开始遍历列表,直到找到要删除的节点.在单链接和双链接列表中,您可以在O(1)时间内删除它,因此整个运行时间为O(n).也就是说,在单链表中执行删除步骤比较困难,因为你需要更新前一个单元格中的指针(要删除的单元格没有指向),所以你需要存储两个指针作为你做这个.
版本2:现在让我们假设您有一个指向要删除的单元格的指针,需要将其删除.在双向链表中,您可以使用下一个和上一个指针来识别要删除的单元格周围的两个单元格,然后重新连接它们以将单元格拼接出列表.这需要时间O(1).但是单链表怎么样？要从列表中删除此单元格,您必须更改要删除单元格之前出现的单元格的下一个指针,以便它不再指向要删除的单元格.不幸的是,您没有指向该单元格的指针,因为该列表仅是单链接的.因此,您必须从列表的开头开始,向下遍历节点,然后找到要删除的节点.这需要时间O(n),因此,在最坏的情况下,删除步骤的运行时间为O(n),而不是O(1).(那就是说,如果你知道的话两个指针 - 要删除的单元格和它之前的单元格,然后您可以在O(1)时间内删除单元格,因为您不必扫描列表来查找前一个单元格.)
简而言之:如果你知道要提前删除的单元格,那么双向链表可以让你在时间O(1)中删除它,而单链表需要时间O(n).如果您事先不知道该单元格,那么在两种情况下都是O(n).
希望这可以帮助!