I want to design a data-structure for storing elements, which will be retrieved only once after insertion and will be deleted after that.
I can't use a stack or queue as the order of retrieval is not guaranteed.
[EDIT] - I would like to use contigous memory (I would prefer to avoid doing malloc every now and then) and also I would prefer searchability also.
A garden variety linked list would fit your requirement. But refining your requirements would produce better recommendations.
For example:
Probably either a hash table or some sort of tree. Since you're doing a lot of deleting, if you use a hash table, it'll (almost) need to be one that handles collisions by chaining.
Assuming the elements are all the same size, you probably also want to consider writing your own code to allocate the elements to make it easy to reuse the space for an element after it has been deleted.
Edit: IMO, you probably do not want a linked list. While a linked list makes the deletion itself constant speed, finding an element is linear, so overall speed is O(N + K) = O(N). For a hash table, the expected speed will be O(1), and for a tree O(lg N).
I think the choice of algorithm requires more information about how it's going to be used. From your comment that you want better than linear search, I'm assuming that the speed of search is important. Your comments on contiguous memory lead me to believe that you want to minimize memory consumption. I'd suggest that a self-balancing tree structure (Red-Black tree) might be appropriate. It would have amortized log(N) insert/delete allowing you to achieve both of the goals I outlined. If memory use is less of a problem, a hashtable would be more efficient for lookup. You can implement a bounded-size tree in contiguous memory -- though the actual elements themselves are not necessarily contiguous.
If, on the other hand, I knew that the order of insertion was random but that the order of retrieval was deterministic and ordered by key, then I might suggest a priority queue using a heap implementation.
Separate the storeage requirement from the datastructure.
You say you want contiguous memory - I assume then that you want to grab a chunk of memory and work entirely within that memory rather than allocating more fragments over time.
Now simplest case withing that is a queue implemented over ring-buffer within your memory chunk. I assume that you want something better, as you don't have fifo happening here.
So some form of balanced tree sounds like what you need. The choice probably depends on what patterns there are withing the arriving keys. Random? Ascending?
A wrinkle is to allocate memory from your chunk rather than using the normal heap allocator and that probably implies keeping a free list too.
It would be interesting to know why you value a contiguous block of memory.
Doubly linked list, obviously. What do you mean by "you want your memory to be contiguous"? No matter which data structure you use, it's only going to be contiguous till you delete one element, after which you'll have to pack the data up to preserve contiguity. And seriously, when you need to move half, on average, of your records after each deletion, it pretty much doesn't matter which data structure you use, you're screwed anyway. Just go with dynamic array.
Use a red-black tree with a memory pool for allocating items from a contiguous memory block. Sample implementations of red-black trees written in C are readily available. Most should be easily modified to support a custom memory allocator if they do not already provide that capability.
It sounds like you want that most ubiquitous of data structures - an array. In your case a dynamically allocated one, similar to that provided by the C++ std::vector class.
You can use a (doubly) linked list and still keep your memory contiguous.
Allocate a big block of memory to hold all your nodes and keep track of which nodes you have allocated for data storage.
You have several options for managing your preallocated memory.
One method is to use a queue or stack of available nodes, you can take a free node out, write your data and add it the linked list. When you are done with a node remove it from the linked list and put it back into the queue/stack.
Depending on your stack/queue implementation, this could amount to maintaining two linked lists. A little thought should yeild a design that is efficient and parsimonious with data structures and underlying code.