Array versus linked-list

First of all, in C++ linked-lists shouldn't be much more trouble to work with than an array. You can use the std::list or the boost pointer list for linked lists. The key issues with linked lists vs arrays are extra space required for pointers and terrible random access. You should use a linked list if you

• you don't need random access to the data
• you will be adding/deleting elements, especially in the middle of the list

Fast insertion and removal are indeed the best arguments for linked lists. If your structure grows dynamically and constant-time access to any element isn't required (such as dynamic stacks and queues), linked lists are a good choice.

Other than adding and remove from the middle of the list, I like linked lists more because they can grow and shrink dynamically.

Arrays make sense where the exact number of items will be known, and where searching by index makes sense. For example, if I wanted to store the exact state of my video output at a given moment without compression I would probably use an array of size [1024][768]. This will provide me with exactly what I need, and a list would be much, much slower to get the value of a given pixel. In places where an array does not make sense there are generally better data types than a list to deal with data effectively.