Why is LinkedList useful?

If you implement a stack with a dynamic array-based with LinkedList you need more memory than with a dynamic array, and with dynamic array for insert in amortized cost is O(1), so the advantage of the LinkedList now is not and advantage, so why you should use a LinkedList, and why is this a useful data structure?

For a normal stack, the implementation on top of a linked list is indeed questionable. Many other uses of linked lists are disappointing in practice as well.

But consider a lock-free stack where push and pop are atomic. A singly-linked list can offer atomic prepend and atomic "remove head" using atomic Compare-and-Swap (some caveats apply). Implementing an atomic stack on top of an array is a bigger problem, one that to my knowledge has not been satisfactorally solved.

The downside that linked lists tend to weave their way somewhat randomly through memory can occasionally be turned into an advantage: elements that are in some other data structure can have a linked list weaved through them without imposing requirements on the addresses of the elements. For example, elements in a hash map can also have a linked list running through them that records their insertion order, while maintaining fast removal (a dynamic array that records the indexes of the elements in insertion order would still allow fast insertion but not fast removal since it could happen in the middle). Elements can even be in several different linked lists at the same time, an example of that is dancing links algorithm which uses linked lists for columns and rows and elements are in both a column and a row at the same time.

StackExchange Computer Science Q#113598, answer score: 2