CODEWITHSUNDEEP
javadata-structurescollections
Jeremy
Jeremy

Reputation: 3809

Most efficient way to keep a collection in Java?

Currently, I have a LinkedList which stores a custom Node class. The Nodes are currently removed in order and evaluated, which generally adds more Nodes back into the LinkedList, treating it like a Queue.

But in reality I don't care about maintaining the order of the Nodes because the order they are being added or removed doesn't matter. You can remove the 1st, 54th, or 1032nd Node from the List, it doesn't matter. All that matters is the Nodes are being processed quickly, which means one is removed (at random), mutated, then added back along with several variations of it (once again the order doesn't matter).

Since I haven't been able to find a Java Bag implementation, what is the most efficient way to maintain this type of collection ?

PS Out of laziness I have avoid using arrays because the collection of nodes could theoretically range from 1 Node to 3^64 Nodes in size, though it's more likely to stay under a million.

Upvotes: 1

Views: 830

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

The Java HashSet or TreeSet types might be good here, since they represent unordered collections of elements that support quick insertion and deletion of elements. That said, you can't possibly hold 364 values in memory, since that's appromately 3.4336838 × 1030, a number vastly bigger than any amount of RAM that I know of can hold.

EDIT: Based on the described use case (support efficient insertion and removal of random elements), you might want to adopt the approach described in this older question for building a data structure that does just that. Intuitively, you would use an ArrayList, then remove elements by swapping them to the end of the ArrayList and removing them. This gives O(1) insertion and O(1) removal with extremely low overhead.

Hope this helps!

Upvotes: 1

Related Questions