Hello. I am learning about some basic data structures. I have also learned about time and memory complexity. I have used from
List
many times in my codes but now when I was looking at its source codes, I did not get what is happening and how does it work behind.
I wrote a simple code to check how much empty space it allocates when it is initializing for the first time, and I noticed that it is actually equal to 0.
var first = new List<int>();
for(int i = 0; i < 23; i++)
{
first.Add(i);
}
for(int i = 0; i < 23; i++)
{
first.Remove(i);
}
Then after adding the first element its
Counts
becomes 1 and its
Capacity
becomes 4. And actually the
Capacity
does not change untill the
Count
becomes equal to it. And it also changes in a sequence like this:
4, 8, 16, 32, 64, etc.
I have read this
link about
List
implementation. But I have some questions. The first one is that,
How do its counstructors work? .
My second question is about the
Contract
class and
Ensures
method. For example in below code, I did not get what is happening and what is their use:
public int Count {
get {
Contract.Ensures(Contract.Result<int>() >= 0);
return _size;
}
}
I also see 2 methods for
Add
, but I did not get what is the use of
EnsureCapacity(_size + 1)
in the first method:
public void Add(T item) {
if (_size == _items.Length) EnsureCapacity(_size + 1);
_items[_size++] = item;
_version++;
}
int System.Collections.IList.Add(Object item)
{
ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(item, ExceptionArgument.item);
try {
Add((T) item);
}
catch (InvalidCastException) {
ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T));
}
return Count - 1;
}
I think the below function changes the
Capacity
when it is needed and actually it sets a
policy when we want to
add elements to our
List
:
private void EnsureCapacity(int min) {
if (_items.Length < min) {
int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
if ((uint)newCapacity > Array.MaxArrayLength)
newCapacity = Array.MaxArrayLength;
if (newCapacity < min) newCapacity = min;
Capacity = newCapacity;
}
}
My last question is that how much space is wasted during
adding or
removing elements from the
List
? Because I noticed that when I was
removing elements from my
List
its
Capacity
does not change and it does not decrease.
What I have tried:
I have read some related questions on the internet and StackOverflow, but it was a bit hard for me to comprehend them, suffice to say I am just a beginner. Sorry because of my bad English. I will be really grateful for any help or advice about my questions.
Thanks.