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

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 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.