Array Vs. Linked List

Question

I apologize--this question may be a bit open-ended but I think there are probably definite, quantifiable answers to it so I'll post it anyway.

A person I know is trying to learn C++ and software development (+1 to him) and he asked me why someone would want to use a linked list in preference to an array. Coding a linked list is, no doubt, a bit more work than using an array and he wondered what would justify the additional effort.

I gave him the answer I know: insertion of new elements is trivial in linked list but it's a major chore in an array. But then I got to thinking about it a bit more. Besides the ease of insertion of a new element into a linked list are there other advantages to using a linked list to store a set of data vs. storing it in an array?

As I said, I'm not meaning to start a long and drawn-out discussion. I'm just looking for other reasons that a developer might prefer a linked list to an array.

Answer 1

Besides inserting into the middle of the list being easier - it's also much easier to delete from the middle of a linked list than an array.

But frankly, I've never used a linked list. Whenever I needed fast insertion and deletion, I also needed fast lookup, so I went to a HashSet or a Dictionary.

Answer 2

Here's a quick one: Removal of items is quicker.

Answer 3

• 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.

Answer 4

Eric Lippert recently had a post on one of the reasons arrays should be used conservatively.

Answer 5

Other than adding and remove from the middle of the list, I like linked lists more because they can grow and shrink dynamically.

Answer 6

Fast insertion and removal are indeed the best arguments for linked lists. If your structure grows dynamically and constant-time access to any element isn't required (such as dynamic stacks and queues), linked lists are a good choice.

Answer 7

Merging two linked lists (especially two doubly linked lists) is much faster than merging two arrays (assuming the merge is destructive). The former takes O(1), the latter takes O(n).

EDIT: To clarify, I meant "merging" here in the unordered sense, not as in merge sort. Perhaps "concatenating" would have been a better word.

Answer 8

Linked-list are especially useful when the collection is constantly growing & shrinking. For example, it's hard to imagine trying to implement a Queue (add to the end, remove from the front) using an array -- you'd be spending all your time shifting things down. On the other hand, it's trivial with a linked-list.

Answer 9

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 10

Because no one ever codes their own linked list anymore. That'd be silly. These days it's just an exercise for students so they can understand the concept. Instead, use a pre-built list. In C++, that'd probably mean an stl vector ( #include <vector> ).

Answer 11

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 12

First of all, in C++ linked-lists shouldn't be much more trouble to work with than an array. You can use the std::list or the boost pointer listfor linked lists. The key issues with linked lists vs arrays are extra space required for pointers and terrible random access. You should use a linked list if you

• you don't need random access to the data
• you will be adding/deleting elements, especially in the middle of the list

Answer 13

Two things:

Coding a linked list is, no doubt, a bit more work than using an array and he wondered what would justify the additional effort.

Never code a linked list when using C++. Just use the STL. How hard it is to implement should never be a reason to choose one data structure over another because most are already implemented out there.

As for the actual differences between an array and a linked list, the big thing for me is how you plan on using the structure. I'll use the term vector since that's the term for a resizable array in C++.

Indexing into a linked list is slow because you have to traverse the list to get to the given index, while a vector is contiguous in memory and you can get there using pointer math.

Appending onto the end or the beginning of a linked list is easy, since you only have to update one link, where in a vector you may have to resize and copy the contents over.

Removing an item from a list is easy, since you just have to break a pair of links and then attach them back together. Removing an item from a vector can be either faster or slower, depending if you care about order. Swapping in the last item over top the item you want to remove is faster, while shifting everything after it down is slower but retains ordering.

Answer 14

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 15

Arrays make sense where the exact number of items will be known, and where searching by index makes sense. For example, if I wanted to store the exact state of my video output at a given moment without compression I would probably use an array of size [1024][768]. This will provide me with exactly what I need, and a list would be much, much slower to get the value of a given pixel. In places where an array does not make sense there are generally better data types than a list to deal with data effectively.

Answer 16

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.

Answer 17

I'll add one other - 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 ...)

ie:

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 - preprend and tail operations can occur freely without having to copy the original data - very important features when you're treating data as immutable.

Answer 18

i also think that link list is more better than arrays. because we do traversing in link list but not in arrays

Answer 19

as arrays are static in nature, therefore all operations like memory allocation occur at the time of compilation only. So processor has to put less effort at its runtime .

Answer 20

Arrays: 1)Accessing/Searching : fast due to random access of any element in array (remember address of array element will be computed as base address + offset, so its just memory fetch along with one addition operation) — O(1)

2)Inserting/Deleting at end — fast — O(1)

3)Even sequential access on arrays are fast — due to locality of reference, for linked lists this may not well applied

1) The size of the array is fixed. Most often this size is specified at compile time however the size of the array can be deferred until the array is created at runtime (from heap), but after that it remains fixed. This causes to waste memory eventhough e may not use.

2) Inserting/Deleting elements at the front is potentially expensive because existing elements need to be shifted over to make room — O(n)

3)When array was full, to insert more data, it need to be resized, this operation is quite expensive, even may not be possible if in case memory got fragmented. Linked lists performs well where arrays fail to do it.

Linked Lists: 1)Accessing/Searching: sequential access - O(n)

2)Inserting/Deleting at the end — fast — O(1)

3)Inserting/Deleting at the beginning — fast — O(1)

4)It makes good persistent data structure (because two or more lists can have a common tail, so several versions of a data can be maintained, new data comes at the beginning of a new list)

5)No space problems, memory effectively used.

6)Inserting/Deleting in the middle — O(n)

7)can not make use of locality of reference

reference: http://www.cpp-programming.net/c-tidbits/linked-lists/

Answer 21

A widely unappreciated argument for ArrayList and against LinkedList is that LinkedLists are uncomfortable while debugging. The time spent by maintenance developers to understand the program, e.g. to find bugs, increases and IMHO does sometimes not justify the nanoseconds in performance improvements or bytes in memory consumption in enterprise applicatons. Sometimes (well, of course it depends on the type of applications), it's better to waste a few bytes but have an application which is more maintainable or easier to understand.

For example, in a Java environment and using the Eclipse debugger, debugging an ArrayList will reveal a very easy to understand structure:

arrayList   ArrayList<String>
  elementData Object[]
 [0] Object "Foo"
 [1] Object "Foo"
 [2] Object "Foo"
 [3] Object "Foo"
 [4] Object "Foo"
    ...

On the other hand, watching the contents of a LinkedList and finding specific objects becomes a Expand-The-Tree clicking nightmare, not to mention the cognitive overhead needed to filter out the LinkedList internals:

linkedList LinkedList<String>
 header LinkedList$Entry<E>
  element E
  next LinkedList$Entry<E>
   element E "Foo"
   next LinkedList$Entry<E>
    element E "Foo"
    next LinkedList$Entry<E>
     element E "Foo"
     next LinkedList$Entry<E>
     previous LinkedList$Entry<E>
     ...
    previous LinkedList$Entry<E>
   previous LinkedList$Entry<E>
  previous LinkedList$Entry<E>

Answer 22

excellent, but 1. try to keep all related point in one place 2. try summarize the concept in table so that freshers easily understand

Answer 23

Suppose you have an ordered set, which you also want to modify by adding and removing elements. Further, you need ability to retain a reference to an element in such a way that later you can get a previous or next element. For example, a to-do list or set of paragraphs in a book.

First we should note that if you want to retain references to objects outside of the set itself, you will likely end up storing pointers in the array, rather than storing objects themselves. Otherwise you will not be able to insert into array - if objects are embedded into the array they will move during insertions and any pointers to them will become invalid. Same is true for array indexes.

Your first problem, as you have noted yourself, is insertion - linked list allows inserting in O(1), but an array would generally require O(n). This problem can be partially overcome - it is possible to create a data structure that gives array-like by-ordinal access interface where both reading and writing are, at worst, logarithmic.

Your second, and more severe problem is that given an element finding next element is O(n). If the set was not modified you could retain the index of the element as the reference instead of the pointer thus making find-next an O(1) operation, but as it is all you have is a pointer to the object itself and no way to determine its current index in the array other than by scanning the entire "array". This is an insurmountable problem for arrays - even if you can optimized insertions, there is nothing you can do to optimize find-next type operation.

Answer 24

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 25

For me it is like this,

Linked Lists allow only sequential access to elements. Thus the algorithmic complexities is order of O(n) 1. Arrays allow random access to its elements and thus the complexity is order of O(1) 2. Linked lists require an extra storage for references. This makes them impractical for lists of small data items such as characters or boolean values. 2. Arrays do not need an extra storage to point to next data item. Each element can be accessed via indexes. 3. The size of Linked lists are dynamic by nature. 3. The size of array is restricted to declaration. 4. Elements can be inserted and deleted in linked lists indefinitely. 4. Insertion/Deletion of values in arrays are very expensive. It requires memory reallocation.