Linked list vs array performance for RemoveAt() function I am trying to compare the RemoveAt() function performance in an array and linked list.

For array:

public T RemoveAt(int index)
{
    if (index &gt;= this.count || index &lt; 0)
    {
        throw new ArgumentOutOfRangeException(
            "Invalid index: " + index);
    }

    T item = this.arr[index];

    Array.Copy(this.arr, index + 1,

        this.arr, index, this.count - index - 1);

    this.arr[this.count - 1] = default(T);

    this.count--;



    return item;
}


For linked list:

public T RemoveAt(int index)
{
    if (index &lt; 0 || index &gt;= count)
    {
        throw new IndexOutOfRangeException("Invalid Index" + index);
    }
    else
    {
        int currentindex = 0;
        ListNode currentnode = this.head;
        ListNode prevnode = null;

        while (currentindex&lt;index)
        {
            prevnode = currentnode;
            currentnode = currentnode.nextnode;
            currentindex++;
        }
        // Remove the found element from the list of nodes

        RemoveListNode(currentnode, prevnode);



        // Return the removed element

        return currentnode.element;

    }
}

private void RemoveListNode(ListNode node, ListNode prevNode)
{

                 prevNode.nextnode = node.nextnode;
}


Main program:

I have inserted 10K elements in each and I am trying to remove the 500th element.

Stopwatch s=new Stopwatch();
CustomArrayList&lt;int&gt; listusingArray = new CustomArrayList&lt;int&gt;(10000);
Console.WriteLine("Deleting 500th elements from array........\n");

s.Start();
listusingArray.RemoveAt(500);
s.Stop();

Console.WriteLine("Time taken to delete from array: " + s.Elapsed);



DynamicList&lt;int&gt; listusingDynamic = new DynamicList&lt;int&gt;();

s.Reset();
Console.WriteLine("Removing 500th elements from Link List........\n");

s.Start();
listusingDynamic.RemoveAt(500);
s.Stop();

Console.WriteLine("Time taken to remove from list: " + s.Elapsed);


Output:




Time taken to delete from array :00:00:00.0003040

Time taken to delete from list  :00:00:00.0008685



Shouldn't the linked list Remove at() function  be faster as it avoids Array.Copy in array?
If you time just removing the item from the list, it probably will be faster.

What you're timing is traversing the list to the correct point, then removing the item. Apparently, traversing the list is slow enough to (more than) make up for the time you're saving on the removal itself.

Although it was written about C++, most of the points Bjarne raises in his video on the subject apply about as well to most other languages.