Choosing an appropriate data structure

Posted on 2004-08-16
Last Modified: 2010-04-17
Hi all,

I would like to know the criteria for choosing a particular abstract data type for e.g linked list, tree, hash table.

How can one determine which data structure is the best
for an application design ?
(design considerations)

Question by:arut

Expert Comment

ID: 11807911
Well, there are a few questions you can ask yourself (this is by no means a complete list).

If accessing speed is the key (ie, time to find a specif element), then a tree would probably be best.  The downside to trees is they incurr a performance hit when adding elements, as you must navigate the tree.  You can also look into self-balancing trees, which are even faster at searching, but even slower at adding.

If you need to be able to loop through ALL your elements regularly, then a linked list is best.  You can change the size of the list on the fly, you can add elements in the middle of the list, and you can even make it backward-searchable.  The downside is that they are very inefficient at searching for individual elements, as you basically have to loop through ALL your elements until you find the right one.  

As for hashtables, they are mainly used when you have a large number of key-value pairs, like a dictionary.  They have an efficient means of storing your keys for reasonably fast searches.  These are the best when you need to retrieve specific elements which usually have a name associated with them.

Hope this helped!

LVL 45

Expert Comment

ID: 11807940
Hi arut,

Primary considerations are

- language(s) that you are using and the capabilities they offer

- the application ... if you need a parser you probably want a LIFO structure ... if you want this parser to handle infinitely long strings, you might prefer to have a data structure that can be expanded dynamically, like a malloced array or linked list ...

If you need to insert randomly in the data, linked list may not be the best choice ... If you need range searches more frequently, linked list might be a good idea ... If you need both then you may consider indexing the data ... all depends on data and application

- future expansion and scalability ... you may find one data structure offering better scalability for an application as compared to another ... e.g. linked list of records in a commercial database offers very little scalability


Author Comment

ID: 11808908
Lets assume I want to implement a multicast routing table which has an entry like :    3         4
.    6         7

and I want to quickly lookup the entries.

In such a scenario what should be my design choice
Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

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.

LVL 45

Accepted Solution

sunnycoder earned 500 total points
ID: 11808938
routing tables have different arrangement of data ... These are more or less variations of trees with some optimizations doe for space and/or search time ... Different data structures are used in different types of routers as they are expected to operate at different speed and handle different volumes of route information

download this thesis, it has some invaluable information which will help you decide your data structures and give you a good insight on the kind of optimizations and approaches used.

Expert Comment

ID: 11809933
also keep in mind that dynamic allocation in non-managed memory is relativly expensive, as hardware developed, and memories are now much faster is is cheaper to simply scale by 2/halve a static structure (rewrite whole to new when needed, with a large mem margin) than alloc/free needed mem in a place/time of entry first/last usage

Expert Comment

ID: 11813549
It depends very much on the data size. Sometimes the "slowest" technique can actually be the fastest because the data set is very small.

When I need extremely fast lookup speeds I usually choose between a sorted vector (a sorted array of consecutively stored elements) or a hash table.

A binary search is extremely fast and gets faster as the data grows. For a binary search, the search time is O(log2 N).

Here is a chart that shows the maximum number of comparisons needed for some array sizes:

Items: max comparisons needed

         128: 7 comparisons max
       1024: 10 comparisons max
16777216: 24 comparisons max

Binary search provides extremely fast lookup speed, but inserting an element in a binary search can be slow because the array must be kept in sorted order. An insertion near the top requires pushing all the subsequent elements forward. This can be minimized by using an array of pointers for the lookup array.

The other choice is a hash table. You can make your searches faster (as fast as O(1), instant) by using a larger hash table. You can save memory (and slow the searches) by using a smaller hash table.

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

Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …

861 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