Choosing an appropriate data structure

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)

Who is Participating?
sunnycoderConnect With a Mentor Commented:
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.
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!

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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

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.

arutAuthor Commented:
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
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
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.
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.