Reputation: 13

How to create my own efficient data structure?

I'm making a program in which I need to save objects that are not repeated and must be sorted into a data structure. Access, modification and removal of the object have to be very efficient.

First I thought about making a Map < String,Object > where the key is the name (attribute) of the object. But my teacher told me it was inefficient because I was duplicating content and I should have to create my own structure without using lists, vectors, .. or at least not directly, that is, I have to override the implementation.

But I do not know where to start and what is a good choice. What advice would you give me to access the object through its name in an efficient way?

Thanks!

Upvotes: 0

Answers (4)

hoopsnake

Reputation: 161

You may want a LinkedHashMap. This is an order-preserving hash map which can be iterated over.

Upvotes: 0

Ilia Lebedev

Reputation: 375

If i understand correctly, you want to map unique string names of objects to object references, and you want to be able to efficiently (faster than O(n)).

A sorted array allows O(log n) insertion, search, and linear-time deletion. A balanced BST allows O(log n) insertion, search, and deletion. A simple dictionary (HashTable) allows O(1) amortized insertion, search, and deletion, but the dictionary contents cannot be efficiently enumerated (Java allows dictionary contents to be enumerated in somewhat meaningless hash order). If you need to enumerate the objects in sorted order, a more efficient approach would be to maintain a sorted linked list of objects (by name) and use a dictionary to map names to liked list entries for O(1) amortized lookup.

As previously answered, TreeSet is a solid starting point using the Java library.

Upvotes: 0