Why List (T). Clear O (N)?

Question

According to the MSDN documentation on the List<T>.Clear :

This method is an O (n) operation where n is a graph.

Why is O (n)? I ask because I suppose that cleaning List<T> can be done simply by allocating a new array T[] inside. No other class can reference this array, so I see no harm in this approach.

Now, maybe this is a stupid question ... does the array T[] O (n) allocate? For some reason, I would not have thought so; but maybe it is (do I have a lack of CS degree showing right now?). If this is the case, I suppose that would explain it, because, according to the same documentation above, the capacity of the list remains unchanged, which means that you need to build an array of equal size.

(Again, this does not look like it could be the correct explanation, since then the documentation should have indicated "where n is Capacity" - not Count *).

I just suspect that this method, instead of allocating a new array, resets all elements of the current; and I'm curious to know why this would be.

_{* Hans Passant indicated in the commentary on the LukeH answer that the documents are correct. Clear only resets the elements that were set to List<T> ; he does not need to "re-zero" all the elements behind them.}

Answer 1

As far as I know, the current implementation simply calls Array.Clear in its internal array T[] , and Array.Clear the O (n) process. (As Hans notes in the comments, MSDN docs are correct that n in this case is a Count list, not its Capacity .)

But even if he just allocated a new array T[] inside, it would still be an O (n) process, since allocating an array of size n implies initializing all elements n their zero / zero / default.

Of course, there is nothing that could stop some kind of internal trick, where the array could be initialized with a length of 0 or 42, or something else, and then automatically updated on the fly, as required, amortizing the total cost of O (n).

Answer 2

Since the implementation of List<T>.Clear() calls Array.Clear() in the array of the list array and in the documentation , this method sets all elements of this array to null .

I would suggest that the reason the existing array is cleared rather than the new one created is because the .NET team determined that it would be more efficient to clean up the existing array instead of allocating a new one. Allocating a new array also takes time / memory, so this is a trade-off that attempts to optimize common usage scenarios.

Answer 3

List<T>.Clear() calls Array.Clear() , as shown here:

 public virtual void Clear() { if (this._size > 0) { Array.Clear(this._items, 0, this._size); this._size = 0; } this._version++; } 

In turn, Array.Clear() refers to an external function that will nullify the elements of an array, which is O (n):

 [MethodImpl(MethodImplOptions.InternalCall), SecuritySafeCritical, ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)] public static extern void Clear(Array array, int index, int length); 

Answer 4

List<T> lists contain some objects. Selecting a new List<T> does not eliminate the objects in the old list, therefore, this is not a clear operation.

The clear operation performs a linear one-time pass through the list, clearing all elements one by one. Since there are n elements, this takes O(n) .

The allocation of a T[] depends on whether the size is specified. If size is specified, then memory must be allocated for each element, or at least for each pointer for that element. So it takes O(n) . However, if we simply initialize the pointer to T[] , it will take O(1) .

PS CS-degree does not automatically mean that you know (or remember) this material ... sad, but true. Lack of a degree of CS is not detrimental at all.