为什么是明确的一个O（n）的操作链表？ [英] Why is clear an O(n) operation for linked list?

问题描述

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

According to attachment 1, linked list's clear operation is O(n).

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

I have a question about why is it so.

下面是我们如何实现在课堂上链表（JAVA）

Here is how we implemented the linked list in class(java)

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

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

And if I were to write a clear method for this linked list class, this is how I would write it

public void clear() { 
        front = null;
}

鉴于这种实现（想这是大多数人会写这篇文章），这将是一个操作独立于列表的大小（只设置前为null）。另外通过设置前指针为空，你会不会实质上会问垃圾回收回收底层的内存，并再次用于将来的对象分配。在这种情况下，底层的存储器将是前节点和所有被连续连接到它的节点。（http://javabook.compuware.com/content/memory/how-garbage-collection-works.aspx)

在说明了这一切，如何清楚一个O（n）的操作链表？

附件1：

这是从数据结构类我在

This is from a data structures class I am in

推荐答案

记住，一个链表有被分配给它的 N 项，并清除它，你确实需要释放他们。

Remember that a Linked List has n entries that were allocated for it, and for clearing it, you actually need to free them.

由于Java有一个内置的垃圾收集器（GC） - 你不'T需要明确地释放这些 - 但GC将超过每其中之一，并释放他们时，时机成熟

Since java has a built in garbage collector (GC) - you don't need to explicitly free those - but the GC will go over each and every one of them and free them when time comes

所以，即使您的明确方法是 O（1），调用它需要 O（N）从时间在GC，这将使你的程序 O（N）

So even though your explicit method is O(1), invoking it requires O(n) time from the GC, which will make your program O(n)

这篇关于为什么是明确的一个O（n）的操作链表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！