0
\$\begingroup\$

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

For array:

public T RemoveAt(int index)
{
    if (index >= this.count || index < 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 < 0 || index >= count)
    {
        throw new IndexOutOfRangeException("Invalid Index" + index);
    }
    else
    {
        int currentindex = 0;
        ListNode currentnode = this.head;
        ListNode prevnode = null;

        while (currentindex<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<int> listusingArray = new CustomArrayList<int>(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<int> listusingDynamic = new DynamicList<int>();

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?

\$\endgroup\$

closed as off-topic by svick, RubberDuck, BenVlodgi, syb0rg, Morwenn Aug 3 '14 at 17:36

If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ This question appears to be off-topic because it is not about reviewing and improving code, it's about analyzing a specific aspect of it. \$\endgroup\$ – svick Aug 3 '14 at 13:44
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

For your linked list, RemoveAt(0) fails. It will try to do null.nextnode = this.head.nextnode;. What should happen is this.head = this.head.nextnode;.

For your linked list, remove the else, and reduce the level of indentation by one for the bulk of the function's body — the way you did for the array's RemoveAt(). It's also curious that you wrote the parameter validation code differently for the two functions, both in the if expression being tested and in the type of exception you throw.

You could optionally eliminate the currentindex variable by decrementing index instead.

\$\endgroup\$
0
\$\begingroup\$

Runnig a test once is usually not sufficient for performance profiling. Additionally, the test may look dramatically different (probably in favour of the array based list) if you remove items from the end of the list. (More iterations, variable reads and assignments with the linked list, but exactly the same method call for the array.)

So why might the array based version faster? Well, for one, you actually have to access the linked list nodes until the correct element it located. The removal itself is probably probably the least performance hungry part of the code. As we can see, Array.Copy is not implemented in IL, but is forwarded to a native method, which is probably a bit faster than traversing the complete node list. Also note that you may want to resize the array at some point, if a substantial amount of list items have been removed. (Possibly as a separate method, as in List.TrimExcess.)

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.