Which Data Structure? LinkedList or Any Other in Java?

Question

I have specific requirements for the data structure to be used in my program in Java. It (Data Structure) should be able to hold large amounts of data (not fixed), my main operations would be to add at the end, and delete/read from the beginning (LinkedLists look good soo far). But occasionally, I need to delete from the middle also and this is where LinkedLists are soo painful. Can anyone suggest me a way around this? Or any optimizations through which I can make deletion less painful in LinkedLists?

Thanks for the help!

Answer 1

you can try using linked list with a pointers after evey 10000th element so that you can reduce the time to find the middle which you wish to delete. here are some different variations of linked list: http://experimentgarden.blogspot.com/2009/08/performance-analysis-of-thirty-eight.html

Answer 2

LinkedList falls down on random accesses. Deletion, without the random access look up, is constant time and so really not too bad for long lists.

ArrayList is generally fast. Inserts and removes from the middle are faster than you might expect because block memory moves are surprisingly fast. Removals and insertions near the start to cause all the following data to be moved down or up.

ArrayDeque is like ArrayList only it uses a circular buffer and has a strange interface.

Usual advice: try it.

Answer 3

A LinkedHashMap may suit your purpose You'd use an iterator to pull stuff from the front and lookup the entry by key when you needed to access the middle of the list

Answer 4

LinkedHashMap is probably the way to go. Great for iteration, deque operations, and seeking into the middle. Costs extra in memory, though, as you'll need to manage a set of keys on top of your basic collection. Plus I think it'll leave 'gaps' in the spaces you've deleted, leading to a non-consecutive set of keys (shouldn't affect iteration, though).

Edit: Aha! I know what you need: A LinkedMultiSet! All the benefit of a LinkedHashMap, but without the superfluous key set. It's only a little more complex to use, though.

Answer 5

First you need to consider whether you will delete from the center of the list often compared to the length of the list. If your list has N items but you delete much less often than 1/N, don't worry about it. Use LinkedList or ArrayDeque as you prefer. (If your lists are occasionally huge and then shrink, but are mostly small, LinkedList is better as it's easy to recover the memory; otherwise, ArrayDeque doesn't need extra objects, so it's a bit faster and more compact--except the underlying array never shrinks.)

If, on the other hand, you delete quite a bit more often than 1/N, then you should consider a LinkedHashSet, which maintains a linked list queue on top of a hash set--but it is a set, so keep in mind that you can't store duplicate elements. This has the overhead of LinkedList and ArrayDeque put together, but if you're doing central deletes often, it'll likely be worth it.

The optimal structure, however--if you really need every last ounce of speed and are willing to spend the coding time to get it--would be a "resizable" array (i.e. reallocated when it was too small) with a circular buffer where you could blank out elements from the middle by setting them to null. (You could also reallocate the buffer when too much was empty if you had a perverse use case then.) I don't advise coding this unless you either really enjoy coding high-performance data structures or have good evidence that this is one of the key bottlenecks in your code and thus you really need it.