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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
In this post we will learn different types of Android Layout and some basics of an Android App.
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

726 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