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

User · Answer

Linked List are more of an overhead to maintain than array, it also requires additional memory storage all these points are agreed. But there are a few things which array cant do. In many cases suppose you want an array of length 10^9 you can't get it because getting one continous memory location has to be there. Linked list could be a saviour here.

Suppose you want to store multiple things with data then they can be easily extended in the linked list.

STL containers usually have linked list implementation behind the scene.

User · Answer

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

User · Answer

While many of you have touched upon major adv  dis of linked list vs array  most of the comparisons are how one is better  worse than the other Eg  you can do random access in array but not possible in linked list and others  However  this is assuming link lists and array are going to be applied in a similar application  However a correct answer should be how link list would be preferred over array and vice-versa in a particular application deployment   Suppose you want to implement a dictionary application  what would you use   Array   mmm it would allow easy retrieval through binary search and other search algo    but lets think how link list can be better  Say you want to search  Blob  in dictionary  Would it make sense to have a link list of A- B- C- D---- Z and then each list element also pointing to an array or another list of all words starting with that letter      A - gt  B - gt  C - gt     Z                        Cat  Cave        Banana  Blob   Adam  Apple    Now is the above approach better or a flat array of  Adam Apple Banana Blob Cat Cave     Would it even be possible with array   So a major advantage of link list is you can have an element not just pointing to the next element but also to some other link list array  heap  or any other memory location  Array is a one flat contigous memory sliced into blocks size of the element it is going to store   Link list on the other hand is a chunks of non-contigous memory units  can be any size and can store anything  and pointing to each other the way you want   Similarly lets say you are making a USB drive  Now would you like files to be saved as any array or as a link list   I think you get the idea what I am pointing to

User · Answer

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 list for 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

User · Answer

Depending on your language  some of these disadvantages and advantages could be considered   C Programming Language  When using a linked list  through struct pointers typically   special consideration must be made sure that you are not leaking memory  As was mentioned earlier  linked lists are easy to shuffle  because all were doing is changing pointers  but are we going to remember to free everything   Java  Java has an automatic garbage collect  so leaking memory won t be an issue  but hidden from the high level programmer is the implementation details of what a linked list is  Methods such as removing a node from the middle of the list is more complicated of a procedure than some users of the language would expect it to be

User · Answer

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

User · Answer

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

User · Answer

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 - gt  3 - gt  2 - gt  1 - gt  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

User · Answer

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

User · Answer

Why would someone want to use a linked-list over an array    This is only one reason - if you need a linked list data structure and a programming language you are using is not supports a pointers

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

1- Linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memory  So there is no need to give an initial size of the linked list  Insertion and deletion of nodes are really easier   2- size of the linked list can increase or decrease at run time so there is no memory wastage  In the case of the array  there is a lot of memory wastage  like if we declare an array of size 10 and store only 6 elements in it then space of 4 elements is wasted  There is no such problem in the linked list as memory is allocated only when required   3- Data structures such as stack and queues can be easily implemented using linked list

User · Answer

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

User · Answer

Why a linked list over an array     Well as some have already said  greater speed of insertions and deletions   But maybe we don t have to live with the limits of either  and get the best of both  at the same time     eh    For array deletions  you can use a  Deleted  byte  to represent the fact that a row has been deleted  thus reorging the array is no longer necessary    To ease the burden of insertions  or rapidly changing data  use a linked list for that     Then when referring to them  have your logic first search one  then the other    Thus  using them in combination gives you the best of both   If you have a really large array  you could combine it with another  much smaller array or linked list where the smaller one hold thes 20  50  100 most recently used items   If the one needed is not in the shorter linked list or array  you go to the large array   If found there  you can then add it to the smaller linked list array on the presumption that  things most recently used are most likey to be re-used    and yes  possibly bumping the least recently used item from the list     Which is true in many cases and solved a problem I had to tackle in an  ASP security permissions checking module  with ease  elegance  and impressive speed

User · Answer

Arrays Vs Linked List    Array memory allocation will fail sometimes because of fragmented memory  Caching is better in Arrays as all elements are allocated contiguous memory space  Coding is more complex than Arrays  No size constraint on Linked List  unlike Arrays Insertion Deletion is faster in Linked List and access is faster in Arrays  Linked List better from multi-threading point of view

User · Answer

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 lt String gt    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 lt String gt      header  LinkedList Entry lt E gt          element E         next    LinkedList Entry lt E gt              element E    Foo              next    LinkedList Entry lt E gt                  element E    Foo                  next    LinkedList Entry lt E gt                      element E    Foo                      next    LinkedList Entry lt E gt                      previous    LinkedList Entry lt E gt                                          previous    LinkedList Entry lt E gt              previous    LinkedList Entry lt E gt          previous    LinkedList Entry lt E gt

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

No one ever codes their own linked list anymore  That d be silly  The premise that using a linked list takes more code is just wrong   These days  building a linked list is just an exercise for students so they can understand the concept  Instead  everyone uses a pre-built list  In C    based the on the description in our question  that d probably mean an stl vector   include  lt vector gt      Therefore  choosing a linked list vs an array is entirely about weighing the different characteristics of each structure relative to the needs of your app  Overcoming the additional programming burden should have zero impact on the decision

User · Answer

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

User · Answer

The difference between an array and a linked list is that an array is an index based data structure  every element is associated with an index whereas the linked list is a data structure that uses references  each node is referred to another node  In array size is fixed whereas in link list size is not fixed

User · Answer

People using linklist must read  People will fall in love with array again  It talks about  Out Of Order exeuction hardware prefetch  memory latency etc   http   www futurechips org thoughts-for-researchers quick-post-linked-lists html

User · Answer

Linked-list are especially useful when the collection is constantly growing  amp  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

User · Answer

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

User · Answer

Besides convenience in insertions and deletions  the memory representation of linked list is different than the arrays  There is no restriction on the number of elements in a linked list  while in the arrays  you have to specify the total number of elements  Check this article

User · Answer

Here s a quick one   Removal of items is quicker

User · Answer

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

[arrays] Array versus linked-list

Examples related to arrays

Examples related to data-structures

Examples related to linked-list

Examples related to language-agnostic