Friday, December 27, 2013

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.
share|improve this question
 
In Java, ArrayList and LinkedList use exactly the same code other than the constructor. Your "array list...used as easily as or easier than the linked list" doesn't make sense. Please provide an example of an ArrayList being "easier" than a LinkedList. –  S.Lott Dec 26 '08 at 12:45
add comment

6 Answers

up vote57down voteaccepted
Linked lists are preferable over arrays when:
a) you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)
b) 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
c) you don't need random access to any elements
d) you want to be able to insert items in the middle of the list (such as a priority queue)
Arrays are preferable when:
a) you need indexed/random access to elements
b) 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
c) 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.
d) 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.
share|improve this answer
1 
Good start, but this leaves out important things: lists support structure sharing, arrays are denser and have better locality. –  Darius Bacon Dec 26 '08 at 8:26
 
Practically, the performance difference between arraylists and arrays is negligible. This assumes you compare comparable and, for example, when you know the size beforehand, you tell the arraylist about it. – svick Jul 3 '11 at 21:39
4 
Since when does LinkedList has O(1) inserts/deletes (which is what I suppose you mean when you sayconstant time inserts/deletes)? Inserting stuff into the middle of a LinkedList is always O(n) –  Pacerier Dec 4 '11 at 16:37 
4 
LinkedLists do have O(1) inserts if you already happen to be in the location of the insertion (via an iterator). Not always, though. –  advs89 Jan 24 '12 at 6:14
1 
Using linked lists for priority queues is a very stupid idea. Dynamic array-backed heaps allow for O(lg n) amortized insertion and worst-case logarithmic delete-min, and are among the fastest practical priority queue structures. –  larsmans Jun 4 at 13:29 
add comment

4 comments:

oakleyses said...

louis vuitton handbags, oakley sunglasses, louboutin, longchamp outlet, nike shoes, louis vuitton outlet stores, chanel handbags, burberry outlet, prada outlet, jordan shoes, tiffany and co, michael kors outlet, tory burch outlet, louis vuitton outlet, longchamp handbags, nike free, true religion jeans, michael kors outlet, kate spade outlet, polo ralph lauren outlet, tiffany and co, prada handbags, polo ralph lauren outlet, michael kors outlet, michael kors outlet, longchamp handbags, oakley sunglasses, ray ban sunglasses, kate spade handbags, burberry outlet, louis vuitton outlet, louboutin outlet, louboutin, coach factory outlet, air max, air max, coach outlet, gucci outlet, christian louboutin shoes, michael kors outlet, coach purses, ray ban sunglasses, michael kors outlet, louis vuitton, coach outlet store online, true religion jeans, oakley sunglasses cheap

oakleyses said...

ralph lauren, lululemon, air max, hollister, north face, nike air max, polo lacoste, vanessa bruno, timberland, vans pas cher, louboutin, louis vuitton, oakley pas cher, air max pas cher, nike roshe run, air max, true religion outlet, barbour, sac longchamp, air force, hollister, sac louis vuitton, nike free, polo ralph lauren, nike trainers, louis vuitton uk, nike roshe, sac hermes, longchamp, michael kors, sac burberry, sac guess, mulberry, new balance pas cher, converse pas cher, sac louis vuitton, hogan outlet, nike tn, north face, true religion outlet, ray ban pas cher, michael kors, air jordan, nike blazer, nike free pas cher, michael kors pas cher, abercrombie and fitch, ray ban sunglasses

oakleyses said...

mac cosmetics, mont blanc, marc jacobs, canada goose outlet, nike huarache, vans shoes, soccer jerseys, hollister, giuseppe zanotti, beats by dre, abercrombie and fitch, longchamp, insanity workout, celine handbags, bottega veneta, ghd, nfl jerseys, north face outlet, chi flat iron, ugg boots, birkin bag, ugg australia, canada goose, herve leger, ugg pas cher, rolex watches, valentino shoes, canada goose uk, canada goose, ferragamo shoes, canada goose, ugg boots, uggs outlet, north face jackets, soccer shoes, asics running shoes, new balance shoes, p90x, lululemon outlet, canada goose jackets, mcm handbags, instyler, babyliss pro, ugg, wedding dresses, jimmy choo outlet, reebok outlet, nike roshe run

oakleyses said...

parajumpers, karen millen, air max, converse, pandora charms, moncler, louboutin, moncler, links of london, lancel, juicy couture outlet, oakley, hollister, pandora charms, supra shoes, thomas sabo, canada goose, gucci, wedding dresses, timberland boots, swarovski crystal, air max, coach outlet store online, moncler, ray ban, canada goose, moncler, ugg, louis vuitton, swarovski, hollister, montre homme, moncler, hollister clothing store, ralph lauren, rolex watches, moncler outlet, moncler, iphone 6 cases, baseball bats, juicy couture outlet, toms shoes, vans, pandora jewelry, ugg, converse shoes