Array Vs. Linked List

Reposting my own answer here, maybe it will spark a discussion:

Suppose you have an ordered set, which you also want to modify by adding and removing elements. Further, you need ability to retain a reference to an element in such a way that later you can get a previous or next element. For example, a to-do list or set of paragraphs in a book.

First we should note that if you want to retain references to objects outside of the set itself, you will likely end up storing pointers in the array, rather than storing objects themselves. Otherwise you will not be able to insert into array - if objects are embedded into the array they will move during insertions and any pointers to them will become invalid. Same is true for array indexes.

Your first problem, as you have noted yourself, is insertion - linked list allows inserting in O(1), but an array would generally require O(n). This problem can be partially overcome - it is possible to create a data structure that gives array-like by-ordinal access interface where both reading and writing are, at worst, logarithmic.

Your second, and more severe problem is that given an element finding next element is O(n). If the set was not modified you could retain the index of the element as the reference instead of the pointer thus making find-next an O(1) operation, but as it is all you have is a pointer to the object itself and no way to determine its current index in the array other than by scanning the entire "array". This is an insurmountable problem for arrays - even if you can optimized insertions, there is nothing you can do to optimize find-next type operation.

A Very detailed pros and cons. Liked it.