aspose file tools*
The moose likes Java in General and the fly likes ArrayList vs LinkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "ArrayList vs LinkedList" Watch "ArrayList vs LinkedList" New topic
Author

ArrayList vs LinkedList

Ali Ekber
Ranch Hand

Joined: Jun 12, 2005
Posts: 41
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

Joined: Jul 08, 2003
Posts: 24184
    
  34

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.)


[Jess in Action][AskingGoodQuestions]
Dave Wingate
Ranch Hand

Joined: Mar 26, 2002
Posts: 262
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?


Fun programming etcetera!
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24184
    
  34

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: ArrayList vs LinkedList