Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions

Most efficient data structure?

Posted on 2000-03-27
Last Modified: 2010-04-16
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.
Question by:jrddcd
  • 2

Expert Comment

by:Jan Louwerens
ID: 2662628
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.

Expert Comment

ID: 2662651
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?

Accepted Solution

MikeCappella earned 50 total points
ID: 2665153
Comment changed to answer

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Controlled Assessment GCSE - desperate help needed 4 98
Beginner to Unreal Engine 4 5 94
ejb wildfly example 2 16
Help Required 2 39
I know it’s not a new topic to discuss and it has lots of online contents already available over the net. But Then I thought it would be useful to this site’s visitors and can have online repository on vim most commonly used commands. This post h…
Today, the web development industry is booming, and many people consider it to be their vocation. The question you may be asking yourself is – how do I become a web developer?
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

791 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question