[Solved] If linked lists have many functional advantages over arrays, what advantages do arrays have over linked lists? [closed]

Question

Because there is no free lunch.

In general, if a data structure is more powerful than another, you will have to pay for that additional power somehow. Sometimes you will not be willing to pay that price.

As for lists, you are correct, in terms of functionality, they are way better than arrays:

You can efficiently insert and delete elements anywhere in the list without having to copy existing elements around
Lists can grow indefinitely. If you want a growing array, you basically have to copy all existing elements to the bigger array and then throw away the old one.
You can efficiently move elements from one list to another without copying.

Arrays can do none of that!

But because arrays don’t have to support these features, they also don’t have to pay for the additional complexities that list implementations introduce:

A list has to allocate each of its elements separately. This means more complex lifetime management for the implementation and a lot of calls to new and delete. You will not notice this in small programs, but those calls are very slow, and what is worse, they get slower the more you use them.
Because the elements are allocated independently, they might end up scattered all over memory. This is bad for caching, because caches work best if all the data is close together in memory. On modern desktop machines this can have a huge impact on performance, as accessing memory is significantly slower than accessing the cache. It is in fact so big, that more often than not, the additional work that you have to do with arrays in terms of copying elements around is still cheaper than having to deal with the bad caching behavior of lists.
Arrays allow for random access. That means I can always directly locate any element of the array from its index. With lists, I need to traverse the list, so if my element is further back in the list, it will take me longer to reach it. Also, bigger lists take longer to traverse than smaller ones. If I frequently use algorithms that need to perform a series of random accesses quickly, using arrays can be a big performance win. Binary search is an obvious example.

So, as you can see, there is a trade-off. The added flexibility is great, but it comes at a cost that might bite you depending on what you want to do with the data structure. The same is true for all data structures by the way. Trees for example solve the slow lookup problem of lists to some extent, but they have other drawbacks compared to lists and arrays. It is important that you as a programmer familiarize yourself with the different strengths and weaknesses of the different data structures, so that you can chose the right one for each problem.

Accepted Answer

Because there is no free lunch.

In general, if a data structure is more powerful than another, you will have to pay for that additional power somehow. Sometimes you will not be willing to pay that price.

As for lists, you are correct, in terms of functionality, they are way better than arrays:

You can efficiently insert and delete elements anywhere in the list without having to copy existing elements around
Lists can grow indefinitely. If you want a growing array, you basically have to copy all existing elements to the bigger array and then throw away the old one.
You can efficiently move elements from one list to another without copying.

Arrays can do none of that!

But because arrays don’t have to support these features, they also don’t have to pay for the additional complexities that list implementations introduce:

A list has to allocate each of its elements separately. This means more complex lifetime management for the implementation and a lot of calls to new and delete. You will not notice this in small programs, but those calls are very slow, and what is worse, they get slower the more you use them.
Because the elements are allocated independently, they might end up scattered all over memory. This is bad for caching, because caches work best if all the data is close together in memory. On modern desktop machines this can have a huge impact on performance, as accessing memory is significantly slower than accessing the cache. It is in fact so big, that more often than not, the additional work that you have to do with arrays in terms of copying elements around is still cheaper than having to deal with the bad caching behavior of lists.
Arrays allow for random access. That means I can always directly locate any element of the array from its index. With lists, I need to traverse the list, so if my element is further back in the list, it will take me longer to reach it. Also, bigger lists take longer to traverse than smaller ones. If I frequently use algorithms that need to perform a series of random accesses quickly, using arrays can be a big performance win. Binary search is an obvious example.

So, as you can see, there is a trade-off. The added flexibility is great, but it comes at a cost that might bite you depending on what you want to do with the data structure. The same is true for all data structures by the way. Trees for example solve the slow lookup problem of lists to some extent, but they have other drawbacks compared to lists and arrays. It is important that you as a programmer familiarize yourself with the different strengths and weaknesses of the different data structures, so that you can chose the right one for each problem.