When to use a linked list over an array array list

Question

I use a lot of lists and arrays but I have yet to come across a scenario in which the array list couldn t be used just as easily as  if not easier than  the linked list   I was hoping someone could give me some examples of when the linked list is notably better

User · Answer

Arrays  by far  are the most widely used data structures  However  linked lists prove useful in their own unique way where arrays are clumsy - or expensive  to say the least   Linked lists are useful to implement stacks and queues in situations where their size is subject to vary  Each node in the linked list can be pushed or popped without disturbing the majority of the nodes  Same goes for insertion deletion of nodes somewhere in the middle  In arrays  however  all the elements have to be shifted  which is an expensive job in terms of execution time   Binary trees and binary search trees  hash tables  and tries are some of the data structures wherein - at least in C - you need linked lists as a fundamental ingredient for building them up   However  linked lists should be avoided in situations where it is expected to be able to call any arbitrary element by its index

User · Answer

A simple answer to the question can be given using these points   Arrays are to be used when a collection of similar type data elements is required  Whereas  linked list is a collection of mixed type data linked elements known as nodes   In array  one can visit any element in O 1  time  Whereas  in linked list we would need to traverse entire linked list from head to the required node taking O n  time   For arrays  a specific size needs to be declared initially  But linked lists are dynamic in size

User · Answer

To add to the other answers  most array list implementations reserve extra capacity at the end of the list so that new elements can be added to the end of the list in O 1  time  When the capacity of an array list is exceeded  a new  larger array is allocated internally  and all the old elements are copied over  Usually  the new array is double the size of the old one  This means that on average  adding new elements to the end of an array list is an O 1  operation in these implementations  So even if you don t know the number of elements in advance  an array list may still be faster than a linked list for adding elements  as long as you are adding them at the end  Obviously  inserting new elements at arbitrary locations in an array list is still an O n  operation   Accessing elements in an array list is also faster than a linked list  even if the accesses are sequential  This is because array elements are stored in contiguous memory and can be cached easily  Linked list nodes can potentially be scattered over many different pages   I would recommend only using a linked list if you know that you re going to be inserting or deleting items at arbitrary locations  Array lists will be faster for pretty much everything else

User · Answer

The advantage of lists appears if you need to insert items in the middle and don t want to start resizing the array and shifting things around    You re correct in that this is typically not the case  I ve had a few very specific cases like that  but not too many

User · Answer

Arrays have O 1  random access  but are really expensive to add stuff onto or remove stuff from   Linked lists are really cheap to add or remove items anywhere and to iterate  but random access is O n

User · Answer

To add to the other answers  most array list implementations reserve extra capacity at the end of the list so that new elements can be added to the end of the list in O 1  time  When the capacity of an array list is exceeded  a new  larger array is allocated internally  and all the old elements are copied over  Usually  the new array is double the size of the old one  This means that on average  adding new elements to the end of an array list is an O 1  operation in these implementations  So even if you don t know the number of elements in advance  an array list may still be faster than a linked list for adding elements  as long as you are adding them at the end  Obviously  inserting new elements at arbitrary locations in an array list is still an O n  operation   Accessing elements in an array list is also faster than a linked list  even if the accesses are sequential  This is because array elements are stored in contiguous memory and can be cached easily  Linked list nodes can potentially be scattered over many different pages   I would recommend only using a linked list if you know that you re going to be inserting or deleting items at arbitrary locations  Array lists will be faster for pretty much everything else

User · Answer

It all depends what type of operation you are doing while iterating   all data structures have trade off between time and memory and depending on our needs we should choose the right DS  So there are some cases where LinkedList are faster then array and vice versa   Consider the three basic operation on data structures    Searching   Since array is index based data structure searching array get index  will take O 1  time while linkedlist is not index DS so you will need to traverse up to index   where index  lt  n   n is size of linked list   so array is faster the linked list when have random access of elements    Q So what s the beauty behind this    As Arrays are contiguous memory blocks  large chunks of them will be loaded into the cache upon first access this makes it comparatively quick to access remaining elements of the array as much as we access the elements in array locality of reference also increases thus less catch misses  Cache locality refers to the operations being in the cache and thus execute much faster as compared to in memory basically In array we maximize the chances of sequential element access being in the cache  While Linked lists aren t necessarily in contiguous blocks of memory  there s no guarantee that items which appear sequentially in the list are actually arranged near each-other in memory  this means fewer cache hits e g  more cache misses because we need to read from memory for every access of linked list element which increases the time it takes to access them and degraded performance so if we are doing more random access operation aka searching   array will be fast as explained below    Insertion   This is easy and fast in LinkedList as insertion is O 1  operation in LinkedList  in Java  as compared to array  consider the case when array is full  we need to copy contents to new array if array gets full which makes inserting an element into ArrayList of O n  in worst case  while ArrayList also needs to update its index if you insert something anywhere except at the end of array   in case of linked list we needn t to be resize it  you just need to update pointers    Deletion   It works like insertions and better in LinkedList than array

User · Answer

Algorithm           ArrayList   LinkedList seek front            O 1          O 1  seek back             O 1          O 1  seek to index         O 1          O N  insert at front       O N          O 1  insert at back        O 1          O 1  insert after an item  O N          O 1    ArrayLists are good for write-once-read-many or appenders  but bad at add remove from the front or middle

User · Answer

Hmm  Arraylist can be used in cases like follows I guess    you are not sure how many elements will be present  but you need to access all the elements randomly through indexing   For eg  you need to import and access all elements in a contact list  the size of which is unknown to you

User · Answer

Hmm  Arraylist can be used in cases like follows I guess    you are not sure how many elements will be present  but you need to access all the elements randomly through indexing   For eg  you need to import and access all elements in a contact list  the size of which is unknown to you

User · Answer

Arrays  by far  are the most widely used data structures  However  linked lists prove useful in their own unique way where arrays are clumsy - or expensive  to say the least   Linked lists are useful to implement stacks and queues in situations where their size is subject to vary  Each node in the linked list can be pushed or popped without disturbing the majority of the nodes  Same goes for insertion deletion of nodes somewhere in the middle  In arrays  however  all the elements have to be shifted  which is an expensive job in terms of execution time   Binary trees and binary search trees  hash tables  and tries are some of the data structures wherein - at least in C - you need linked lists as a fundamental ingredient for building them up   However  linked lists should be avoided in situations where it is expected to be able to call any arbitrary element by its index

User · Answer

I think that main difference is whether you frequently need to insert or remove stuff from the top of the list   With an array  if you remove something from the top of list than the complexity is o n  because all of the indices of the array elements will have to shift   With a linked list  it is o 1  because you need only create the node  reassign the head and assign the reference to next as the previous head   When frequently inserting or removing at the end of the list  arrays are preferable because the complexity will be o 1   no reindexing is required  but for a linked list it will be o n  because you need to go from the head to the last node     I think that searching in both linked list and arrays will be o log n  because you will be probably be using a binary search

User · Answer

Use linked list for Radix Sort over arrays and for polynomial operations

User · Answer

Algorithm           ArrayList   LinkedList seek front            O 1          O 1  seek back             O 1          O 1  seek to index         O 1          O N  insert at front       O N          O 1  insert at back        O 1          O 1  insert after an item  O N          O 1    ArrayLists are good for write-once-read-many or appenders  but bad at add remove from the front or middle

User · Answer

The advantage of lists appears if you need to insert items in the middle and don t want to start resizing the array and shifting things around    You re correct in that this is typically not the case  I ve had a few very specific cases like that  but not too many

User · Answer

I did some benchmarking  and found that the list class is actually faster than LinkedList for random inserting   using System  using System Collections Generic  using System Diagnostics   namespace ConsoleApplication1       class Program               static void Main string   args                        int count   20000              Random rand   new Random 12345                Stopwatch watch   Stopwatch StartNew                LinkedList lt int gt  ll   new LinkedList lt int gt                 ll AddLast 0               for  int i   1  i  lt  count  i                                  ll AddBefore ll Find rand Next i   i                              Console WriteLine  LinkedList Random Add   0 ms   watch ElapsedMilliseconds                watch   Stopwatch StartNew                List lt int gt  list   new List lt int gt                 list Add 0               for  int i   1  i  lt  count  i                                  list Insert list IndexOf rand Next i    i                              Console WriteLine  List Random Add   0 ms   watch ElapsedMilliseconds                Console ReadLine                        It takes 900 ms for the linked list and 100ms for the list class   It creates lists of subsequent integer numbers  Each new integer is inserted after a random number which is already in the list  Maybe the List class uses something better than just an array

User · Answer

Linked lists are preferable over arrays when    you need constant-time insertions deletions from the list  such as in real-time computing where time predictability is absolutely critical  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    Arrays are preferable when    you need indexed random access to elements you know the number of elements in the array ahead of time so that you can allocate the  correct amount of memory for the array you need speed when iterating through all the elements in sequence   You can use pointer math on the array to access each element  whereas you need to lookup the node based on the pointer for each element in linked list  which may result in page faults which may result in performance hits  memory is a concern   Filled arrays take up less memory than linked lists   Each element in the array is just the data   Each linked list node requires the data as well as one  or more  pointers to the other elements in the linked list    Array Lists  like those in  Net  give you the benefits of arrays  but dynamically allocate  resources for you so that you don t need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around   Performance-wise  arraylists are slower than raw arrays

User · Answer

Arrays have O 1  random access  but are really expensive to add stuff onto or remove stuff from   Linked lists are really cheap to add or remove items anywhere and to iterate  but random access is O n

User · Answer

It all depends what type of operation you are doing while iterating   all data structures have trade off between time and memory and depending on our needs we should choose the right DS  So there are some cases where LinkedList are faster then array and vice versa   Consider the three basic operation on data structures    Searching   Since array is index based data structure searching array get index  will take O 1  time while linkedlist is not index DS so you will need to traverse up to index   where index  lt  n   n is size of linked list   so array is faster the linked list when have random access of elements    Q So what s the beauty behind this    As Arrays are contiguous memory blocks  large chunks of them will be loaded into the cache upon first access this makes it comparatively quick to access remaining elements of the array as much as we access the elements in array locality of reference also increases thus less catch misses  Cache locality refers to the operations being in the cache and thus execute much faster as compared to in memory basically In array we maximize the chances of sequential element access being in the cache  While Linked lists aren t necessarily in contiguous blocks of memory  there s no guarantee that items which appear sequentially in the list are actually arranged near each-other in memory  this means fewer cache hits e g  more cache misses because we need to read from memory for every access of linked list element which increases the time it takes to access them and degraded performance so if we are doing more random access operation aka searching   array will be fast as explained below    Insertion   This is easy and fast in LinkedList as insertion is O 1  operation in LinkedList  in Java  as compared to array  consider the case when array is full  we need to copy contents to new array if array gets full which makes inserting an element into ArrayList of O n  in worst case  while ArrayList also needs to update its index if you insert something anywhere except at the end of array   in case of linked list we needn t to be resize it  you just need to update pointers    Deletion   It works like insertions and better in LinkedList than array

User · Answer

Arrays have O 1  random access  but are really expensive to add stuff onto or remove stuff from   Linked lists are really cheap to add or remove items anywhere and to iterate  but random access is O n

User · Answer

1  As explained above the insert and remove operations give good performance  O 1   in LinkedList compared to ArrayList O n    Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice   2  Search  get method  operations are fast in Arraylist  O 1   but not in LinkedList  O n   so If there are less add and remove operations and more search operations requirement  ArrayList would be your best bet

User · Answer

I think that main difference is whether you frequently need to insert or remove stuff from the top of the list   With an array  if you remove something from the top of list than the complexity is o n  because all of the indices of the array elements will have to shift   With a linked list  it is o 1  because you need only create the node  reassign the head and assign the reference to next as the previous head   When frequently inserting or removing at the end of the list  arrays are preferable because the complexity will be o 1   no reindexing is required  but for a linked list it will be o n  because you need to go from the head to the last node     I think that searching in both linked list and arrays will be o log n  because you will be probably be using a binary search

User · Answer

Those are the most common used implementations of Collection   ArrayList    insert delete at the end generally O 1  worst case O n  insert delete in the middle O n  retrieve any position O 1    LinkedList    insert delete in any position O 1   note if you have a reference to the element  retrieve in the middle O n  retrieve first or last element O 1    Vector  don t use it  It is an old implementation similar to ArrayList but with all methods synchronized  It is not the correct approach for a shared list in a multithreading environment   HashMap  insert delete retrieve by key in O 1   TreeSet insert delete contains in O log N   HashSet insert remove contains size in O 1

User · Answer

Use linked list for Radix Sort over arrays and for polynomial operations

User · Answer

Those are the most common used implementations of Collection   ArrayList    insert delete at the end generally O 1  worst case O n  insert delete in the middle O n  retrieve any position O 1    LinkedList    insert delete in any position O 1   note if you have a reference to the element  retrieve in the middle O n  retrieve first or last element O 1    Vector  don t use it  It is an old implementation similar to ArrayList but with all methods synchronized  It is not the correct approach for a shared list in a multithreading environment   HashMap  insert delete retrieve by key in O 1   TreeSet insert delete contains in O log N   HashSet insert remove contains size in O 1

User · Answer

Hmm  Arraylist can be used in cases like follows I guess    you are not sure how many elements will be present  but you need to access all the elements randomly through indexing   For eg  you need to import and access all elements in a contact list  the size of which is unknown to you

User · Answer

Linked lists are preferable over arrays when    you need constant-time insertions deletions from the list  such as in real-time computing where time predictability is absolutely critical  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    Arrays are preferable when    you need indexed random access to elements you know the number of elements in the array ahead of time so that you can allocate the  correct amount of memory for the array you need speed when iterating through all the elements in sequence   You can use pointer math on the array to access each element  whereas you need to lookup the node based on the pointer for each element in linked list  which may result in page faults which may result in performance hits  memory is a concern   Filled arrays take up less memory than linked lists   Each element in the array is just the data   Each linked list node requires the data as well as one  or more  pointers to the other elements in the linked list    Array Lists  like those in  Net  give you the benefits of arrays  but dynamically allocate  resources for you so that you don t need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around   Performance-wise  arraylists are slower than raw arrays

User · Answer

Linked lists are preferable over arrays when    you need constant-time insertions deletions from the list  such as in real-time computing where time predictability is absolutely critical  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    Arrays are preferable when    you need indexed random access to elements you know the number of elements in the array ahead of time so that you can allocate the  correct amount of memory for the array you need speed when iterating through all the elements in sequence   You can use pointer math on the array to access each element  whereas you need to lookup the node based on the pointer for each element in linked list  which may result in page faults which may result in performance hits  memory is a concern   Filled arrays take up less memory than linked lists   Each element in the array is just the data   Each linked list node requires the data as well as one  or more  pointers to the other elements in the linked list    Array Lists  like those in  Net  give you the benefits of arrays  but dynamically allocate  resources for you so that you don t need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around   Performance-wise  arraylists are slower than raw arrays

User · Answer

To add to the other answers  most array list implementations reserve extra capacity at the end of the list so that new elements can be added to the end of the list in O 1  time  When the capacity of an array list is exceeded  a new  larger array is allocated internally  and all the old elements are copied over  Usually  the new array is double the size of the old one  This means that on average  adding new elements to the end of an array list is an O 1  operation in these implementations  So even if you don t know the number of elements in advance  an array list may still be faster than a linked list for adding elements  as long as you are adding them at the end  Obviously  inserting new elements at arbitrary locations in an array list is still an O n  operation   Accessing elements in an array list is also faster than a linked list  even if the accesses are sequential  This is because array elements are stored in contiguous memory and can be cached easily  Linked list nodes can potentially be scattered over many different pages   I would recommend only using a linked list if you know that you re going to be inserting or deleting items at arbitrary locations  Array lists will be faster for pretty much everything else

User · Answer

Linked lists are preferable over arrays when    you need constant-time insertions deletions from the list  such as in real-time computing where time predictability is absolutely critical  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    Arrays are preferable when    you need indexed random access to elements you know the number of elements in the array ahead of time so that you can allocate the  correct amount of memory for the array you need speed when iterating through all the elements in sequence   You can use pointer math on the array to access each element  whereas you need to lookup the node based on the pointer for each element in linked list  which may result in page faults which may result in performance hits  memory is a concern   Filled arrays take up less memory than linked lists   Each element in the array is just the data   Each linked list node requires the data as well as one  or more  pointers to the other elements in the linked list    Array Lists  like those in  Net  give you the benefits of arrays  but dynamically allocate  resources for you so that you don t need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around   Performance-wise  arraylists are slower than raw arrays

User · Answer

I did some benchmarking  and found that the list class is actually faster than LinkedList for random inserting   using System  using System Collections Generic  using System Diagnostics   namespace ConsoleApplication1       class Program               static void Main string   args                        int count   20000              Random rand   new Random 12345                Stopwatch watch   Stopwatch StartNew                LinkedList lt int gt  ll   new LinkedList lt int gt                 ll AddLast 0               for  int i   1  i  lt  count  i                                  ll AddBefore ll Find rand Next i   i                              Console WriteLine  LinkedList Random Add   0 ms   watch ElapsedMilliseconds                watch   Stopwatch StartNew                List lt int gt  list   new List lt int gt                 list Add 0               for  int i   1  i  lt  count  i                                  list Insert list IndexOf rand Next i    i                              Console WriteLine  List Random Add   0 ms   watch ElapsedMilliseconds                Console ReadLine                        It takes 900 ms for the linked list and 100ms for the list class   It creates lists of subsequent integer numbers  Each new integer is inserted after a random number which is already in the list  Maybe the List class uses something better than just an array

User · Answer

In reality memory locality has a huge performance influence in real processing   The increased use of disk streaming in  big data  processing vs random access shows how structuring your application around this can dramatically improve performance on a larger scale   If there is any way to access an array sequentially that is by far the best performing  Designing with this as a goal should be at least considered if performance is important

User · Answer

The advantage of lists appears if you need to insert items in the middle and don t want to start resizing the array and shifting things around    You re correct in that this is typically not the case  I ve had a few very specific cases like that  but not too many

User · Answer

A simple answer to the question can be given using these points   Arrays are to be used when a collection of similar type data elements is required  Whereas  linked list is a collection of mixed type data linked elements known as nodes   In array  one can visit any element in O 1  time  Whereas  in linked list we would need to traverse entire linked list from head to the required node taking O n  time   For arrays  a specific size needs to be declared initially  But linked lists are dynamic in size

User · Answer

Arrays have O 1  random access  but are really expensive to add stuff onto or remove stuff from   Linked lists are really cheap to add or remove items anywhere and to iterate  but random access is O n

User · Answer

In reality memory locality has a huge performance influence in real processing   The increased use of disk streaming in  big data  processing vs random access shows how structuring your application around this can dramatically improve performance on a larger scale   If there is any way to access an array sequentially that is by far the best performing  Designing with this as a goal should be at least considered if performance is important

User · Answer

Hmm  Arraylist can be used in cases like follows I guess    you are not sure how many elements will be present  but you need to access all the elements randomly through indexing   For eg  you need to import and access all elements in a contact list  the size of which is unknown to you

User · Answer

To add to the other answers  most array list implementations reserve extra capacity at the end of the list so that new elements can be added to the end of the list in O 1  time  When the capacity of an array list is exceeded  a new  larger array is allocated internally  and all the old elements are copied over  Usually  the new array is double the size of the old one  This means that on average  adding new elements to the end of an array list is an O 1  operation in these implementations  So even if you don t know the number of elements in advance  an array list may still be faster than a linked list for adding elements  as long as you are adding them at the end  Obviously  inserting new elements at arbitrary locations in an array list is still an O n  operation   Accessing elements in an array list is also faster than a linked list  even if the accesses are sequential  This is because array elements are stored in contiguous memory and can be cached easily  Linked list nodes can potentially be scattered over many different pages   I would recommend only using a linked list if you know that you re going to be inserting or deleting items at arbitrary locations  Array lists will be faster for pretty much everything else

User · Answer

1  As explained above the insert and remove operations give good performance  O 1   in LinkedList compared to ArrayList O n    Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice   2  Search  get method  operations are fast in Arraylist  O 1   but not in LinkedList  O n   so If there are less add and remove operations and more search operations requirement  ArrayList would be your best bet

User · Answer

The advantage of lists appears if you need to insert items in the middle and don t want to start resizing the array and shifting things around    You re correct in that this is typically not the case  I ve had a few very specific cases like that  but not too many

[arrays] When to use a linked list over an array/array list?

Examples related to arrays

Examples related to list

Examples related to arraylist

Examples related to linked-list