Originally published on software-engineer-blog.com.
Every data-structures course teaches the same table. Array: insert O(n), because you have to shift everything. Linked list: insert O(1), because you just repoint two pointers. Conclusion: if you insert a lot, use a linked list.
Then you write both, measure them, and the array wins anyway.
Here is the measurement that starts the whole story. Ten million integers, held as one contiguous array and as ten million linked nodes. Walk each one, summing as you go — the same operation count, the same complexity class, O(n) both:
contiguous array: 0.53 seconds (52.6 ns per element)
