Coding a linked-list is, no doubt, a bit more work than using an array and one may wonder what would justify the additional effort.
You are watching: Lists are dynamic data structures such that items may be added to them or removed from them.
I think insertion of new elements is trivial in a linked-list but it"s a major chore in an array. Are there other advantages to using a linked list to store a set of data versus storing it in an array?
This question is not a duplicate of this question because the other question is asking specifically about a particular Java class while this question is concerned with the general data structures.
arrays data-structures linked-list language-agnostic
Improve this question
edited Jan 11 "19 at 20:09
10 revs, 5 users 76%Onorio Catenacci
Add a comment |
34 Answers 34
Active Oldest Votes
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.
Improve this answer
edited Oct 3 "08 at 15:58
answered Oct 3 "08 at 13:59
Alex MillerAlex Miller
66.3k2525 gold badges116116 silver badges164164 bronze badges
Add a comment |
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.
Improve this answer
answered Oct 3 "08 at 13:40
9,74077 gold badges4141 silver badges5656 bronze badges
| Show 14 more comments
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.
See more: Pretty Middle Aged Woman - Middle Aged Attractive Woman Images
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.