Are there other advantages to linked lists over arrays other than constant time removals of the first element?
Linked lists can work well even if memory is fragmented. Arrays usually require a continuous piece of memory. For large piece of data finding this large continuous piece of memory might be hard.
Most of benefits of linked lists requires to remember more links than just the head. For example. If you are doing some sequential checks and deletions or insertions, you can keep this link of the last checked element. Then all of this insertions or deletions are O(1), you have all the data needed, and memory required for insert is small. In other words linked lists are good for local operations. Like text. If you would try to implement a text editor and rewrite the whole array when user adds another letter in the middle, it will be slower than with a linked list, if linked list remembers last edit points and most edits are a bit further than it. Upgrade to this idea are skip list and rope.
Another useful feature of links is atomicity of small edits. With an array you could achieve atomicity by replacing the link to the array itself, but only after making a whole new copy. But with linked list you can build another subchain, and then replace the link to it, changing the small portion of the linked list this way, keeping all the data consistent and not spending lots of memory on another copy.
This isn't really about "advantages", but appropriateness. Sometimes it's more appropriate to use an array, and sometimes to use a linked list.
If it helps, take a look at this large table of the complexity of various operations of a bunch of data structures from the C++ standard library so you can compare them. If you're not familiar with C++,
vector is a growable array,
deque is a double-ended queue (essentially a chunked array), and
list is a linked list. What you can see is that the main tradeoff is:
- Dereferencing an element of an array, from a position index, is $O(1)$ operation, and linked lists don't really support that.
- Insertion and deletion of an arbitrary element of a linked list is $O(1)$, and $O(n)$ for an array.
An important consideration missing from the other answers: It's easier and more performant to use immutable linked lists than immutable arrays, which is especially important in functional programming languages.
For example, to add an element to an array in an immutable language, you actually create a new array with the extra element added to it, which entails copying the entire array. The compiler might be able to optimize this out (it might detect that the original array is never read again, and just append in-place), but not in general.
Adding an element to an immutable linked list is easy, as long as you're willing to add to the front: Create the new head node, and link it to the old head. The old head still represents the old list, and the new head represents the new list!
This implies another benefit of linked lists: Two lists that differ only in the first few elements can share most of their memory.
If you make the elements stored in the list already contain the next/prev pointers (called an intrinsic or intrusive linked list) than the list doesn't need to do allocations and risk fragmenting memory further just to store 3-pointer sized structs or an array of pointer that needs reshuffling every time you pull out an element.
This is very handy if you expect the elements to move lists frequently and/or a possibly failing allocation means a panic. Like for example the thread descriptor object moving between various wait queues in the kernel depending on why the thread was interrupted.
With an intrinsic list which is doubly linked then if you can acquire a pointer to the object directly then you can pull the object out of the list without needing to find it in the list or array.
A linked list is appropriate for many use cases independent of performance considerations. In addition to examples given by other answers here, consider that a given object (an instance) can be in more than one linked list (internally linked as well as externally linked) but can only be in one array (it can be pointed to by multiple arrays, but that's not the same, for many use cases).
Consider these diagrams from the book The Design Of An Optimizing Compiler (Wulf, Johnsson, Weinstock, Hobbs) (1973) - first is the multiply-internally-linked symbol table, second is the multiply-internally-linked "graph table" used for recognizing common subexpressions - the "threads" are multiple semantically different, semantically important traversals of the same data structure implemented by separate linked lists into the same objects each representing a symbol or a syntax tree node.
BTW, IMO it is a design mistake to consider performance of a data structure before considering appropriateness. But I can see that it frequently happens, probably because of the way CS/programming is taught, in many cases by teachers and textbooks, in which performance characteristics are prioritized over appropriateness, and in fact, appropriateness is given short shrift. See for example many industry "interview questions" which are considered properly answered by discussions of O-bounded performance, where the data structure to use is just assumed to be "obvious". Or in many many examples in textbooks, websites, and language libraries that have good support for external data structures (linked lists, arrays, dictionaries, hash tables) and never mention at all much less support internally linked data structures as used above. (Note that as in the diagrams above hash tables and trees can be represented using internal links if that is appropriate - it's just never done anymore not because it is wrong by mainly because there's no language or library support.)
Donald Knuth’s “dancing links” algorithm is a well-known one that uses the constant-time insertion and deletion of items in a linked list for performance. You can hear him discuss it, twenty-four years later, here.
An important optimization for linked lists, in a lazy functional language with immutable linked lists, is to treat them just as a sequence and avoid ever actually creating the list itself, compiling to something much like
yield return in C#.
I don't have an exhaustive list (pun intended), but off the top of my head:
- You can also perform constant time operation at the tail (for a circular doubly linked list).
- You can implement the move-to-front heuristic (MTF) efficiently.
- No need to perform costly expansion/contraction (there is a way to prevent this in an array but requires extra memory)
If you mean fixed arrays (whose lengths are fixed in advance) versus linked lists, then linked lists have the advantage that they use up memory only on an as needed basis - a new cell is allocated each time a new insert operation is done. Whereas, arrays would require you to specify the maximum length of the list in advance, and any unused space is wasted, and you can’t insert more elements than this maximum length even if you encounter more data. So, if you don’t know in advance how many elements will be inserted into the list, a linked list would be a better data structure to use.