Selecting a Data Structure

How can we select the data structure needed to solve a problem? You have already studied where to use array and the size of array and when and where to use the pointers etc. First of all, we have to analyze the problem to determine the resource constraints that a solution must meet. Suppose, the data is so huge i.e. in Gega bytes (GBs) while the disc space available with us is just 200 Mega bytes. This problem can not be solved with programming. Rather, we will have to buy a new disk.

Secondly, it is necessary to determine the basic operations that must be supported. Quantify the resource constraints for each operation. What does it mean? Suppose you have to insert the data in the computer or database and have to search some data item. Let’s take the example of telephone directory. Suppose there are eight million names in the directory. Now someone asks you about the name of some particular person. You want that this query should be answered as soon as possible. You may add or delete some data. It will be advisable to consider all these operations when you select some data structure.

Finally select the data structure that meets these requirements the maximum. Without, sufficient experience, it will be difficult to determine which one is the best data structure. We can get the help from internet, books or from someone whom you know for already getting the problems solved. We may find a similar example and try to use it. After this course, you will be familiar with the data structures and algorithms that are used to solve the computer problems.

Now you have selected the data structure. Suppose a programmer has inserted some data and wants to insert more data. This data will be inserted in the beginning of the existing data, or in the middle or in the end of the data. Let’s talk about the arrays and suppose you have an array of size hundred. Data may be lying in the first fifty locations of this array. Now you have to insert data in the start of this array. What will you do? You have to move the existing data (fifty locations) to the right so that we get space to insert new data. Other way round, there is no space in the start. Suppose you have to insert the data at 25th location. For this purpose, it is better to move the data from 26th to 50th locations; otherwise we will not have space to insert this new data at 25th location.

Now we have to see whether the data can be deleted or not. Suppose you are asked to delete the data at 27th position. How can we do that? What will we do with the space created at 27th position?

Thirdly, is all the data processed in some well-defined order or random access allowed? Again take the example of arrays. We can get the data from 0th position and traverse the array till its 50th position. Suppose we want to get the data, at first from 50th location and then from 13th. It means that there is no order or sequence. We want to access the data randomly. Random access means that we can’t say what will be the next position to get the data or insert the data.