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

Question

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

I have a question about why is it so.

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;
}

Given this implementation(think this is how most people would write this), this would be one operation that is independent of the size of the list (just setting front to null). Also by setting the front pointer as null, wouldn't you essentially be asking the garbage collector to "reclaim the underlying memory and reuses it for future object allocation." In this case , the underlying memory would be the front node and all the nodes that are consecutively attached to it.(http://javabook.compuware.com/content/memory/how-garbage-collection-works.aspx)

After stating all of that, how is clear an O(n) operation for linked list?

---

Attachment 1:

This is from a data structures class I am in

Answer 1

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

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

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)

Answer 2

I expect that your data structure class is not assuming that JAVA is the only system in the world.

In C, C++, Pascal, Assembly, Machine Code, Objective C, VB 6, etc, it takes a fixed time to free each block of memory, as they do not have a garbage collector. Until very recently most programs where wrote without the benefits of a garbage collector.

So in any of the above, all the node will need to be pass to free(), and the call to free() takes about a fixed time.

---

In Java, the link listed would take O(1) time to clear for a simple implantation of a linked list.

However as it may be possible that nodes would be pointed to from outside of the list, or that a garbage collector will consider different part of the memory at different time, there can be real life benefits from setting all the “next” and “prev” pointers to null. But in 99% of cases, it is best just to set the “front” pointer in the header to null as your code shows.

---

I think you should ask your lecture about this, as I expect lots of the students in the class will have the same issue. You need to learn C well before you can understand most generally data structure books or classes.