Advantages of the “both” arraylist and linked list ... are possible in java?

Question

Of course, I know about the performance difference between arraylist and linked list. I ran the tests myself and saw a huge difference in time and memory for insert / delete and iterate between arraylist and linked list for a very large list.

(Correct me if I am wrong) We usually prefer arraylist over a linked list, because:

1) We practically iterate more often than insert / delete. Therefore, we prefer iterations to be faster than insert / delete.

2) The overhead of a linked list's memory is much more than an arraylist

3) There is NO way that we can define a list as a linked list when inserting / deleting in batch mode and as an arraylist during iteration. This is due to the fact that arraylist and linked list have fundamentally different methods of data storage.

Am I wrong about the third paragraph [I hope so :)]? Is it possible to take advantage of these two data structures in one list? I think data structure developers should have thought about this.

Answer 1

If you are looking for some more realistic collection implementations, check out Javolution . This package provides FastList and FastTable , which can at least reduce the cost of choosing between linked lists and array lists.

Answer 2

You might want to look into Clojure's “vectors” (which are much more than a simple array under the hood): http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ . This is O (log32 n) for search and insert.

Please note that they are directly used with Java! (In fact, they are implemented in Java code.)

Answer 3

Perhaps we have a few more points to consider, but one aspect that makes me choose LinkedList instead of ArrayList is when:

• When I do not need to get an element by index (in the case of a process, all elements)
• When I do not know the size when creating my list

Here is an interesting manifesto on this subject.