Click here to Skip to main content
15,890,438 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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.
C#
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:
C#
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
C#
EnsureCapacity(_size + 1)
in the first method:
C#
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:

C#
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.
Posted
Updated 16-Nov-21 4:52am
v2

1 solution

 
Share this answer
 
Comments
Aylin Naebzadeh 16-Nov-21 11:55am    
I have read your article and it helps me to get a better idea about what is happening when we use Add, Remove and Insert methods. Thanks.
OriginalGriff 16-Nov-21 12:25pm    
Good!
For the rest, start with the Reference Sources - they contain the full source code for the List class and make interesting reading.
Maciej Los 16-Nov-21 12:34pm    
5ed!

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900