• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

ArrayList vs LinkedList

 
Ali Ekber
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How do ArrayList and LinkedList compare to each other when you are storing information and searching? Mostly in the areas of efficiency and resource (memory) handling. Thanks.
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ArrayList will generally use less memory per item -- often quite a bit less. It also gives you faster access to a given item by index (constant time as opposed to time linearaly proportional to size.)

LinkedList, however, has a big advantage in one area: adding and deleting items in the middle of the list is much faster than the equivalent operations on an ArrayList (again, it's constant time vs. linear time.)
 
Dave Wingate
Ranch Hand
Posts: 262
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why would LinkeList use so much more memory per item. I would have figured that the only extra memory needed for a linked implementation would be 2 pointers per object (next & previous). What else am I not thinkingof that would account for the extra memory per item?
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, even just that is already twice again as much space per item, right? Then you have to add to that whatever the expense of a Java object is in general, because each link is an Object with three members (the item and those two pointers.) The exact size isn't specified (it's VM dependent,) but it's at least another 8 bytes in any VM I've seem, and 16 bytes is more typical. That means (assuming 4-byte pointers) that LinkedList uses 24 bytes per item, as opposed to 4 for ArrayList -- 600% more storage per item.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic