Lists

The favorite from the days of yore: you can insert and remove elements without any copying, and traversing it requires only one pointer dereference. What sounded like a good idea back then is rather unappealing today—inserting new elements requires dynamic memory allocations each time and traversing the list amounts to a classic pointer chase. That's why lists have fallen quite out of favor with the performance folks of today.

We can search for an item in a list in O(n) time, so there's no improvement over arrays. However, inserting elements in the middle doesn't have to pay the price of moving the elements as the array does.