Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

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

 
Ryan Atwood
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 42967
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ryan Atwood
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 42967
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10417
63
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ryan Atwood
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic