I Drained a List From the Front. It Shifted Five Billion Elements.

I had a List<int> standing in for a work queue. Jobs went on the back, and a loop pulled them off the front one at a time: read list[0], list.RemoveAt(0), do the work, repeat until the list was empty. It worked. It also crawled once the backlog got into the tens of thousands, and I couldn't see why a loop that just sums numbers would care how many numbers there were in a way that wasn't linear.

So I did the thing I always end up doing. I counted.

RemoveAt(0) moves everything else down

A List<T> is an array with a count on top. When you remove the item at index 0, every element after it has to slide down one slot to close the gap. Remove the front of a 100,000-item list and that's 99,999 elements copied. Do it again and it's 99,998. Keep going until the list is empty and you've shifted the sum of every number from 99,999 down to zero.

That sum is n * (n - 1) / 2, which is the quadratic you were trying not to write.

foreach (int n in new[] { 25_000, 50_000, 100_000 }) { long shifts = (long)n * (n - 1) / 2; Console.WriteLine($"n = {n,7:N0} -> {shifts,18:N0} element shifts"); }

n = 25,000 -> 312,487,500 element shifts n = 50,000 -> 1,249,975,000 element shifts n = 100,000 -> 4,999,950,000 element shifts

Five billion element moves to empty a list of a hundred thousand ints. The work I actually cared about was adding up a hundred thousand numbers. Everything else was the list closing gaps I'd just opened.

Putting a clock on it

I measured it the way I measure everything: fill a fresh collection, drain it, sum what comes out so nothing gets optimized away, best of five runs. This isn't a lab, it's a container, so I'm not going to pretend the millisecond counts are anything but rough. The shape is the point.

static long DrainWithListRemoveAt(int[] source) { var list = new List<int>(source); long sum = 0; while (list.Count > 0) { int job = list[0]; list.RemoveAt(0); // shifts every remaining element down one sum += job; } return sum; } static long DrainWithQueue(int[] source) { var queue = new Queue<int>(source); long sum = 0; while (queue.Count > 0) sum += queue.Dequeue(); // no shifting return sum; }

n = 25,000 List.RemoveAt(0) 315.04 ms Queue<int>.Dequeue() 0.07 ms n = 50,000 List.RemoveAt(0) 1284.42 ms Queue<int>.Dequeue() 0.13 ms n = 100,000 List.RemoveAt(0) 5193.70 ms Queue<int>.Dequeue() 0.14 ms

Double the size and the list takes roughly four times as long. That four-times-for-double is the signature of an O(n²) loop, and it's exactly what the shift count predicted. The Queue barely moves off zero because dequeuing is just bumping a head index.

I left the "list is 30,000x faster" line out on purpose. That ratio is meaningless. You're comparing something quadratic to something linear, so the gap keeps widening with no natural number at the end of it. The honest read is simpler: one of these grows with the square of your backlog and the other doesn't.

It isn't really a List problem

Here's the part that made me put the article together instead of just swapping in a Queue and moving on. I ran the same List<int>, with the same number of items, but pulled from the back instead of the front.

static long DrainFromEnd(int[] source) { var list = new List<int>(source); long sum = 0; while (list.Count > 0) { int job = list[^1]; list.RemoveAt(list.Count - 1); // last slot, nothing after it to shift sum += job; } return sum; }

n = 100,000 List.RemoveAt(0) 5193.70 ms List.RemoveAt(Count-1) 0.11 ms Queue<int>.Dequeue() 0.14 ms

Same list, same count, and it's right there with the Queue. RemoveAt(Count - 1) drops the last slot, and there's nothing behind it to move, so each removal is O(1). The five seconds was never about List<T> being slow. It was about repeatedly removing from the one position that forces a full shift.

That distinction matters because the fix depends on what you actually need. If order is up to you, draining from the end costs nothing and you keep your list. If you genuinely need first-in-first-out, Queue<T> is the type that was built for it, and it reads better than a list pretending to be one. Reaching for LinkedList<T> here is usually the wrong instinct, by the way; it gives you cheap removal but spends an allocation per node and wrecks cache locality, and for a plain FIFO it loses to Queue<T> on nearly everything.

And to be fair to RemoveAt(0): if your list is small, or you're pulling off the front once in a blue moon, none of this registers. A ten-item list doesn't care. The trap is specifically the loop that drains a big collection from the front, because that's where the per-call shift turns into a per-run square. I only noticed because the backlog grew past the size where I'd ever tested it.

The rule I walked away with: if a loop removes from the front of a list every iteration, that loop is quadratic, and the front is the problem, not the list.

Here's the whole thing if you want to run it yourself. The harness is nothing clever: warm up once so the JIT has done its work, take the best of five, and BuildJobs just fills an array so each int stands in for a small unit of work.

int[] sizes = [25_000, 50_000, 100_000]; foreach (int n in sizes) { int[] source = BuildJobs(n); (double listMs, _) = BestOf(5, () => DrainWithListRemoveAt(source)); (double endMs, _) = BestOf(5, () => DrainFromEnd(source)); (double queueMs, _) = BestOf(5, () => DrainWithQueue(source)); Console.WriteLine($"n={n,7:N0} front {listMs,8:F2}ms end {endMs,6:F2}ms queue {queueMs,6:F2}ms"); } static int[] BuildJobs(int n) { var jobs = new int[n]; for (int i = 0; i < n; i++) jobs[i] = i & 1023; return jobs; } static (double ms, long result) BestOf(int runs, Func<long> body) { body(); // warm up / JIT double best = double.MaxValue; long result = 0; var sw = new System.Diagnostics.Stopwatch(); for (int i = 0; i < runs; i++) { sw.Restart(); result = body(); sw.Stop(); best = Math.Min(best, sw.Elapsed.TotalMilliseconds); } return (best, result); }