Java performance and memory: LinkedList & arrays

Question

I'm building an Android app (so machines with limited resources) and I want to know how picky I should be with LinkedLists.

I know that arrays are the lightest containers and are the best at random access, so they're obviously the ideal choice if you only consider performance. However, their rigidness is a pain when you don't know how big your list will be.

So here's my question: is it worth it to systematically use the following type of mechanism in classes who have one or more list of unpredictable size:

public class unpredictable
public Object[]realArray;
private LinkedList<Object> temp;

//what using classes will call to add items
public void add(Object item) 
{
    temp.add( item );
}

//what the outer class calls when it knows there's nothing left to add 
public void doneAdding() 
{
    realArray = new Object[tmp.size()];
    transferAndRecycle();
}

private void transferAndRecycle()
{
    // copy items from linkedlist to array
}

So I guess I'm asking if it's worth it to take the extra steps to get rid of the extra space Java's LinkedList object takes?

Any input? Thanks

It smells of premature optimization.

Robin
– Robin

2011-07-03 22:43:59 +00:00
Commented Jul 3, 2011 at 22:43 — Robin
– Robin, Commented Jul 3, 2011 at 22:43

ncmathsadist · Accepted Answer · 2011-07-03 22:33:21Z

9

I think you are providing a lot of services that the ArrayList class already contains. The ArrayList gives you O(1) element access; with a linked list it's O(n). The underlying mechanism of an ArrayList is an array. You can control the size of this array by manipulating the capacity.

Look closely at ArrayList -- you may avoid reinventing some wheels.

Additional thought: Arrays and Generics don't play nicely. ArrayLists do. That is a small item but could be important to you.

answered Jul 3, 2011 at 22:33

ncmathsadist

4,9253 gold badges34 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

soBinary Over a year ago

Thank you! My profs hammered linkedlists so deep into our brains these past 2 semesters that when I came back to Java this summer I didn't even consider anything else.

user330315 · Accepted Answer · 2011-07-03 22:43:38Z

1

In addition to what ncmathsadist already said:

Your choice should also depend on which operation happens more often: adding/removing elements or accessing a single element directly. If it's the former, use a LinkedList. If it's the latter use an ArrayList.

Don't forget: when resizing the array (be it your own solution or Java's ArrayList) there is one point in time where twice the memory is allocated: once for the "old arry" and once for the "new array" right before the resize operation is finished.

So if memory is really your concern is something you should also think about.

answered Jul 3, 2011 at 22:43

user330315

Comments

seand · Accepted Answer · 2011-07-03 22:49:43Z

1

ArrayList has better locality of reference and less memory references than LinkedList. Generally unless you need a specific LinkedList trait (quick deletions in the middle, splicing etc) prefer ArrayList

answered Jul 3, 2011 at 22:49

seand

5,3162 gold badges26 silver badges38 bronze badges

Comments

GSingh · Accepted Answer · 2011-07-04 05:28:42Z

0

If you take a look at the Java Docs, you can find methods provided by the class that already have the desired functions you would like in you problem. For example, this is a function that converts an arraylist to an array.

http://download.oracle.com/javase/1.5.0/docs/api/

T[] toArray(T[] a) Returns an array containing all of the elements in this list in the correct order; the runtime type of the returned array is that of the specified array.

edited Jul 4, 2011 at 5:28

answered Jul 4, 2011 at 1:15

GSingh

1761 silver badge8 bronze badges

1 Comment

soBinary Over a year ago

I know how to convert a Collection to an array... Read my question again, you misunderstood it.

Collectives™ on Stack Overflow

Java performance and memory: LinkedList & arrays

4 Answers 4

1 Comment

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related