• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

ArrayList vs LinkedList

 
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.)
 
Ranch Hand
Posts: 262
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
My pie came with a little toothpic holding up this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic