8

Of course, I know about the performance difference between arraylist and linkedlist. I have run tests myself and seen the huge difference in time and memory for insertion/deletion and iteration between arraylist and linkedlist for a very big list.

(Correct me if i am wrong)We generally prefer arraylist over linkedlist because:

1)We practically do iterations more often than insertion/deletion. So we prefer iterations to be faster than insertion/deletion.

2)The memory overhead of linkedlist is much more than arraylist

3)There is NO way in which we can define a list as linkedlist while inserting/deleting in batch, and as arraylist while iterating. It is because arraylist and linkedlist have fundamentally different data-storage techniques.

Am I wrong about the 3rd point [I hope so :)]? Is there any possibility to have benefits of these two data structures in a single list? I guess, data structure designers must have thought about it.

nkr
  • 3,026
  • 7
  • 31
  • 39
Biman Tripathy
  • 2,766
  • 3
  • 23
  • 27
  • 4
    Possible duplicate: http://stackoverflow.com/questions/1712952/is-there-a-known-implementation-of-an-indexed-linked-list – Aubin Nov 18 '12 at 19:12
  • You said it yourself, if there was a non-compromise solution that had all those benefits, nobody would even know about `ArrayList` and `LinkedList`. – Marko Topolnik Nov 18 '12 at 19:17
  • @Aubin thanks for the link. +1 :) but its a 2009 question. Any improvements in the field of Data structures in the past 3 years? Especially after the release of Java 7? – Biman Tripathy Nov 18 '12 at 19:26
  • The well known containers algorithms are not recently discovered... – Aubin Nov 18 '12 at 19:30
  • @MarkoTopolnik So what I have mentioned in point 3 is correct? Currently we do not have any data structure which is as fast as Arraylist regarding iteration and as fast as Linkedlist regarding insertion/deletion? – Biman Tripathy Nov 18 '12 at 19:41
  • @Aubin Please share some useful info like Trimble did by sharing about FastList and FastTable – Biman Tripathy Nov 18 '12 at 19:52
  • You have mentioned just two requirements (performance-related). Those two could possibly be matched, but **not** together with space efficiency of the `ArrayList`. – Marko Topolnik Nov 18 '12 at 19:56

3 Answers3

1

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

Christian Trimble
  • 2,126
  • 16
  • 27
0

You might want to look into Clojure's "vectors" (which are a lot more than a simple array under the hood): http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/. They are O(log32 n) for lookup and insertion.

Note that these are directly usable from Java! (Actually, they're implemented in Java code.)

Alex D
  • 29,755
  • 7
  • 80
  • 126
0

Probably we have another points to consider, but one aspect that make me choose LinkedList over ArrayList is when:

  • When I don't need to get an element by index (in case of process all elements)
  • When I don't know the size when creating my list

Here is an interesting manifesto about this topic.

Jonatas Emidio
  • 73
  • 8
  • Even then, using an array list will likely perform better than a linked list (and use less memory). – Mark Rotteveel Dec 18 '18 at 18:05
  • 1
    Hi @MarkRotteveel, You are right, here is a very interesting discussion about this case: https://stackoverflow.com/questions/11564352/arraylist-vs-linkedlist-from-memory-allocation-perspective – Jonatas Emidio Dec 19 '18 at 18:38