What are real world examples of when Linked Lists should be used?
A real-world example would be a FIFO queue. An simple array-based list is pretty bad for that because you need to add at one end and remove at the other end, and one of those operations will be O(n) with an array-based list (unless you add extra logic to work with a start AND end index), while both are O(1) with a linked list without extra effort.
Intrusive linked lists are interesting beasts for game development. For example, it's somewhat common practice to have an intrusive singly- or doubly-linked "render" list:
class Renderable /* or class Object, whatever */ { // ... Renderable * m_pNext; Renderable * m_pPrev; // or not, if singly-linked // ... }
As Renderables come into and out of existence they can register themselves with this list -- without causing any memory allocation. If their render depth or priority is changed they can remove and reinsert themselves, etc.
When it comes time to render, all you need to do is find the head of the list and zip through, calling the appropriate method!
(There are, of course, many variations on this theme, with multiple separate lists, etc. And you don't need to have an intrusive list to make this work, I just find the intrusive ones interesting.)
Linked Lists offer several advantages over comparable data structures such as static or dynamically expanding arrays.
- LinkedLists does not require contiguous blocks of memory and therefore can help reduce memory fragmentation
- LinkedLists support efficient removal of elements (dynamic arrays usually force a shift in all of the elements).
- LinkedLists support efficient addition of elements (dynamic arrays can cause a re-allocation + copy, if a particular add exceeds the current capacity)
Any place where these advantages would be significantly valuable to a program (and the disadvantages of a LinkedList were negligible) would be a place to use a LinkedList.