Post
Ask Question

Data Structure - Part One

What is Data Structure?

 
In one word, it is a data organizer.
 
Just imagine your room as computer memory and the things as  data.
 
You use shelves, cupboards, kitchen organizers etc. to organize different things in your room so that you can access your things easily. Without organization there will be a huge mess of things lying on floor. It's the same thing with a computer and its memory.
 
 
 
Some organizing system (structure) is made for specific data, some of them are multi-functional.
 

Algorithm

 
An algorithm is a finite set of instructions or logic, written in order, to accomplish a certain predefined task. As per the above example, to organize things in our house, we have to put them into their place. But with a computer of course we want some logic which works automatically to handle huge sets of data and memory.
 
Array
  • An array is a collection of items stored at contiguous memory locations.
  • The idea is to store multiple items of the same type together
That’s it.
 
These two statements are enough to define any structure as an array.
 
What is contiguous memory? (Very important concept)
 
Contiguous memory = sequential memory
 

 
Computer memory is divided into chunk of partitions. Whenever you define any object in your program you must remember you are actually allocating memory to store data.
 
Like you require a home to live, in the same way variables require memory to live
 
Eg. Int A, Float b It means you register part of memory for your variable ‘A’ and variable ‘B’.
 
As per the above example, Diagram 1 is Contiguous memory and Diagram 2 is non-Contiguous memory.
 
If you declare array of size 6, it will search for continuous 6 unit of memory, which it will get in diagram 1. Even though diagram 2 has 6 unit of blocks it will not assigned to array since it is not sequential.
 
You can’t change the size; i.e. once you have declared the array you can’t change its size because of static memory allocated to it.
 

Traversing

 
In a traversing operation of an array, each element of an array is accessed exactly once for processing. This is also called visiting of an array.
 
Program 1 ( Simple array traverse and print number).
 
Take a deep breath and now start thinking with me.
 
I need variable to hold my array with a specific size. Let's declare it first.
  1. int arr[5]={10, 0, 20, 0, 30}; //creating and initializing array   
Now I want to iterate through an array. Of course I need a loop.
  1. //traversing array  
  2. for (int i = 0; i < 5; i++)  
  3. { .. }   
Now I want to access each element of that array.
  1. arr[i]  
Put everything together,
  1. #include <iostream>  
  2.   
  3. using namespace std;  
  4. int main() {  
  5.     int arr[5] = {  
  6.         10,  
  7.         0,  
  8.         20,  
  9.         0,  
  10.         30  
  11.     };  
  12.     for (int i = 0; i < 5; i++) {  
  13.         cout << arr[i] << "\n";  
  14.     }  
  15. }  
I have written this program in C++, but you can choose any language.
 
I only wanted to show how to think while writing program.
 
Program 2 (Insert element at given position).
 
When you are writing program for array, keep these things in mind,
  1. You will require for loop to iterate
  2. You need to access Position of array i.e A[0]
  3. You need to play with that position
e.g to shift element at index 0 to index 1 , A[0+1] = a[0]
Data Structure
 
Insert integer 20 at index position 2
 
Start thinking with me
 
I need to create array ‘MyArray’ of size 5 and insert above elements so that I can write a program.
  1. int MyArray[5]={5,10,12,14};   
To insert element at index 2, I need to shift elements by one position ahead; n will be last index of array; i.e 4. So the data between index 4 to index 2 has to be touched. So my loop will be
  1. for (i = n; i >= pos; i--) // pos = index 2 i.e( for(i=4,4>=2,i--))   
Now think and visualize, my loop is running.
  1. MyArray [4] = MyArray [3] // Copy the element at index 3 to index 4  
  2. MyArray[3] = MyArray[2]// Copy the element at index 2 into index 3  
  3. i.e in generalized way, MyArray[i]= MyArray[i-1]  
  4. // shift elements forward  
  5. for (i = n; i >= pos; i--)  
  6. MyArray [i] = MyArray [i - 1];   
Now index 2 is empty, I will add my data to it.. wohhh
 
MyArray[pos]=20.
 
With these basic steps and visualization, you can play with one dimensional array. It is really fun to do. You can rotate left or right with same steps.
 
Logic at line MyArray [i] = MyArray [i - 1]; will be differe according to you need
 
Program 3 - Merge two Array
 
Array 1 (of size 5) , Array 2 (of size 3)
 
Data Structure
 
Steps,
  • I need to merge two arrays so my Result array should be of size
    1. ResultArraySize = ‘ArraySize1’ + ‘ArraySize2’  
  • I will copy my ‘Array1’ into Result array without thinking further, let’s do it.
    1. for(i=0; i<size1; i++)  
    2. {  
    3. Result[i]=arr1[i];  
    4. }  
  • Now third step is interesting
You will require 2 iterations.
 
First, to iterate your 2nd array (ArraySize2)
 
Second, to iterate positions of result array so that you can insert elements.
  1. (Array Size 1 to Result ArraySize)  
  2. for(i=0, k=Array Size1; k<Result Array && i< Array Size2; i++, k++)  
  3. {  
  4. Result Array[k]=Array2[i];  
  5. }  
You are done with your core logic.


Similar Articles