Which Java collection's Linked list adds in O(1) when given an element?

views:

566

answers:

Which Java collection's Linked list adds in O(1) when given an element?

hi,

i need to insert into a very large LinkedList, whose elements i hold in a fast-access HashMap.
it's important to keep the list in order (which is not the natural order of the keys).

i thought it would be possible to hash the linked list nodes, then insert directly on the node (getting the node from the map + insert in a linked list == constant time).

however, i couldn't find any Java collection that would do that or similar...
i'm currently using LinkedHashMap, which doesn't meet the requirements above.

thanks, asaf :-)

+3 A:

If the LinkedList should be sorted after each insertion, I doubt you will be able to find such a data structure, as it implies that you would get a sorting algorithm with time complexity O(n), which has been proven impossible. (The lowest bound on sorting is O(n log n).) The best you could get on insertion is O(log n).

Then you can use the TreeMap data structure.

MicSim 2009-10-20 09:27:04

As it's "important to keep the list in order" your effectively doing an insertion sort which has a best-case-performance of O(n). Additionally, you must not confuse hashing with sorting - as the order of a hash isn't defined as it depends on the size of the underlying hashtable. (Using a hash to insert would only be useful if you know the predecessor or successor of the node you want to insert)

sfussenegger 2009-10-20 09:30:57

'your effectively doing an insertion sort which has a best-case-performance of O(n)' - if the list is kept ordered binary search may be used for finding insertion index and insertion complexity is O(log n) then.

denis.zhdanov 2009-10-20 09:37:59

A binary search with a complexity of O(log n) is only possible if the complexity for random access to an indexed element is O(1), which is not the case for a linked list.

jarnbjo 2009-10-20 09:50:55

The author provided us with information that he uses dedicated HashMap for indexed access to the list elements which allows to have O(1) complexity for random element access.

denis.zhdanov 2009-10-20 10:00:30

If the author is talking about a `java.util.LinkedList` (which I suppose he is), there is no way to access elements randomly in O(1)

sfussenegger 2009-10-20 10:53:01

Did you check the initial message? 'i need to insert into a very large LinkedList, whose elements i hold in a fast-access HashMap.'

denis.zhdanov 2009-10-20 11:15:07

I did read the message. But the term 'elements' is ambiguous. I assumed elements being values of the list - mainly as it isn't possible to access the nodes (`LinkedList.Entry<E>` - where the value is stored as the field `E element` btw) of a LinkedList. I didn't expect it a custom implementation of a linked list - if it is, it shouldn't be called LinkedList to avoid confusion. But back to the main problem: If it's possible to access (randomly) *and* insert nodes in O(1), it would be possible to do an insertion sort in O(log n) as you mentioned.

sfussenegger 2009-10-20 12:09:22

Ok, see your point now, fair enough.

denis.zhdanov 2009-10-20 12:52:08

hey, that's a good idea! thanks!

Asaf 2009-10-20 13:30:00

Use a TreeSet or TreeMap. Inserts are O(log(n)) but remember that means LOG. So if you have 4 billion entries the runtime is O(32). If you have 2⁶⁴ entries, then an insert takes O(64), so it's not really a big deal.

Chad Okere 2009-10-20 10:20:58

When you say that you must keep your list in order - but that it is not the natural order of the keys, I hear you saying that you must preserve insertion order.

But then I don't know why LinkedHashMap doesn't meet your requirements.

Can you explain what LinkedHashMap fails to do?

CPerkins 2009-10-20 10:58:36

The problem seems to be that you don't have good access to the list. So you can't use the hashmap to jump to the list node and then insert an element after that node.

starblue 2009-10-20 15:20:13

Two questions: 1) Is it insertion order you need to preserve? 2) Why do you say that about LinkedHashMap? I'll test and post a certain response later, but from the docs, LinkedHashMap _is_ a hash map, but one which uses original insertion order as the order for iteration.

CPerkins 2009-10-21 10:44:47

ansaurus

tags:

views:

answers:

Which Java collection's Linked list adds in O(1) when given an element?

related questions