为什么是明确的链表为O（n）操作？(Why is clear an O(n) operation f

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

我有一个关于为什么会这样的问题。

下面是我们如何在类中实现链表（JAVA）

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

如果我写这个链表类一个明确的方法，这是我会怎么写呢

public void clear() { 
        front = null;
}

鉴于此实现（认为这是大多数人会怎么写），这将是一个运作独立于列表的大小（只是将前为null）。 此外，通过设置在前指针为空，难道你基本上可以要求垃圾收集器“回收站底层的内存，并再次用于将来的对象分配。” 在这种情况下，底层的存储器将是前节点和被连续连接到它的所有节点。（ http://javabook.compuware.com/content/memory/how-garbage-collection-works.aspx ）

说明了这一切之后， 如何明确为链表为O（n）操作？

---

附件1：

这是从数据结构类我在

Answer 1:

请记住，一个链表具有n已分配它，并清除它，你实际上需要释放他们的条目。

由于Java有一个内置的垃圾收集器（GC） -你不需要明确地释放这些-但是，当定时时刻到来GC会在每个与他们每个人，并让他们自由

因此，即使您的明确方法是O(1)调用它需要O(n)从GC，这将使你的程序的时间O(n)

Answer 2:

我期待你的数据结构类并不假设JAVA是全球唯一的系统。

在C，C ++，Pascal中，大会，机器码，目标C，VB 6等，它需要一个固定的时间，以释放存储器的每个块，因为它们不具有垃圾收集器。 直到这里没有垃圾收集器的好处写得非常最近的方案。

因此，在上述任何一项，所有的节点将需要传递给free（），并且调用free（）大约需要一个固定的时间。

---

在Java中，列出的链接将采取O（1）时间以清除链表的简单移植。

但是，因为它可能是可能的节点会指出，从名单之外，或者是一个垃圾收集器将考虑在不同的时间对内存的不同部分，也可以是将所有的“下一步”和“上一个现实生活中的好处”指针为null。 但在案件99％，最好是刚刚设置的“前”指针在标题中NULL作为你的代码所示。

---

我想你应该问你的演讲了解，因为我希望很多学生在班级都会有相同的问题。 你需要学习C好，然后才能了解最普遍的数据结构的书或班。

文章来源: Why is clear an O(n) operation for linked list?