Most efficient data structure?

First - I'm "cross-posting" this ques. under Pascal and Java - someone may want to flame me for doing so - but I can't find the "rules" on "cross-posting" for this site.

Anyway, regarding different data structures and the time it takes to search, insert, deleting, etc. - what is the most efficient structure and why?  I'm working on a project where I'm using a B-tree, but I'm just wondering if there is something better.  I have to be able to do both types of functions - retrieve data and manipulate data - search, and add/dele, etc.

Any ideas?  And can you explain your reasoning?

Also - if you take the time and give a thoughtful answer, please let me know what number of points should be awarded.  I'm still getting used to how everyone weighs their questions - I haven't found any logic.  I think it may be an easy answer for someone - I myself find it more difficult, otherwise I wouldn't be asking the question.  So if you can help me out, I'm willing to give you whatever points are really deserved.  

If you need more explanation as for the program/project let me know, but I'm really looking for what is the most efficient data structure.

Thanks - Dawn D.
Who is Participating?
MikeCappellaConnect With a Mentor Commented:
Comment changed to answer
Jan LouwerensSoftware EngineerCommented:
Usually, for cross-posting, you would just ask the question in one topic area, and then in other topic areas, just ask a 0 point question with a URL to the original question, and an explanation.

About your question, the most efficient data structure fully depends on what you intend to do with it. There is no best general data structure, otherwise that would be the only one ever used. You would have to describe what you want to do in order to get an acceptable answer.
Dawn - Unfortunately, given the generic nature of your question, there is no simple, one size fits all answer.

You need to consider the trade offs between "time" and "space".  While you may optimize the "time" of an algorithm (and the accompanying data strucutures required to implement the algorithm), this often negatively impacts the "space" used by the data structures.  And of course, the converse is true - optimizing for space, usually hurts performance.  And  still, both of these impact other users on multi-user systems, and other programs on your single-user PCs. If you use too much space, you end up thrashing a system in terms of memory.  And if you use too much of the CPU optimzing for time, you hog the CPU from other apps/users (although this is controlled somewhat in multi-user OSs such as Unix).

The first question that needs to be answered is what are you trying to optimize - time or space?  And then, which operations are the most crritical - add, delete, sort...?

Each algorithm and accompanying data-structure has its own time/space characteristics.  These are referred to as by the term O  (pronounced ohhh), and then followed by the time/space required relative to the unit; for example, a sort algorithm may be O(n^2) (pronounced: ohhh of n squared) time and O(n) space, indicating that it takes n-squared visits to each element on the average, and n units of space to maintain each element to sort the entire population of n elements.

B-Trees are excellent, as are AVL trees.  But certainly they are overkill or inefficient for very small datasets.  If the data set is very large, these algorithms make more sense.  So, you can also see that the size of your anticipated dataset must also be considered.

An additional consideration is how the data will be stored - is this data only going to be used in core (in RAM), or will the data be written out to the disk?  And if written out, how often?  Each operation?  During startup/shutdown of the program?

The Macintosh Filesystem for example is implemented using a B-Tree - it is very fast, but requires a large B-Tree database to be written to disk, which becomes corrupted at times, and needs to be rebuilt.

A basic Data Structures and Algorithms book will give you the O values for various algorithms and their operations (add, delete, sort, etc.).

Does this help?
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.