MODULE I

Array is a container which can hold a fix number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms. Following are the important terms to understand the concept of Array

//SAMPLE PROGRAME

#include 
main() {
	int Array[] = {1,3,5,7,8};
	int i = 0;   
	int n = 5;
	printf("The original array elements are :\n");
	
	for(i = 0; i <n; i++) {
		printf("Array_Index_value[%d] = %d \n", i, Array[i]);
	}
}
       
                                      
                                           
                                        

A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack

• A real-world stack allows operations at one end only
• LIFO data structure (Last-in-first-out)
• In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation.

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing

    //peek operation
    
    int peek() {
        return stack[top];
     }

     //check stack is full

     bool isfull() {
        if(top == MAXSIZE)
           return true;
        else
           return false;
     }

     //check stack is empty

     bool isempty() {
        if(top == -1)
           return true;
        else
           return false;
     }

     //stack PUSH

     void push(int data) {
        if(!isFull()) {
           top = top + 1;   
           stack[top] = data;
        } else {
           printf("Could not insert data, Stack is full.\n");
        }
     }

     //stack POP

     int pop(int data) {

        if(!isempty()) {
           data = stack[top];
           top = top - 1;   
           return data;
        } else {
           printf("Could not retrieve data, Stack is empty.\n");
        }
     }
           
                                          
                                               
                                            

Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.

As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and Structures. For the sake of simplicity, we shall implement queues using one-dimensional array.

    //peek operation
    
    int peek() {
        return queue[front];
     }

     //check queue is full

     bool isfull() {
        if(rear == MAXSIZE - 1)
           return true;
        else
           return false;
     }

     //check queue is empty

     bool isempty() {
        if(front < 0 || front > rear) 
           return true;
        else
           return false;
     }

     //Enqueue Operation

     int enqueue(int data){      
        if(isfull())
          return 0;
   
        rear = rear + 1;
        queue[rear] = data;
   
        return 1;
    }

     //Dequeue Operation

     int dequeue() {
        if(isempty())
           return 0;
     
        int data = queue[front];
        front = front + 1;
     
        return data;
     }
           
                                          
                                               
                                            

Tree represents the nodes connected by edges. We will discuss binary tree or binary search tree specifically.

Binary Tree is a special datastructure used for data storage purposes.
A binary tree has a special condition that each node can have a maximum of two children.
A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a sorted array and insertion or deletion operation are as fast as in linked list.

Binary Search tree exhibits a special behavior. A node's left child must have a value less than its parent's value and the node's right child must have a value greater than its parent value.

The basic operations that can be performed on a binary search tree data structure, are the following

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

• Linear data structure
• Elements are not stored at contiguous memory locations
• Elements in a linked list are linked using pointers
• Linked list consists of nodes
• Each node contains a data field and a reference(link) to the next node in the list
• Dynamic size
• Ease of insertion/deletion

• Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists efficiently with its default implementation
• Extra memory space for a pointer is required with each element of the list
• Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists

                    
    // A linked list node 
    struct Node { 
    int data; 
    struct Node* next; 
    }; 
                    

Simple Linked List

Item navigation is forward only

Doubly Linked List

Items can be navigated forward and backward

Circular Linked List

Last item contains link of the first element as next and the first element has a link to the last element as previous

• Insertion
• at beginning
• at end
• at a particular position
• Deletion
• Display
• Search
• Delete

Linked List Full Programme