Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Array versus linked-list

People also ask

Is array better than linked list?

Better use of Memory: From a memory allocation point of view, linked lists are more efficient than arrays. Unlike arrays, the size for a linked list is not pre-defined, allowing the linked list to increase or decrease in size as the program runs.

Why is linked list preferred over array?

Linked lists are preferable over arrays when:you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big. you don't need random access to any elements. you want to be able to insert items in the middle of the list (such as a priority queue)


Another good reason is that linked lists lend themselves nicely to efficient multi-threaded implementations. The reason for this is that changes tend to be local - affecting only a pointer or two for insert and remove at a localized part of the data structure. So, you can have many threads working on the same linked list. Even more, it's possible to create lock-free versions using CAS-type operations and avoid heavy-weight locks altogether.

With a linked list, iterators can also traverse the list while modifications are occurring. In the optimistic case where modifications don't collide, iterators can continue without contention.

With an array, any change that modifies the size of the array is likely to require locking a large portion of the array and in fact, it's rare that this is done without a global lock across the whole array so modifications become stop the world affairs.


  • It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size.
  • As you mentioned, it's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow.
  • Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory.
  • As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.

Wikipedia has very good section about the differences.

Linked lists have several advantages over arrays. Elements can be inserted into linked lists indefinitely, while an array will eventually either fill up or need to be resized, an expensive operation that may not even be possible if memory is fragmented. Similarly, an array from which many elements are removed may become wastefully empty or need to be made smaller.

On the other hand, arrays allow random access, while linked lists allow only sequential access to elements. Singly-linked lists, in fact, can only be traversed in one direction. This makes linked lists unsuitable for applications where it's useful to look up an element by its index quickly, such as heapsort. Sequential access on arrays is also faster than on linked lists on many machines due to locality of reference and data caches. Linked lists receive almost no benefit from the cache.

Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or boolean values. It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element, a problem generally solved using memory pools.

http://en.wikipedia.org/wiki/Linked_list


I'll add another - lists can act as purely functional data structures.

For instance, you can have completely different lists sharing the same end section

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

i.e.:

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

without having to copy the data being pointed to by a into b and c.

This is why they are so popular in functional languages, which use immutable variables - prepend and tail operations can occur freely without having to copy the original data - very important features when you're treating data as immutable.