为什么 clear 是链表的 O(n) 操作？

Question

根据附件1，链表的清除操作是O(n)。

我有一个问题，为什么会这样。

下面是我们如何在 class(java)

中实现链表

public class LinkedIntList {
           private ListNode front;
            ......
}

如果我要为这个链表写一个清晰的方法class，我会这样写

public void clear() { 
        front = null;
}

鉴于此实现（认为这是大多数人的写法），这将是一个独立于列表大小的操作（只需将 front 设置为 null）。此外，通过将前端指针设置为 null，您实际上是否会要求垃圾收集器 "reclaim the underlying memory and reuses it for future object allocation." 在这种情况下，底层内存将是前端节点和所有连续附加到它的节点。（http://javabook.compuware.com/content/memory/how-garbage-collection-works.aspx)

说完所有这些，链表的 O(n) 操作如何清楚？

附件 1：

这是来自数据结构class我在

Answer 1

请记住，链表有 n 个分配给它的条目，要清除它，您实际上需要释放它们。

因为 java 有一个内置的 garbage collector (GC) - 你不需要显式释放它们 - 但 GC 会遍历它们中的每一个并在时间到来时释放它们

所以即使你的显式方法是 O(1)，调用它需要 GC 的 O(n) 时间，这将使你的程序 O(n)

Answer 2

我希望你的数据结构class不假设JAVA是世界上唯一的系统。

在 C、C++、Pascal、汇编、机器代码、Objective C、VB6 等中，释放每个内存块需要固定的时间，因为它们没有垃圾收集器。直到最近，大多数程序的编写都没有垃圾收集器的好处。

所以在上面的任何一个中，所有的节点都需要传递给free()，而对free()的调用大约需要一个固定的时间。

在 Java 中，列出的 link 需要 O(1) 时间来清除 linked 列表的简单植入。

然而，由于可能会从列表外部指向节点，或者垃圾收集器会在不同时间考虑内存的不同部分，因此设置所有“ next”和“prev”指针指向空。但是 在 99% 的情况下，最好只是将 header 中的“前”指针设置为 null，如您的代码所示。

我想你应该问一下你的讲座，因为我预计 class 中的很多学生都会有同样的问题。 你需要学习 C在您可以理解最普遍的数据结构书籍或 classes.

之前

为什么 clear 是链表的 O(n) 操作？

Why is clear an O(n) operation for linked list?

java

algorithm

garbage-collection

linked-list

time-complexity