How does the RemoveRange () method work in List <>?

Question

As in the title. I know that this probably combines 2 sublists before and after deleted items, but how does this method behave when deleting LAST items? In other words: does it somehow make a copy of all the elements located before deleting the index? I'm just wondering how to use RemoveRange in a gigantic list (say 5000 items) to remove fe only the last 2 of them.

If this makes a copy, is there a way to change some internal variable that sets the size of the list (and treat the rest of the selected items as garbage)?

I managed to find information that this is an O (n) complexity algorithm, but I'm not sure if “n” in this case is the size of the list or the number of items to delete.

We will be glad to any hint.

Answer 1

What he will do is take each item after the end of the range of items to remove and move it in the list by the number of items deleted. As for performance indicators, after the end of the range of moved items, one copy will be displayed for each item. This means that it will work best when removed from the end (this will be O (1)) and worst when deleted from the beginning (O (n)).

As an example, consider the following list:

  index - value

 0 - A
 1 - B
 2 - C
 3 - D
 4 - E
 5 - F
 6 - G 

If we call RemoveRange(2, 2) then we remove the two elements starting at index 2, so we remove C and D.

This means that E needs to be copied to index 2, then F needs to be copied to index 3, and G needs to be copied to index 4. For each element after one last element there is one copy operation.

Please note that due to the fact that you can move the entire memory block “up” by two, it becomes more efficient in practice when copying each element individually. It is much easier for computer memory to move the entire memory block by a fixed number of bytes than to move many small sections of memory to different arbitrary locations. However, it will have the same asymptotic complexity.

Answer 2

List<T> is just a wrapper around the array called _items in the code below. The array may have more slots than the list item, so _size used to track the number of valid values. When you do RemoveRange(index, count) ...

 _size -= count; if (index < _size) Array.Copy(_items, index + count, _items, index, _size - index); Array.Clear(_items, _size, count); 

... copies elements from a range to white space and clears old elements.

If you delete a range close to the beginning of a large list, then the cost is proportional to the size of the list, because so many things need to be moved down.

If you delete a large range near the end of a large list, copying is cheap, but cleaning is expensive, so the cost will be proportional to the size of the range being deleted.