CODEWITHSUNDEEP
c#listfor-loopforeachwhile-loop
Dragomok
Dragomok

Reputation: 622

Performance of for/while loop vs foreach loop on List<T>

There are plenty of posts about performance of for and foreach loops on arrays and IEnumerables in general. Unfortunately, they deal mostly with overheads related to foreach loop, and I can't find anything clear about their performance on linked lists - or rather List<T>.

To keep things simple, I'm going to present my question as two assumptions, and ask if they are correct.

Assumption 1

When I run the following code:

List<Foo> list = new List<Foo>();

//(list is filled here)

foreach (Foo f in list)
{
    f.baz();
}

loop iterations are going to execute like this:

0: You have a pointer to node 0. Call baz() on node 0's item. Move pointer to the node after node 0.

1: You have a pointer to node 1. Call baz() on node 1's item. Move pointer to the node after node 1.

2: You have a pointer to node 2. Call baz() on node 2's item. Move pointer to the node after node 2.

...

n: You have a pointer to node n. Call baz() on node n's item. Move pointer to the node after node n.

In other words, the code above has O(n) complexity.

Assumption 2

When I run the following code:

List<Foo> list = new List<Foo>();

//(list is filled here)

for (int i = 0; i < list.Count; i++)
{
    list[i].baz();
}

or the following code:

List<Foo> list = new List<Foo>();

//(list is filled here)

int i = 0;
while (i < list.Count)
{
    list[i].baz();
    i++;
}

loop iterations are going to execute like this:

0: You have a pointer to list. Get pointer to node 0 from list. Call baz() on node 0's item.

1: You have a pointer to list. Get pointer to node 0 from list. Move pointer to the node after node 0. Call baz() on node 1's item.

2: You have a pointer to list. Get pointer to node 0 from list. Move pointer to the node after node 0. Move pointer to the node after node 1. Call baz() on node 2's item.

...

n: You have a pointer to list. Get pointer to node 0 from list. Move pointer to the node after node 0. Move pointer to the node after node 1. Move pointer to the node after node 2. [...] Move pointer to the node after node (n-2). Move pointer to the node after node (n-1). Call baz() on node n's item.

In other words, the code above has O(n2) complexity.

Are my assumptions correct?

Upvotes: 0

Views: 1241

Answers (1)

Scott Chamberlain
Scott Chamberlain

Reputation: 127543

No, your assumptions are incorrect. The List<T> data type is backed by an array not a Linked List. The logic would be

0: You have a refrence to list. Get the internal array and directly jump to the 0th index. Call baz() on node 0's item.

1: You have a refrence to list. Get the internal array and directly jump to the 1st index's offset. Call baz() on node 1's item.

2: You have a refrence to list. Get the internal array and directly jump to the 2nd index's offset. Call baz() on node 2's item.

...

n: You have a refrence to list. Get the internal array and directly jump to the nth index's offset. Call baz() on node n's item.

If you where working with a LinkedList<T> your description would be correct however LinkedList<T> does not have a indexer property [i] so you would not be able to pass in a index to retrieve like your code example does.

Upvotes: 1

Related Questions