[2 days left] What’s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now


Choosing an appropriate data structure

Posted on 2004-08-16
Medium Priority
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
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

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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

LVL 45

Accepted Solution

sunnycoder earned 1500 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

What’s Wrong with Your Cloud Strategy ?

Even as many CIOs are embracing a cloud-first strategy, the reality is that moving to the cloud is a lengthy process and the end-state is likely to be a blend of multiple clouds—public and private. Learn why multicloud solutions matter in this webinar by Nimble Storage.

Question has a verified solution.

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

In this post we will learn different types of Android Layout and some basics of an Android App.
This article will show how Aten was able to supply easy management and control for Artear's video walls and wide range display configurations of their newsroom.
Six Sigma Control Plans

649 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