Efficient list data structure

I need a list-type data structure to implement in a project. Actually it doesn't necessary have to be some kind of list, but it has to be fast and I'm going to use to it to constantly insert/delete/retrieve data (other data structures) from it. I might insert something, search, insert again, delete, searc开发者_运维知识库h again and so on, so actions are sort of random.

I found skip-lists the fastest so far, what is there faster than that?

---

A great deal depends on your language of choice. C gives you the greatest control over your final data structure, and you will end up with one of the fastest implementations. With, of course, a very easy time shooting yourself in the foot. Rather badly. Python abstracts a lot of list data structure, and I find it is consistently fast, but I'm not stressing it too terribly either.

I would suggest a check of freshmeat for prebuilt C libraries that you can repurpose for your task. Perhaps wikipedia's page on skip lists will point you towards more: http://en.wikipedia.org/wiki/Skip_list

Data structures are a deep subject that requires a decent grounding in big O notation and exactly what it means when we talk about "speed" and "efficiency" or you will not be able to make an objective comparison. Finally, everything has trade offs. Pick a data structure that most closely models both your data, and how you intend to manipulate it. If you're tasks are rather random, step back into the design phase and ask your self how you can refine what happens before it gets to the data structure. That is, get your algorithm hammered out, and then pick a data structure to complement it.

---

A hashtable/hashmap/dictionary sounds like what you want. For example, dictionaries in Python.

---

You might look into the BTree