Array versus linked-list

Question

Why would someone want to use a linked-list over an array?

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.

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.

Answer 1

Linked List

Its more preferable when it comes about insertion! Basically what is does is that it deals with the pointer

1 -> 3 -> 4

Insert (2)

1........3......4
.....2

Finally

1 -> 2 -> 3 -> 4

One arrow from the 2 points at 3 and the arrow of 1 points at 2

Simple!

But from Array

| 1 | 3 | 4 |

Insert (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

Well anyone can visualize the difference! Just for 4 index we are performing 3 steps

What if the array length is one million then? Is array efficient? The answer is NO! :)

The same thing goes for deletion! In Linked List we can simply use the pointer and nullify the element and next in the object class! But for array, we need to perform shiftLeft()

Hope that helps! :)

Answer 2

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.

Answer 3

It's really a matter of efficiency, the overhead to insert, remove or move (where you are not simply swapping) elements inside a linked list is minimal, i.e. the operation itself is O(1), verses O(n) for an array. This can make a significant difference if you are operating heavily on a list of data. You chose your data-types based on how you will be operating on them and choose the most efficient for the algorithm you are using.

Answer 4

In an array you have the privilege of accessing any element in O(1) time. So its suitable for operations like Binary search Quick sort, etc. Linked list on the other hand is suitable for insertion deletion as its in O(1) time. Both has advantages as well as disadvantages and to prefer one over the other boils down to what you want to implement.

-- Bigger question is can we have a hybrid of both. Something like what python and perl implement as lists.

Answer 5

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

Answer 6

Only reason to use linked list is that insert the element is easy (removing also).

Disadvatige could be that pointers take a lot of space.

And about that coding is harder: Usually you don't need code linked list (or only once) they are included in STL and it is not so complicated if you still have to do it.