Introduction to Data Structures

What is data Structures?

In simple terms, "Data Structures stores data"

Where it is used?

It is used in computer science programming. In order to handle (store, manipulate,remove) the data involved in the programming problem effectively, we use data structures.

Some sample Data Structures: List,Stack,Queue,Tree,Graphs and many more.

Is data Structures important?

The common mantra in programming is "Algorithm+Data Structures = Program", So without data structures programming is just not possible.

More on Data Structures:

One aspect of data structures is that each data structure(ds) behaves very differently. I mean to say, that each ds (data structure) has its own way of storing, searching, manipulating,deleting the data. So one particular ds maybe suitable for particular program but another ds may not. So the right choice of ds for the programs you develop is an essential factor

Small Example to Illustrate Importance of Data Structures:

A simple program to print an integer in words.

#include <stdio.h>
#include <stdlib.h>

int main ( )
{
  char zero [ 5 ] = "zero" ;
  char one [ 5 ] = "one" ;
  char two [ 5 ] = "two" ;
  char three [ 10 ] = "three" ;
  char four [ 5 ] = "four" ;
  char five [ 5 ] = "five" ;
  char six [ 5 ] = "six" ;
  char seven [ 10 ]  = "seven" ;
  char eight [ 5 ] = "eight" ;
  char nine [ 5 ] = "nine" ;

  int number ;

  clrscr ( ) ;
  printf ( "Enter a number between 0 and 9...." ) ;
  scanf ( "%d" , &number ) ;

  switch ( number )
  {
      case 0 :
          printf ( "%s" , zero) ;
          break ;
      case 1 :
          printf ( "%s" , one ) ;
          break ;
      case 2 :
          printf ( "%s" , two ) ;
          break ;
      case 3 :
          printf ( "%s" , three ) ;
          break ;
      case 4 :
          printf ( "%s" , four ) ;
          break ;
      case 5 :
          printf ( "%s" , five ) ;
          break ;
      case 6 :
          printf ( "%s" , six ) ;
          break ;
      case 7 :
          printf ( "%s" , seven ) ;
          break ;
      case 8 :
          printf ( "%s" , eight ) ;
          break ;
      case 9 :
          printf ( "%s" , nine ) ;
          break ;
  }
  getch ( ) ;

  return 0 ;
}

The above simple program used one dimensional character array as the data structures. Now lets see another program which does the same thing but uses a two dimensional character array.

#include <stdio.h>
#include <stdlib.h>

int main ( )
{
  char nos [ 20 ] [ 10 ] = {          "Zero" ,
                   "One" ,
                   "Two" ,
                   "Three" ,
                   "Four" ,
                   "Five" ,
                   "Six" ,
                   "Seven" ,
                   "Eight" ,
                   "Nine" ,
                   "Ten" ,
                   "Eleven" ,
                   "Twelve" ,
                   "Thirteen" ,
                   "Fourteen" ,
                   "Fifteen" ,
                   "Sixteen" ,
                   "Seventeen" ,
                   "Eighteen" ,
                   "Nineteen"
                } ;
  int number ;

  clrscr ( ) ;
  printf ( "Enter a number between 0 and 19......." ) ;
  scanf ( "%d" , &number ) ;

  printf ( "%s\n" , nos [ number ] ) ;
  getch ( ) ;

  return 0 ;
}

Now do you see, how simple the program has become by a different choice of data structure.

Static and Dynamic data structures

Hope my simple introduction to data structures was informative to you. Now lets see the two methods by which an data structure can operate

Note: If you need a introduction on data structures please click here

Look, the major function of data structure is to handle data which are.

1. Store
2. Manipulate
3. Retrieve
4. Delete

Consider the first function , "Storing". (If you don't understand the other functions for the time being, just ignore it. No problems! :))

The data structure as to save the values which we pass into the memory. This is done mainly using assignment operator.

Example 1: int a = 4;

Here a is an integer data type(a data structure) which stores the value 4

Example 2: char str [ 10 ] = "String"

Here str is a character array data type which stores the value "String"
( In c Strings and character array means the same)

Consider this example

Example3: char *c;
c = (char *) malloc ( sizeof ( char ) * 10 ) ;
c = "String" ;


Here again c is of string data type that stores the value "String". but if you closely observe we use a malloc (memory allocation) function to allocate memory to our data structure c.

Note: If you don't understand the workings of malloc don't panic.It just allocates memory to the variable from the memory heap( memory where the variables are stored). Click here to learn more on malloc function

When we manually allocate memory as in example 3, then such a data structure is called a dynamic data structure. but if the memory is allocated automatically (by the runtime environment of the language) as in example 1 and example2 then the data structure is a static data structure.


Which type of data structures I should use???

The type of data structure you need to use depends on your application. If you know the number of data you need to store beforehand you can use static data structures. On the other hand if you know the size of data only at the runtime its better to use dynamic data structures but writing dynamic data structures is more complex than writing simple ones.