But the entire point of linked lists is to insert in the middle in constant time.
1 -> 2 -> 3 -> 4
Can become...
1 -> 2 -> 2.5 -> 3 -> 4
If you do that with arrays, you need a O(n) memcpy and maybe even a realloc.
-----------
Furthermore, linked lists don't even need a malloc routine !!!!!! See Knuth's dancing links (DXL) algorithm.
The ability to efficiently add and remove nodes from a linked list (even if that list was statically allocated) can sometimes beat the performance of arrays, because memcpy is just asymptotically slower than insert / remove.
1 -> 2 -> 3 -> 4
Can become...
1 -> 2 -> 2.5 -> 3 -> 4
If you do that with arrays, you need a O(n) memcpy and maybe even a realloc.
-----------
Furthermore, linked lists don't even need a malloc routine !!!!!! See Knuth's dancing links (DXL) algorithm.
The ability to efficiently add and remove nodes from a linked list (even if that list was statically allocated) can sometimes beat the performance of arrays, because memcpy is just asymptotically slower than insert / remove.