Data Structures and Algorithms

Data Structure can be defined as the group of data elements which provides an efficient way of storing and organising data in the computer so that it can be used efficiently. Some examples of Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are widely used in almost every aspect of Computer Science i.e. Operating System, Compiler Design, Artifical intelligence, Graphics and many more.

Data Structures are the main part of many computer science algorithms as they enable the programmers to handle the data in an efficient way. It plays a vital role in enhancing the performance of a software or a program as the main function of the software is to store and retrieve the user's data as fast as possible.

Data Structure Classification

• Primitive Data Structure
• Non Primitive Data Structure
  • Linear
    • Static
      • Array
    • Dynamic
      • Linked list
      • Stack
      • Queue
  • Non Linear
    • Tree
    • Graph

Linear Data Structures: A data structure is called linear if all of its elements are arranged in the linear order. In linear data structures, the elements are stored in non-hierarchical way where each element has the successors and predecessors except the first and last element.

• Types of Linear Data Structures are given below:

Arrays: An array is a collection of similar type of data items and each data item is called an element of the array. The data type of the element may be any valid data type like char, int, float or double.

The elements of array share the same variable name but each one carries a different index number known as subscript. The array can be one dimensional, two dimensional or multidimensional.

The individual elements of the array age are:

age[0], age[1], age[2], age[3],......... age[98], age[99].

Linked List: Linked list is a linear data structure which is used to maintain a list in the memory. It can be seen as the collection of nodes stored at non-contiguous memory locations. Each node of the list contains a pointer to its adjacent node.

Stack: Stack is a linear list in which insertion and deletions are allowed only at one end, called top.

A stack is an abstract data type (ADT), can be implemented in most of the programming languages. It is named as stack because it behaves like a real-world stack, for example: - piles of plates or deck of cards etc.

Queue: Queue is a linear list in which elements can be inserted only at one end called rear and deleted only at the other end called front.

It is an abstract data structure, similar to stack. Queue is opened at both end therefore it follows First-In-First-Out (FIFO) methodology for storing the data items.

Non Linear Data Structures : This data structure does not form a sequence i.e. each item or element is connected with two or more other items in a non-linear arrangement. The data elements are not arranged in sequential structure.

• Types of Non Linear Data Structures are given below:

Trees: Trees are multilevel data structures with a hierarchical relationship among its elements known as nodes. The bottommost nodes in the herierchy are called leaf node while the topmost node is called root node. Each node contains pointers to point adjacent nodes.

Tree data structure is based on the parent-child relationship among the nodes. Each node in the tree can have more than one children except the leaf nodes whereas each node can have atmost one parent except the root node. Trees can be classfied into many categories which will be discussed later in this tutorial.

Graphs: Graphs can be defined as the pictorial representation of the set of elements (represented by vertices) connected by the links known as edges. A graph is different from tree in the sense that a graph can have cycle while the tree can not have the one.

• Data can be organized in many different ways. The logical or mathematical model of a organization of data is called a Data Structure
•  A data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data,

NEEDS OF DATA  STRUCTURE--

• The computer are electronic data processing machine. In order to solve particular problem we need to know:

             1-- How to represent data in computers?

             2-- How to access them?

             3-- What are the steps we need to perform to get the needed output

     These task can be achieved with the knowledge of data structure and algorithm.

CLASSIFICATION OF DATA STRUCTURE---

• Data structure are classified into PRIMITIVE and NON-PRIMITIVE data structures

               1-> PRIMITIVE DATA STRUCTURE  

                      --   These are the fundamentals standards data types.

                      --  These are used to represent single values .

                      example- int, float, char, double

               2->  NON-PRIMITIVE DATA STRUCTURE

                      -- These are derived from primitive data types

                      --  Used to store group of values

                      example- arrays, stacks, queues, trees etc.

• Based on the structures and arrangement of data, non-primitive data structures are further classified into linear and non-linear.                   

            LINEAR DATA STRUCTURE--

           >  A data structure is said to be linear if its elements form a sequence or a linear list

           > In linear data structures, the data is arranged in a linear fashion although the way they are stored in memory need not be sequential

            example- Arrays, linked list etc

            NON-PRIMITIVE DATA STRUCTURE--

           > A data structure is said to be a non-linear if the data is not arranged in sequence. 

           > The insertion and deletion of data is therefore not possible in a linear fashion

           example- trees, graphs

DATA STRUCTURE------

• The logical or mathematical model of an organization of data is called a Data Structure.

DATA STRUCTURE OPERATIONS----

===>  The data appearing in our data structures are processed by means of certain operations. In fact, the particular data structure that one chooses for a given situation depends largely on the                      frequency with which specific operations are performed.

1. Traversing
2.  Searching
3. Inserting
4. Deleting
5. Sorting
6. Merging

TRAVERSING----

>>  Accessing each record exactly once so that certain items in the record maybe processed. (This accessing and processing is sometimes called "visiting" the record)

SEARCHING----

>>  Finding the location of the record with a given key value, or finding the locations of all records which satisfy one or more conditions.

INSERTING----

>>  Adding a new record to the structure

DELETING ----

>> : Removing a record from the structure

SORTING----

>> Arranging the records in some logical order

MERGING----

>> Combining the records of two different sorted files into a single sorted file

DYNAMIC MEMORY ALLOCATION----

•  It refers to performing manual management for dynamic memory allocation using standard library functions such as malloc, realoc, calloc and free.
• The size of array initially declared can be sometimes insufficient or sometimes more than required but dynamic memory allocation allows a program to obtain more memory space, while running or to release space when not required.

FUNCTIONS OF DYNAMIC MEMORY ALLOCATION----

• There are four standard library functions under “stdlib.h” for dynamic memory allocation. 

1. malloc()
2. calloc()
3. realloc()
4. free()             

=>   malloc() – It allocates requested size of bytes and returns a pointer first byte of allocated space.

                      Syntax : ptr=(data_type *)malloc(bysize);

                      Ex : (int*)malloc(100*sizeof(int)) 

=>   calloc() – Allocates spaces for array elements, initializes to zero and then returns a pointer to memory.

                      Syntax : ptr=(data_type*)calloc(n,element_size);

                      Ex : ptr=(float*)calloc(25,sizeof(float))

=>   realloc() – Changes the size of the previously allocated space according to the requirement.

                      Syntax : ptr=realloc(ptr,newsize);

=>   free() – It deallocates the previously allocated space.

                     Syntax – free(ptr);

==> One Dimensional Array---

               Declaration::

                      Syntax: data_type array_name[array_size];

                                   where, data_type can be int, float or char.

                                   array_name is the name of the array.

                                   array_size indicates number of elements in the array.

                                   For ex: int age[5];

             Initialization::

                          Syntax: data_type array_name[array_size]={v1,v2,v3};

                                       where, v1, v2, v3 are the values

                                       For ex: int age[5]={2,4,34,25,18};

==> Two Dimensional Array----

             Declaration::

                            Syntax: data_type array_name[array_size][array_size];

                                          where, first index shows the row number of the element and

                                                         second index shows the coulmn number of the element

            Initialisation::

                             Syntax: data_type array_name[array_size][array_size]={V1,V2,V3,.....Vn};

                                           where, V1, V2, V3,......,Vn are the values

                             For ex: int matrix[2][3]={2,4,56,3,6};

==> POINTERS--

• A pointer is a variable which contains the address in memory of another variable.
• Pointers are the variables that are used to store the location of value present in the memory

       Declaration :

                             data_type *variable_name;

                              Ex : int *a;

                  Ex :

                         #include int main()

                         {

                            int var = 20;

                            int *ip;

                            ip=&var;

                            printf(“Address of variable is %x ”, &var);

                            printf(“Address stored in ip variable is :%x”,ip);

                            printf(“value of *ip variable : %d”, *ip);

                            return 0;

                         }  

==> STRINGS--

• , array of character are called strings
•  a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable

==>  STRUCTURE

• It is defined as group of dissimilar or hetrogenous data items, where item can be of different data type

==> POLYNOMIAL

• A  polynomial is a sum of terms where each term has a form of  exponent, variable and co-efficient

==> Stacks

• : A stack is linear Data Sturcture in which items are added (pushed, inserted) and removed(pop, deleted) from one end called top.
• A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle.
• . In the stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack.
• A stack is a limited access data structure - elements can be added and removed from the stack only at the top. Push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.

==> Stack Operations--

       1. Stack full

       2. Stack empty

       3. Push

       4. Pop

       5. Display

       6. Top of stack

==> Stacks--

• A stack is linear Data Sturcture in which items are added (pushed, inserted) and removed(pop, deleted) from one end called top.
• A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack

==> Applications of Stack----

• The simplest application of a stack is to reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack
• Another application is an "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
• Evaluation of Expressions
• Language processing::

1. space for parameters and local variables is created internally using a stack.
2. compiler's syntax check for matching braces is implemented by using stack.
3. support for recursion 

==> Infix expression---

• The expression in which operator is placed in between operands
• Ex. a+b

==> Polish Notation---

•  - names after the Polish Mathematician Jan Lukasiewiez, refers to the expression in which the operator is placed before the operands also called prefix expression.
• Ex. +ab

==> Reverse Polish Notation---

• refers to the expression in which the operator is placed after the operands also called postfix expression or suffix Expression.
• Ex. ab+ 

==> Evaluation of Postfix expression---

• In high level languages, infix notation cannot be used to evaluate expressions
• Instead compilers typically use a parenthesis free notation to evaluate the expression
• A common technique is to convert a infix notation into postfix notation, then evaluating it.
• Before knowing the function that translates infix expression to postfix expression, we need to know how to evaluate the postfix expression.                                                                                                         45+ will be evaluate as 4+5=9
• To evaluate an expression we make single left to right scan (read) of it. We place the operands on a stack until we find an operator. We then remove, from the stack, correct number of operands for the operator, perform operation, and place the result back on the stack. We continue until we reach the end of the expression. We remove the result top of the stack.

==> Fibonacci Sequence---

        Fibonacci series 0,1,1,2,3,5,8,13,21,…..

1. if n=0 or n=1, then Fn =n
2. if n>1 then Fn=Fn-1+Fn-2

         fib(n)

        {

         if(n==0)

         return 0;

         if(n==1) return 1;

         else

         return( fib(n-1)+fib(n-2));

          } 

==> Tower of Hanoi---

• Tower of Hanoi, is a mathematical puzzle which consists of three tower (pegs) and more than one rings;
• These rings are of different sizes and stacked upon in ascending order i.e. the smaller one sits over the larger one. There are other variations of puzzle where the number of disks increase, but the tower count remains the same.

==> Tower of Hanoi--

• Tower of Hanoi, is a mathematical puzzle which consists of three tower (pegs) and more than one rings
• These rings are of different sizes and stacked upon in ascending order i.e. the smaller one sits over the larger one. There are other variations of puzzle where the number of disks increase, but the tower count remains the same.

==>  Queue--

•  Queue is a first in first out FIFO linear data structure Queue is an important data structure for computer applications even.
• Queue is linear data structure in which deletion of element can take place only at one end called the front end and insertion can take place at the other end called the rear

==> Basic features of Queue--

1. Like Stack, Queue is also an ordered list of elements of similar data types.
2. Queue is a FIFO( First in First Out ) structure.
3. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

==> Queue--

• Queue is a first in first out FIFO linear data structure Queue is an important data structure for computer applications even.
• Queue is linear data structure in which deletion of element can take place only at one end called the front end and insertion can take place at the other end called the rear.

==> Applications of Queue--

• Queue, as the name suggests is used whenever we need to have any group of objects in an order in which the first one coming in, also gets out first while the others wait for there turn, like in the following scenarios : 

1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive, First come first served. 

==> Implementation of Queue--

• Queue can be implemented using an Array, Stack or Linked List.
• The easiest way of implementing a queue is by using an Array.
• Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of array from 0).
• As we add elements to the queue, the rear keeps on moving ahead, always pointing to the position where the next element will be inserted, while the front remains at the first index.
• When we remove element from Queue, we can follow two possible approaches (mentioned [A] and [B] in above diagram).
• In [A] approach, we remove the element at front position, and then one by one move all the other elements on position forward.
• In approach [B] we remove the element from front position and then move front to the next position.
• In approach [A] there is an overhead of shifting the elements one position forward every time we remove the first element.
• In approach [B] there is no such overhead, but whenever we move head one position ahead, after removal of first element, the size on Queue is reduced by one space each time.

==>  simple queue--

• A simple queue is the most basic queue. In this queue, the enqueue operation takes place at the rear, while the dequeue operation takes place at the front: Its applications are process scheduling, disk scheduling, memory management, IO buffer, pipes, call center phone systems, and interrupt handling
• Simple QUEUE of Characters (Array Implementation of Queue with maximum size MAX)

1. Insert an Element on to QUEUE
2. . Delete an Element from QUEUE
3. Demonstrate Overflow and Underflow situations on QUEUE
4. . Display the status of QUEUE
5. Exit 

==> Disadvantage Simple Queue--

• When the first element is serviced, the front is moved to next element. However, the position vacated is not available for further use. Thus, we may encounter a situation, wherein program shows that queue is full, while all the elements have been deleted are available but unusable, though empty. 

==> Algorithm for Enqueue operation using array--

        Step 1. start

        Step 2. if (front == (rear+1)%max)

                   Print error “circular queue overflow “

       Step 3. else { rear = (rear+1)%max

                   Q[rear] = element;

                  If (front == -1 ) f = 0;

                 }

       Step 4. stop

==> Algorithm for Dequeue operation using array--

        Step 1. start

        Step 2. if ((front == rear) && (rear == -1))

                   Print error “circular queue underflow “

       Step 3. else { element = Q[front]

                If (front == rear) front=rear = -1

              Else

             Front = (front + 1) % max

                   }

     Step 4. stop

==> Circular queue--

•  Circular queue is a linear data structure. It follows FIFO principle
•  In circular queue the last node is connected back to the first node to make a circle
•  In circular queue the last node is connected back to the first node to make a circle
• Both the front and the rear pointers points to the beginning of the array.
• It is also called as “Ring buffer”.

==> Linked List--

• List is a linear collection of data items.
• s. List can be implemented using arrays and linked lists.
• s. In arrays there is linear relationship between the data elements which is evident from the physical relationship of data in the memory.
• The address of any element in the array can easily be computed but, it is very difficult to insert and delete any element in an array
• Usually, a large block of memory is occupied by an array which may not be in use and it is difficult to increase the size of an array, if required.
• LINKED LIST is a linear data structure and it is very common data structure which consists of group of nodes in a sequence which is divided in two parts. Each node consists of its own data and the address of the next node and forms a chain. Linked Lists are used to create trees and graphs.

==> Advantages of Linked Lists--

1. They are a dynamic in nature which allocates the memory when required.
2.  Insertion and deletion operations can be easily implemented.
3.  Stacks and queues can be easily executed.
4.  Linked List reduces the access time. 

==> Disadvantages of Linked Lists--

1. The memory is wasted as pointers require extra memory for storage.
2.  No element can be accessed randomly; it has to access each node sequentially.
3.  Reverse Traversing is difficult in single linked list. 

==> LINKED LIST--

• Linked List is a linear data structure and it is very common data structure which consists of group of nodes in a sequence which is divided in two parts. Each node consists of its own data and the address of the next node and forms a chain.
• Linked Lists are used to create trees and graphs.

 ==> Types of Linked Lists--

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

==> Linked List Operations--

1. Node creation
2. Insertion
3. Deletion
4. Traversing & Displaying

==> ordered linked list --

•  a linked list is a linear collection of data elements whose order is not given by their physical placement in memory

==> Circular doubly linked list--

• Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node.
• Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contains the address of the first node of the list.

==> Types of Trees--

1. complete binary tree
2. Almost complete binary tree
3. Strictly Binary Tree:
4. Binary Search Tree
5. Binary Tree

Define binary search tree. Explain common operation of binary search tree ? 

==> Graph--

• Graph is a nonlinear data structure,it contains a set of points known as nodes(or vertices) and set of links known as edges(or Arcs) which connects the vertices

==>  hashing--

• Hashing is the process of transforming any given key or a string of characters into another value
• This is usually represented by a shorter, fixed-length value or key that represents and makes it easier to find or employ the original string.