Java: alternative to LinkedList or int pointer data structure

Question

Since LinkedList is a nightmare in terms of memory overhead and also slower when iterating elements, I would like to have something like int poiter data structure.

So I have a list of ints and I form it by inserting elements at the beginning-middle. When the list is ready, I iterate it in a one-by-one fashion from the left. That is my problem constraint.

• Flavio: Insert in middle is O(1) with LinkedList and O(n) with ArrayList or "int pointer"... I don't think you have other choices, unless your problem has some additional information you can use.
• Alderath: Just out of curiosity... What is the "nightmare in terms of memory overhead" that you are referring to? Each list node stores one reference to its value object, one reference to the previous node and one reference to the next node. This seems like the bare minimum for a linked list to work (well, it might be possible to get rid of the "previous" reference if you only need to use the list for forward iteration). But what is the memory overhead that you are referring to? Is it merely the fact that there is a "previous" reference?

Answer 1

I would profile and try different data structures.

That being said, why not try to use ArrayList; it's fast to iterate and even insert, while in O(n), is fast because moving consecutive data in a cache is lightning fast. (If you also reverse the list while inserting it will be even faster!)

---

Update, since my fellow programmers doesn't understands why I recommend ArrayList for this perticular problem:

The problem isn't inserting elements. In that case the linked list wins direcly (O(1) against the O(n) for the array list). The problem is to find the place to insert them. In this case the LinkedList is really slow. There is a huge overhead to find the place to insert since it doesn't allocate the memory in a "good matter". Lots of cache misses!

OP hasn't posted any code so we only know what OP wants but here is an algorithm analysis for the two cases (where C* are constants):

LinkedList, for each element to insert:

• Iterating O(C1 * n)
• Inserting O(1)

ArrayList, for each element to insert:

• Iterating O(C2 * n)
• Inserting O(C3 * n)

So, both algorithms are in O(n) but looking closely at the constants: C1 is really big (explained above). C2 and C3 on the other hand are small because iterating and moving within the cache is fast.

So, if you have enough memory try an ArrayList!

• Sophie Sperner: I guess I would need reverse it twice.
• Sophie Sperner: Or reverse it only once and then iterate from the end :)
• dacwe: Yes, while inserting / before iterating. Or like you said iterate from the end and do not reverse it. :) Updated answer why I recommended an ArrayList.

Answer 2

LinkedList has indeed terible performance if you constantly do list.get(index);
Use the ListIterator instead so that each time you don't traverse the list over and over.
And if you need to add elements in the middle of the list it will have much better performance than an ArrayList O(1) (since you don't need to move elements)

Update:
The proper way to iterate over a list is using iterators (implicit or explicit). Example of using implicit iterators:

for(E e:list){ 
} 

Never do:

for(int i = 0; list.size(); i++{ 
 E e = list.get(i); 
} 

If the list is a LinkedList this operation is O(N^2) as list.get(i) is traversing the list from the beginning in each iteration of the loop.
Using the first form with an iterator is only O(N) same almost as an ArrayList due to the fact that the iterator "remembers" the last element accessed and starts from there

• dacwe: Finding the index using a Iterator is in O(n) and so is moving the elements when inserting it in the array list. If you could save the pointer and reuse it could be faster.
• Cratylus: If you move through the list using an iterator, you have O(1) access since you move to the next element.If you do list.get(idx) each time, then yes you are right is O(N) but this is NOT the proper way to iterate over a list
• dacwe: You don't understand, finding the place to insert the element is O(n) when using a iterator whichever data structure you use.
• Cratylus: Of course.But inserting the element at that place is O(1) in the case of linked list.
• dacwe: Yes, I know! What I am trying to say is: LinkedList: O(C1*n + 1) => O(n). ArrayList: O(C2*n + C3*n) => O(n). C1 is a big constant, iterating over non consecutive memory is slow (OP question) whereas constants C2 (interating over consecutive memory) and C3 (moving consecutive memory) if fairly small compared to C1.

Answer 3

Try Gaplist, it offers ArrayList-like performance and memory footprint for many use cases. If insertion is mostly sequential (at any index), inserts are close to O(1).

• aioobe: "[...] are close to O(1)" -- Right. And 1 equals 2 for sufficiently large values of 1.
• dantuch: @aioobe so it's not as fast as it's written there?
• aioobe: There's no such thing as "close to O(1)" :) That just doen't make sense.
• Durandal: Close is a vague term, and as such does not specify an exactly quantifieable value or magnitude. So, I'm curious, what would have been a better description in your opinion?

Answer 4

1st step: insert the elements in LinkedList

2nd step: copy elements to ArrayList to iterate.

btw, "nightmare" is a little bit exaggerating to LinkedList:)

• dacwe: Still is O(n) to find the place to insert the elements at so you could use a array list directly.
• 卢声远 Shengyuan Lu: Insert in ArrayList is O(n), LinkedList is O(1).
• dacwe: Yes, but to find the place to insert is O(n) (question: inserting elements somewhere from beginning to middle).