aspose file tools*
The moose likes Performance and the fly likes arraylist with O(log n) insertion/removal/search Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "arraylist with O(log n) insertion/removal/search" Watch "arraylist with O(log n) insertion/removal/search" New topic
Author

arraylist with O(log n) insertion/removal/search

Ryan Atwood
Greenhorn

Joined: Feb 03, 2009
Posts: 15
Is there any such data structure that you guys are aware of that can store a list of numbers and perform insertion/removal/search in O(log n)? Or, even better, search in O(1)? Been pulling my hair to find a way to do this without pointers.

Thanks
Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3610
    
  60

There is probably no such List implementation. To perform efficient searches, you usually need to maintain some internal structure in your collection, which lists generally don't do.

If you look for O(1) lookup for integer numbers, you might be interested in a BitSet. If it does not suit your needs, then a HashSet (or another Set implementation) could be useful. However, none of these can store multiple copies of the same number, which is what a list would generally allow.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 41872
    
  63
Also, one of the main features of a List is its ordering - through integer indexes in the case of ArrayList, and through next/previous operations in the case of LinkedList. Do you need that? Otherwise a Set would be more appropriate, but then you can't have duplicate elements, as Martin mentioned.


Ping & DNS - my free Android networking tools app
Ryan Atwood
Greenhorn

Joined: Feb 03, 2009
Posts: 15
Yeah I guess I need one data structure that can let me traverse both ways? Integer indexing allows me to do a binary search to retrieve elements, and the ability to add/remove in O(lg n) can be made if that data structure is also doubly-linked. Right now, I'm using the ArrayList but any add/remove calls a System.arrayCopy which I believe is O(n).

Thanks,
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 41872
    
  63
Integer indexing allows me to do a binary search to retrieve elements

So you're not really using the index to retrieve specifically the, say, 6th element, but just as a means of implementing binary search? I'm beginning to think that java.util.TreeSet may be for you. From its javadocs: "This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains)." It's still a Set, though, so no duplicate elements.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7807
    
  21

Ryan Atwood wrote:Is there any such data structure that you guys are aware of that can store a list of numbers and perform insertion/removal/search in O(log n)? Or, even better, search in O(1)? Been pulling my hair to find a way to do this without pointers.

Well, there is a SkipList, but unfortunately you'll have to write it yourself if you want it to support duplicates, because the only implementation supplied in the standard libraries is as a Set or a Map. It's possible that somebody's already written one; otherwise it might be a fun exercise.
BTW - It works in O(log(n)) time for all the main operations, but possibly faster than TreeSet for iteration.


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Ryan Atwood
Greenhorn

Joined: Feb 03, 2009
Posts: 15
Skip List def. sounds like the way to go. I totally forgot about this one from my data structures class in college. Yes I do need to support duplicates in my list.

Thanks all
 
wood burning stoves
 
subject: arraylist with O(log n) insertion/removal/search