Data Structure for a particular problem??

views:

answers:

+2 Q:

Data Structure for a particular problem??

Hi,

Which data structure can perform insertion, deletion and searching operation in O(1) time in the worst case?

We may assume the set of elements are integers drawn from a finite set 1,2,...,n, and initialization can take O(n) time.

I can only think of implementing a hash table.

Implementing it with Trees will not give O(1) time complexity for any of the operation. Or is it possible??

Kindly share your views on this, or any other data structure apart from these..

Thanks..

+3 A:

Although this sounds like homework, given enough memory you can just use an array. Access to any one element will be O(1). If you use each cell to keep the count of how many integers of that type have been encountered insertion will also be O(1). Searching will be O(1) because it would require indexing the array at that index and seeing the count. This is basically how radix sort works.

R0MANARMY 2010-05-23 05:05:26

i love it! This has to be the worlds simplest hashtable implementation i have ever read. Sure you sacrifice a little generality but look at the gains in simplicity of implementation!! +1

luke 2010-05-23 05:12:57

Well Its not an homework,, but yaa i am trying to work out some problems of Algorithms on my own i.e. personal interest, and try to seek as much experiences as possible through this forum.. This forum rocks! and extremely experienced guys are there to solve one's queries.. Thanks a lot.. +1..

AGeek 2010-05-23 05:18:50

@ AGeek: In that case you might also like this link http://kevinrodrigues.com/blog/2010/02/06/can-you-sort-10-million-numbers-using-1mb-of-memory/

R0MANARMY 2010-05-23 05:38:53

It's not a hashtable - it's a bitmap (or if the same value can be inserted multiple times, a counting bitmap, or simply an array).

Nick Johnson 2010-05-24 01:07:49

Depending on the range of elements an array might do but for a lot of data you want a hashtable. It will give you O(1) amortized operations.

D'Nabre 2010-05-23 08:39:42

ansaurus

tags:

views:

answers:

Data Structure for a particular problem??

related questions