Introduction to Data Structure

Introduction:  Data structures are building blocks of a program. They are like pillars of a huge structure.  If a program is built using improper data structures, then the program may not work as expected always. It is very much important to use right data structure for a program.  Data structure enables a programmer to structure a program in such a way that the data are represented in real life. The data structure must be rich enough in structure to mirror the actual relationship of the data in the real world. And it must be simple enough that one can effectively process the data when necessary.

Definition: The logical and mathematical model of a particular organization of a data is known as data structure. In other words data structure is collection of data elements whose organization is represented by accessing operations that are used to store and retrieve the individual data element effectively.

1.      Primitive data structure:  The data structures which are predefine are known as primitive data structure. i.e. integer, float, char etc.

2.      Non-primitive data structure:  The data structure which is derived from primitive data structure is known as non-primitive data structure or composite data structure or abstract data type (ADT). It can be further classified in the following types:

                           I.          Classification based on memory allocation time:

                                                    i.     Static: for such type of data structure, the size and structure of memory locations are fixed at compile time.

                                                   ii.     Dynamic: for such memory allocation for the data will be done at run time. It can be expanded or shrieked as required during the program execution.

                         II.          Classification on the basis of relationship between data:

                                                    i.     Linear: a data structure is said to be linear if its elements form a sequence or a linear list. There are two basic ways of representing linear data structure in memory between elements as sequential memory location for example, array. Another way is to show the linear relationship between the elements by use of pointer or links. Linked list is example of such data structure.

                                                   ii.     Non-linear data structure: a data structure used to show non-sequential relationship such as hierarchical relationship. For example, tree and graph. Here, each node may contain more than one node.

                        III.          Classification on the basis of type of data:

                                                    i.     Homogeneous: this is the data structure in which all the elements or data are of the same type. For example, array.

                                                   ii.     Non-homogeneous: in such type of data structure all the elements or data may or may not be of same type. For example, structure.

Logical and control structure:  It is a mechanism by which we can control flow of any program. There are three types of logic or flow of controls.

1.      Sequential logic or sequential control (no condition –no loop): The statements are written in sequence in an algorithm or program and the statements are executed in sequence one after the other. Such structure is called sequential structure. In algorithm the sequence is maintained by numbering. In computer program the sequence is presented by the order in which the statements are written.

2.      Selection logic or conditional control (if…else): The selection logic uses number of conditions which are used for selection of one out of several options. The conditional statement falls into three types,

a.      Single alternate:

  if (condition)

Statements

                                             End if

If the condition is true then statements are executed otherwise these statements are skipped and control transferred to the next statement after the if structure.                                                         

b.     Double alternatives:

  if (condition)

Statements group 1

                              Else

                                             Statements group 2

                       End if

If the condition is true then statements group 1 are executed otherwise statements group 2 are executed.

c.      Multiple alternatives:

  if (condition)

Statements group 1

                              Else if(condition)

                                             Statement group 2

                                                            :

                                                            :

                              Else

                                             Statements group n

                       End if

The logic of this structure allows only one of the group of statements to be executed depending upon a condition.

3.      Iteration logic or repetitive control (loops): This type of control involves loops. Each type begins with repeat statement and is followed by group of statement called the body of the loop. There are two types of repeat statements as the following,

a.      Repeat for loop: This statement uses an index variable to control the loop. i.e.

Repeat for I=0,1,2 to n step 2

               Group of statements

Here, I is the index variable, 0 is initial value and n is the end value and the value of I will be incremented by 2 (step 2) in each step.

b.      Repeat While loop: This structure uses condition to control the loop. i.e.

Repeat while (condition)

        Group of statements

The loop continues until the condition becomes false. There must be some statements inside the loop which can ever make the condition false.

Time and space efficiency of algorithm:  This is the process of identifying the exact amount of time and space required by an algorithm. Analysis is to be done because complexity refers the rate at which the required time or storage grows as a function of the problem size. The absolute growth depends on the machine used to execute the program, the compiler used to construct the program and many other factors. But it is very difficult to calculate the exact time. So we must concentrate on the “proportionality” approach. This type of analysis is known as asymptotic analysis. Some examples of asymptotic analysis are Omega notation (tight bound), Theta notation (Lower bound) and big O notation (Upper bound). Let’s discuss the big O notation in detail.

The big O notation (Upper Bound):  here are some rules for big O notaion:

1.      f (n) = O(f(n)) for any function f. in other words every function is bounded by itself.

2.      a_kn^k  + a_k-1n^k-1 + ….+ a₁n + a₀ = O(n^k) for all k >=0 and for all a₀, a₁, …a_k belongs to R. means every polynomial of degree k can be bounded by the function n^k. Smaller order terms can be ignored in big O notation.

3.      Basis of logarithm can be ignored in big O notation.

4.      Any logarithmic function can be bounded by polynomial.

5.      Any polynomial function can be bounded by exponential function.

6.      Any exponential function can be bounded by factorial function.

Three Cases:

Best Case:  It is a measure of minimum time required by an algorithm of size ‘n’.

Average Case: It is a measure of average amount of time required by an algorithm of size ‘n’.

Worst case: It is a measure of maximum time required by an algorithm of size ‘n’.

Process of analysis: The process of analysis of algorithm (program) means to analyze each step of algorithm. It depends on the kinds of statements used in algorithm or program. Consider the following examples

Simple sequence of statements: The total time can be found by adding the times for all statements. Assume that each statement is for performing only simple operations the time for each simple statement is constant and total time is also constant: O(1).

1.      If-then-else statements: here either sequence will execute depending on the condition. The worst case time in this case is the slower of the two possibilities.

2.      Loop statement:  loop executes n times, so sequence is also execute n times. As we assume that a simple statement will take O (1) so total time for loop is n*O (1) means O(n).

3.      Nested for loop: each loop executes n times, so sequence is also execute n times for each loop. As we assume that a simple statement will take O (1) so total time for loop is n*O(1) means O(n) and O(n) for each loop. So if there are two nested loops it will take O(n) * O(n) = O(n²)

Space complexity (Efficiency):

·        It is very much important to analyze the amount of memory used by the program.

·        If the running time of algorithm is not good then it will take longer to execute. But if it takes more memory beyond the capacity of the machine then the program will not execute at all.

·        The space complexity of the computer program is the amount of memory required for its proper execution.

·        The important concept behind space required is that unlike time, space can be reused during the execution of program.

Time complexity (Efficiency):

·        It is very much important to calculate the amount of time the computer takes to execute the algorithm.