---

---

Prerequisites:
Before you get into data structures and algorithms you should have basic prior knowledge in C language, C++ or any other programming languages along with the topics like loops, functions, arrays, pointers, recursions and structures.

What will we learn in this Tutorial?

1. Learn various codes based on Data Structures and their Algorithms and use them in practical applications.

2. Increase your programming skills on Data Structures.

3. Implementation of Data Structures and Algorithms using C Language.

4. Topics to be covered –

   1. Arrays Representation and Array Abstract Data Type

   2. Linked List

   3. Stack

   4. Queues

   5. Trees

   6. Binary Search Tree

   7. AVL Trees

   8. Hashing Technique.

   9. Graphs

Now we will start with a basic introduction to Data Structures and Algorithms.

Introduction to Data Structures and Algorithms

What is Data Structure?

Data Structure is a way of storing and organizing data in a system so that it can be used efficiently by the user. A data structure is a special layout for organizing and storing data. Basic Data Structure includes arrays, linked list, stack, queues, trees, graphs, etc.

Data Structure is classified into two types:

1. Linear Data Structure - In linear data structures, the elements are stored/ accessed in sequence one after the other. Example - linked list, stack and queues.

2. Non-linear Data structure - In non-linear data structures, the elements are stored/ accessed in non-linear or non-sequential order. Examples - trees and graphs.

What is an Algorithm?

An Algorithm is defined as a step-by-step instruction to solve a given problem. To analyze a given algorithm we need to know which algorithm takes less time and which algorithm takes a long time. Depending on this there are two types of analysis:

1. Time complexity - The amount of time required by an algorithm for its execution is known as time complexity. Time complexity is mainly classified into three types:

a.Best Case - The algorithm which takes least time for its execution.

b.Worst Case - The algorithm which takes a long time for its execution.

c. Average Case - The algorithm which takes average time for its execution.

2. Space Complexity - The space Complexity of an algorithm is defined as the total space taken by the algorithm in the memory. Space complexity includes both Auxiliary space (temporary space used by algorithm) and space used by input.

Rules for calculating time complexity:
1. Time taken by the for loop is considered by the statements inside the for loop.

Ex:-
for (i=0; i<n ;i++)                    -------------(n+1)
x = x + i;                     ------------ n
__________
2n+1
Time complexity=O (n)

2.     Time taken by Nested for loop is the product of the sizes of all loops.
Ex:-
for (i=0; i<n; i++) {                                               ---------------- (n+1)
 for (j=0; j<n; j++)           {                          ---------------- n(n+1)

C[i][j]=A[i][j]+B[i][j];                   ------------- (n*n)
}}                                             
Time complexity=O (n²)

Abstract Data Types:
An abstract data type (ADT) is a set of operations that specifies what is to be and its implementation details are hidden. The basic idea is that the implementation of these operations is written once in the program and any other part of the program that needs to perform an operation on the ADT can do so by calling the appropriate function.
Example: Insertion, deletion, merging and set operations on arrays are Abstract Data types.

Memory Segments:

1. Code Segment - Code segment includes all machine code of the compiled program..

2. Initialized Data Segment - Initialized data segment stores global, static and external variables that are initialized beforehand.

3. Uninitialized Data Segment - This Data segment is initialized to arithmetic 0 before the program starts executing.

4. Stack - Stack segment stores all of the local variables and is used for passing arguments to the functions by call by reference or call by the address which is to be executed after the function call is over.

5. Heap - Heap segment is a segment where memory is allocated dynamically. Here memory is allocated by using malloc and calloc functions.

 

 

---

---