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.
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.
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.
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).
Joined: Mar 22, 2005
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.
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
Joined: Feb 03, 2009
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.
subject: arraylist with O(log n) insertion/removal/search