Data Management concepts, Data types – primitive and non-primitive, Types of Data Structures- Linear &Non Linear Data Structures, implementation of some of the user defined data types such as – rational number, complex number, string, matrix etc.    

1. Types of Data structure

   1. Primitive 

      1. Integer

      2. Float

      3.  Character

      4. Boolean

      5. Byte

   2. Non-Primitive

      1. Linear Data Structure

         1. Static

            1. Array

         2. Dynamic

            1. Linked List

            2. Stack

            3. Queue

      2. Non-Linear Data Structure

         1. Tree

         2. Graph

1.    Primitive Data Structures

Primitive Data Structures are the Lineare data structures consisting of the numbers and the characters that come in-built into programs. These data structures can be manipulated or operated directly by machine-level instructions. Basic data types like Integer, Float, Character, and Boolean come under the Primitive Data Structures. These data types are also called Simple data types, as they contain characters that can't be divided further

Examples of Primitive Datatype

1.  Integer: Represents whole numbers, such as int in Java or C++.

2. Float/Double: Represents numbers with fractional parts. Float is for single precision, and Double is for double precision.

3. Character: Represents individual characters like 'A', 'b', '3', etc. It's usually denoted as char in languages like C, C++, and Java.

4.  Boolean: Represents truth values, typically true or false.

5. Byte: Represents a byte of data and is often used for raw binary data processing.

2.    Non-Primitive Data Structures

Non-Primitive Data Structures are those data structures derived from Primitive Data Structures.These data structures can't be manipulated or operated directly by machine-level instructions.The focus of these data structures is on forming a set of data elements that is either homogeneous (same data type) or heterogeneous (different data types).Based on the structure and arrangement of data, we can divide these data structures into two sub-categories -

1. Linear Data Structures

Data structure in which data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements, is called a linear data structure.
Example: Array, Stack, Queue, Linked List, etc.

1. Static Data Structure: Static data structure has a fixed memory size. It is easier to access the elements in a static data structure.
Example: array.

2.Dynamic Data Structure: In dynamic data structure, the size is not fixed. It can be randomly updated during the runtime which may be considered efficient concerning the memory (space) complexity of the code.
Example: Queue, Stack, etc.

2. Non- Linear Data Structures

Data structures where data elements are not placed sequentially or linearly are called non-linear data structures. In a non-linear data structure, we can’t traverse all the elements in a single run only.
Examples: Trees and Graphs.

 Examples of Nonprimitive Datatypes

       ·         Arrays: A collection of elements, typically of the same data type, arranged in a sequential order.

·         Linked Lists: Consists of nodes where each node contains data and a reference (or link) to the next node in the sequence.

·         Stacks: Follows the Last In First Out (LIFO) principle. Operations are performed at one end, called the top of the stack.

·         Queues: Operate on the First In First Out (FIFO) principle. Elements are added at the rear and removed from the front.

·         Trees: A hierarchical structure with a root value and subtrees of children, represented as a set of linked nodes.

·         Graphs: Consist of nodes (vertices) that are connected by edges. Useful for representing networks.

·         Hash Tables: Store data in an associative manner. Data is accessed via a unique key.

·         Sets: A collection of distinct elements with no particular order.

A stack is a data structure which is used to store data in a linear fashion. It is an Abstract data type (ADT) in which data is inserted and deleted from a single end which is the stack's top. It follows a Last in, First out (LIFO) principle i.e. the data which is inserted most recently in the stack will be deleted first from the stack

Basic Operations on Stacks

There are some basic operations that allow us to perform different actions on a stack.

1)      Push: Add an element to the top of a stack

Step 1: First, check whether or not the stack is full

Step 2: If the stack is complete, then exit

Step 3: If not, increment the top by one

Step 4: Insert a new element where the top is pointing

Step 5: Success

The algorithm of the push operation is:

Begin push: stack, item

If the stack is complete, return null

end if

top ->top+1;

stack[top] <- item

end

Program:

#include <stdio.h>

int MAXSIZE = 8;

int stack[8];

int top = -1;

/* Check if the stack is full*/

int isfull(){

   if(top == MAXSIZE)

      return 1;

   else

      return 0;

}

/* Function to insert into the stack */

int push(int data){

   if(!isfull()) {

      top = top + 1;

      stack[top] = data;

   } else {

      printf("Could not insert data, Stack is full.\n");

   }

}

/* Main function */

int main(){

   int i;

   push(44);

   push(10);

   push(62);

   push(123);

   push(15);

   printf("Stack Elements: \n");

   // print stack data

   for(i = 0; i < 8; i++) {

      printf("%d ", stack[i]);

   }

   return 0;

}

Output

Stack Elements:

44 10 62 123 15 0 0 0

2)      Pop: Remove an element from the top of a stack

Algorithm:

Step 1: First, check whether or not the stack is empty

Step 2: If the stack is empty, then exit

Step 3: If not, access the topmost data element

Step 4: Decrement the top by one

Step 5: Success

The following is the algorithm of the pop operation:

Begin pop: stack

If the stack is empty

 return null

end if

item -> stack[top] ;

Top -> top - 1;

Return item;

end

             Program

#include <stdio.h>

int MAXSIZE = 8;

int stack[8];

int top = -1;

/* Check if the stack is empty */

int isempty(){

   if(top == -1)

   return 1;

   else

   return 0;

}

/* Check if the stack is full*/

int isfull(){

   if(top == MAXSIZE)

   return 1;

   else

   return 0;

}

/* Function to delete from the stack */

int pop(){

   int data;

   if(!isempty()) {

   data = stack[top];

   top = top - 1;

   return data;

   } else {

   printf("Could not retrieve data, Stack is empty.\n");

   }

}

/* Function to insert into the stack */

int push(int data){

   if(!isfull()) {

   top = top + 1;

   stack[top] = data;

   } else {

   printf("Could not insert data, Stack is full.\n");

   }

}

/* Main function */

int main(){

   int i;

   push(44);

   push(10);

   push(62);

   push(123);

   push(15);

   printf("Stack Elements: \n");

   // print stack data

   for(i = 0; i < 8; i++) {

   printf("%d ", stack[i]);

   }

   /*printf("Element at top of the stack: %d\n" ,peek());*/

   printf("\nElements popped: \n");

   // print stack data

   while(!isempty()) {

   int data = pop();

   printf("%d ",data);

   }

   return 0;

}

Output

Stack Elements:

44 10 62 123 15 0 0 0

Elements popped:

15 123 62 10 44

3)      IsEmpty: Check if the stack is empty

Algorithm:

                             1. START

2. If the top value is -1, the stack is empty. Return 1.

3. Otherwise, return 0.

4. END

4)      IsFull: Check if the stack is full

Algorithm:

                             1. START

2. If the size of the stack is equal to the top position of the stack,  the stack is full.  Return 1.

3. Otherwise, return 0.

4. END

5)      Peek: Get the value of the top element without removing it.

Algorithm:

1. START

2. return the element at the top of the stack

3. END

begin to peek

return stack[top];

end

Program:

#include <stdio.h>

int MAXSIZE = 8;

int stack[8];

int top = -1;

/* Check if the stack is full */

int isfull(){

   if(top == MAXSIZE)

   return 1;

   else

   return 0;

}

/* Function to return the topmost element in the stack */

int peek(){

   return stack[top];

}

/* Function to insert into the stack */

int push(int data){

   if(!isfull()) {

   top = top + 1;

   stack[top] = data;

   } else {

   printf("Could not insert data, Stack is full.\n");

   }

}

/* Main function */

int main(){

   int i;

   push(44);

   push(10);

   push(62);

   push(123);

   push(15);

   printf("Stack Elements: \n");

   // print stack data

   for(i = 0; i < 8; i++) {

   printf("%d ", stack[i]);

   }

   printf("\nElement at top of the stack: %d\n" ,peek());

   return 0;

}

Output

Stack Elements:

44 10 62 123 15 0 0 0

Element at top of the stack: 15

Characteristics of  Stack:

·         The stack follows the LIFO order, which means that the last element added to the stack will be the first element to be removed.

·         A register that points to the top of the stack is known as the stack pointer. It is used to keep track of the current position of the top of the stack.

·         A stack is also characterized by its capacity, which is the maximum number of elements it can hold at any given time. If an attempt is made to push an element onto a full stack, a stack overflow error will occur.

Implementing Stack in C

In C, we can implement the Stack data structure using an array or a linked list.

Stack Program in C using Array

We will be using an array to implement a Static Stack (Bounded Stack) as arrays are static in C.
A Static Stack has a bounded capacity. A static stack is called to be in an Overflow State if it is full (no elements can be further pushed into it).

Implementation

// Implementing Static Stack using an Array in C

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

// N will be the capacity of the Static Stack

#define N 1000

// Initializing the top of the stack to be -1

int top = -1;

// Initializing the stack using an array

int stack[N];

// Function prototypes

void push();   // Push element to the top of the stack

int pop();     // Remove and return the top most element of the stack

int peek();    // Return the top most element of the stack

bool isEmpty(); // Check if the stack is in Underflow state or not

bool isFull(); // Check if the stack is in Overflow state or not

int main(){

printf("STATIC ARRAY (Total Capacity: %d)\n", N);

int choice;

while(1){

     printf("\nChoose any of the following options:\n");

     printf(" 0: Exit        1: Push        2: Pop        3: Peek\n");

     printf(" 4: Check if the stack is empty 5: Check if the stack is full\n\n");

     scanf("%d", &choice);

     switch(choice){

         case 0: exit(0);

         case 1: push(); break;

         case 2: pop(); break;

         case 3: peek(); break;

         case 4: isEmpty(); break;

         case 5: isFull(); break;

         default: printf("Please choose a correct option!");

     }

}

return 0;

}

void push(){

// Checking overflow state

if(top == N-1)

     printf("Overflow State: can't add more elements into the stack\n");

else{

     int x;

     printf("Enter element to be pushed into the stack: ");

     scanf("%d", &x);

     top+=1;

     stack[top] = x;

}

}

int pop(){

// Checking underflow state

if(top == -1)

     printf("Underflow State: Stack already empty, can't remove any element\n");

else{

     int x = stack[top];

     printf("Popping %d out of the stack\n", x);

     top-=1;

     return x;

}

return -1;

}

int peek(){

int x = stack[top];

printf("%d is the top most element of the stack\n", x);

return x;

}

bool isEmpty(){

if(top == -1){

     printf("Stack is empty: Underflow State\n");

     return true;

}

printf("Stack is not empty\n");

return false;

}

bool isFull(){

if(top == N-1){

     printf("Stack is full: Overflow State\n");

     return true;

}

printf("Stack is not full\n");

return false;

}

Output

STATIC ARRAY (Total Capacity: 1000)

Choose any of the following options:

 0: Exit        1: Push        2: Pop        3: Peek

 4: Check if the stack is empty 5: Check if the stack is full

1

Enter element to be pushed into the stack: 7

Choose any of the following options:

 0: Exit        1: Push        2: Pop        3: Peek

 4: Check if the stack is empty 5: Check if the stack is full

1

Enter element to be pushed into the stack: 6

Choose any of the following options:

 0: Exit        1: Push        2: Pop        3: Peek

 4: Check if the stack is empty 5: Check if the stack is full

2

Popping 6 out of the stack

Choose any of the following options:

 0: Exit        1: Push        2: Pop        3: Peek

 4: Check if the stack is empty 5: Check if the stack is full

0

Process returned 0 (0x0)   execution time : 20.144 s

Press any key to continue.

Stack Program in C using Linked List

We will be using a linked list to implement a Dynamic Stack as linked lists are dynamic data stuctures.
A Dynamic Stack does not have a bounded capacity, we can push as much as elements as we want into it.

Implementation:

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

// Function prototypes

void push();   // Push element to the top of the stack

int pop();     // Remove and return the top most element of the stack

int peek();    // Return the top most element of the stack

bool isEmpty(); // Check if the stack is in Underflow state or not

struct node{

int val;

struct node *next;

};

struct node *head;

int main (){

int choice=0;

printf("DYNAMIC STACK");

while(1){

     printf("\n\nChose any of the following options:\n");

     printf("\n 0: Exit 1: Push 2: Pop 3: Peek\n 4: Check if stack is empty\n");

     scanf("%d",&choice);

     switch(choice){

         case 0: exit(0);

         case 1: push(); break;

         case 2: pop(); break;

        case 3: peek(); break;

         case 4: isEmpty(); break;

         default: printf("Please choose a correct option!");

     }

}

}

void push (){

int val;

struct node *ptr = (struct node*)malloc(sizeof(struct node));

printf("Enter the value to be pushed: ");

scanf("%d", &val);

if(head == NULL){

     ptr->val = val;

     ptr->next = NULL;

     head = ptr;

}

else{

     ptr->val = val;

     ptr->next = head;

     head=ptr;

}

}

int pop(){

int item;

struct node *ptr;

if (head == NULL)

     printf("Underflow State: can't remove any item");

else{

     item = head->val;

     ptr = head;

     head = head->next;

     free(ptr);

     printf("%d is popped out of the stack", item);

     return item;

}

return -1;

}

int peek(){

int x = head->val;

printf("%d is the top most element of the stack\n", x);

return x;

}

bool isEmpty(){

if(head == NULL){

     printf("Stack is empty: Underflow State\n");

     return true;

}

printf("Stack is not empty\n");

return false;

}

Output

DYNAMIC STACK

Chose any of the following options:

0: Exit 1: Push 2: Pop 3: Peek

4: Check if stack is empty

1

Enter the value to be pushed: 56

Chose any of the following options:

0: Exit 1: Push 2: Pop 3: Peek

4: Check if stack is empty

1

Enter the value to be pushed: 76

Chose any of the following options:

0: Exit 1: Push 2: Pop 3: Peek

4: Check if stack is empty

2

76 is popped out of the stack

Chose any of the following options:

0: Exit 1: Push 2: Pop 3: Peek

4: Check if stack is empty

0

Process returned 0 (0x0)   execution time: 10.200 s

Press any key to continue.

Applications of Stack in C

Application of Stack in Data Structures

Here are the top 7 applications of the stack in data structure:

1. Expression Evaluation and Conversion

There are three types of expression that you use in programming, they are:

Infix Expression: An infix expression is a single letter or an operator preceded by one single infix string followed by another single infix string.

X

X + Y

(X + Y ) + (A - B)

Prefix Expression: A prefix expression is a single letter or an operator followed by two prefix strings.

X 

+ X Y

+ + X Y - A B

Postfix Expression: A postfix expression (also called Reverse Polish Notation) is a single letter or an operator preceded by two postfix strings.

X

X Y +

X Y + C D - +

Similarly, the stack is used to evaluate these expressions and convert these expressions like infix to prefix or infix to postfix.

2. Backtracking

Backtracking is a recursive algorithm mechanism that is used to solve optimization problems.

To solve the optimization problem with backtracking, you have multiple solutions; it does not matter if it is correct. While finding all the possible solutions in backtracking, you store the previously calculated problems in the stack and use that solution to resolve the following issues.

The N-queen problem is an example of backtracking, a recursive algorithm where the stack is used to solve this problem.

3. Function Call

Whenever you call one function from another function in programming, the reference of calling function stores in the stack. When the function call is terminated, the program control moves back to the function call with the help of references stored in the stack.

So stack plays an important role when you call a function from another function.

4. Parentheses Checking

Stack in data structures is used to check if the parentheses like ( ), { } are valid or not in programing while matching opening and closing brackets are balanced or not.

So it stores all these parentheses in the stack and controls the flow of the program.

For e.g ((a + b) * (c + d)) is valid but {{a+b})) *(b+d}] is not valid.

5. String Reversal

Another exciting application of stack is string reversal. Each character of a string gets stored in the stack.

The string's first character is held at the bottom of the stack, and the last character of the string is held at the top of the stack, resulting in a reversed string after performing the pop operation.

6. Syntax Parsing

Since many programming languages are context-free languages, the stack is used for syntax parsing by many compilers.

7. Memory Management

Memory management is an essential feature of the operating system, so the stack is heavily used to manage memory.

Convert Infix to Postfix Expression

Stack is used to convert a given infix expression to postfix form. We use the following steps to convert a given infix expression to postfix form.

Step 1 –  Scan each character in given infix expression one by one from left to right till end.

Step 2 – If the scanned character is operand then put it into Postfix String

Step 3 – If the scanned character is an operator then do the following –

        Case 1– IF there is no operator is present on stack then push the currently scanned operator on stack.

 Case 2 – IF there is an operator is already present at the top of stack that has the lesser precedence than the currently scanned operator then also push the currently scanned operator on the top of stack.

Case 3 – IF there is an operator is already present at the top of the stack that has the greater or equal precedence than the currently scanned operator then POP that operator from stack and append that operator to the postfix sting and push the currently scanned operator on the top of stack.

Step 4 – IF left and right parenthesis is occurred then push it on stack.

Step 5 – IF there is a case when some operators are enclosed between left parenthesis and right parenthesis on stack then pop the enclosed operators one by one from up to down and append to postfix string. here left and right parenthesis will cancel to each other they will not be append to postfix string.

Infix to Postfix Conversion Example 

Example 1 – Convert the following infix expression to postfix form

 A – ( B / C +  ( D % E * F ) / G ) * H

Check for Balanced Bracket expression using Stack

#include <stdio.h>

#include <stdlib.h>

#define bool int

// Structure of a stack node

struct sNode {

    char data;

    struct sNode* next;

};

// Function to push an item to stack

void push(struct sNode** top_ref, int new_data);

// Function to pop an item from stack

int pop(struct sNode** top_ref);

// Returns 1 if character1 and character2 are matching left

// and right Brackets

bool isMatchingPair(char character1, char character2)

{

    if (character1 == '(' && character2 == ')')

        return 1;

    else if (character1 == '{' && character2 == '}')

        return 1;

    else if (character1 == '[' && character2 == ']')

        return 1;

    else

        return 0;

}

// Return 1 if expression has balanced Brackets

bool areBracketsBalanced(char exp[])

{

    int i = 0;

    // Declare an empty character stack

    struct sNode* stack = NULL;

    // Traverse the given expression to check matching

    // brackets

    while (exp[i]) {

        // If the exp[i] is a starting bracket then push

        // it

        if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')

            push(&stack, exp[i]);

        // If exp[i] is an ending bracket then pop from

        // stack and check if the popped bracket is a

        // matching pair*/

        if (exp[i] == '}' || exp[i] == ')'

            || exp[i] == ']') {

            // If we see an ending bracket without a pair

            // then return false

            if (stack == NULL)

                return 0;

            // Pop the top element from stack, if it is not

            // a pair bracket of character then there is a

            // mismatch.

            // his happens for expressions like {(})

            else if (!isMatchingPair(pop(&stack), exp[i]))

                return 0;

        }

        i++;

    }

    // If there is something left in expression then there

    // is a starting bracket without a closing

    // bracket

    if (stack == NULL)

        return 1; // balanced

    else

        return 0; // not balanced

}

// Driver code

int main()

{

    char exp[100] = "{()}[]";

    // Function call

    if (areBracketsBalanced(exp))

        printf("Balanced \n");

    else

        printf("Not Balanced \n");

    return 0;

}

// Function to push an item to stack

void push(struct sNode** top_ref, int new_data)

{

    // allocate node

    struct sNode* new_node

        = (struct sNode*)malloc(sizeof(struct sNode));

    if (new_node == NULL) {

        printf("Stack overflow n");

        getchar();

        exit(0);

    }

    // put in the data

    new_node->data = new_data;

    // link the old list of the new node

    new_node->next = (*top_ref);

    // move the head to point to the new node

    (*top_ref) = new_node;

}

// Function to pop an item from stack

int pop(struct sNode** top_ref)

{

    char res;

    struct sNode* top;

    // If stack is empty then error

    if (*top_ref == NULL) {

        printf("Stack overflow n");

        getchar();

        exit(0);

    }

    else {

        top = *top_ref;

        res = top->data;

        *top_ref = top->next;

        free(top);

        return res;

    }

}

Output

Balanced

C Program to Convert Infix to Postfix using Stack

#include<stdio.h>

#include<ctype.h>

char stack[100];

int top = -1;

void push(char x)

{

stack[++top] = x;

}

char pop()

{

if(top == -1)

     return -1;

else

     return stack[top--];

}

int priority(char x)

{

if(x == '(')

     return 0;

if(x == '+' || x == '-')

     return 1;

if(x == '*' || x == '/')

     return 2;

return 0;

}

int main()

{

char exp[100];

char *e, x;

printf("Enter the expression : ");

scanf("%s",exp);

printf("\n");

e = exp;

while(*e != '\0')

{

     if(isalnum(*e))

         printf("%c ",*e);

     else if(*e == '(')

         push(*e);

     else if(*e == ')')

     {

         while((x = pop()) != '(')

             printf("%c ", x);

     }

     else

     {

         while(priority(stack[top]) >= priority(*e))

             printf("%c ",pop());

         push(*e);

     }

     e++;

}

while(top != -1)

{

     printf("%c ",pop());

}return 0;

}

Output:

Enter the expression : a+b*c

a b c * +

C Program to Evaluate POSTFIX Expression Using Stack

#include<stdio.h>

int stack[20];

int top = -1;

void push(int x)

{

stack[++top] = x;

}

int pop()

{

return stack[top--];

}

int main()

{

char exp[20];

char *e;

int n1,n2,n3,num;

printf("Enter the expression :: ");

scanf("%s",exp);

e = exp;

while(*e != '\0')

{

     if(isdigit(*e))

     {

         num = *e - 48;

         push(num);

     }

     else

     {

         n1 = pop();

         n2 = pop();

         switch(*e)

         {

         case '+':

         {

             n3 = n1 + n2;

             break;

         }

         case '-':

         {

             n3 = n2 - n1;

             break;

         }

         case '*':

         {

             n3 = n1 * n2;

             break;

         }

         case '/':

         {

             n3 = n2 / n1;

             break;

         }

         }

         push(n3);

     }

     e++;

}

printf("\nThe result of expression %s  =  %d\n\n",exp,pop());

return 0;

}

OUTPUT:

Enter the expression :: 245+*

The result of expression 245+*  =  18

Queue

Linked List

A linked list is a linear data structure that includes a series of connected nodes. Here, each node stores the data and the address of the next node. For example,

You have to start somewhere, so we give the address of the first node a special name called HEAD. Also, the last node in the linked list can be identified because its next portion points to NULL.

Representation of Linked List

Let's see how each node of the linked list is represented. Each node consists:

·         A data item

·         An address of another node

We wrap both the data item and the next node reference in a struct as:

struct node

{

  int data;

  struct node *next;

};

Each struct node has a data item and a pointer to another struct node. Let us create a simple Linked List with three items to understand how this works.

/* Initialize nodes */

struct node *head;

struct node *one = NULL;

struct node *two = NULL;

struct node *three = NULL;

/* Allocate memory */

one = malloc(sizeof(struct node));

two = malloc(sizeof(struct node));

three = malloc(sizeof(struct node));

/* Assign data values */

one->data = 1;

two->data = 2;

three->data=3;

/* Connect nodes */

one->next = two;

two->next = three;

three->next = NULL;

/* Save address of first node in head */

Types of Linked List

1)      Singly Linked Lists

Singly linked lists contain two "blocks" in one node; one block holds the data and the other block  holds the address of the next node of the list. Traversals can be done in one direction only as there is only a single link between two nodes of the same list.

2)      Doubly Linked Lists

Doubly Linked Lists contain three "blocks" in one node; one block holds the data and the other blocks hold the addresses of the previous and next nodes in the list. The list is traversed twice as the nodes in the list are connected to each other from both sides.

3)      Circular Linked Lists

Circular linked lists can exist in both singly linked list and doubly linked list.

Since the last node and the first node of the circular linked list are connected, the traversal in this linked list will go on forever until it is broken.

Basic Operations in Linked List

The basic operations in the linked lists are insertion, deletion, searching, display, and deleting an element at a given key. These operations are performed on Singly Linked Lists as given below −

Insertion − Adds an element at the beginning of the list.

Deletion − Deletes an element at the beginning of the list.

Display − Displays the complete list.

Search − Searches an element using the given key.

Insertion of a node in Linked List

Adding a new node in linked list is a more than one step activity.  First, create a node using the same structure and find the location where it has to be inserted.

Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point B.next to C −

NewNode.next -> RightNode;

It should look like this −

Now, the next node at the left should point to the new node.

LeftNode.next -> NewNode;

This will put the new node in the middle of the two. The new list should look like this −

Insertion in linked list can be done in three different ways. They are explained as follows −

Insertion at Beginning

In this operation, we are adding an element at the beginning of the list.

Algorithm

1. START

2. Create a node to store the data

3. Check if the list is empty

4. If the list is empty, add the data to the node and

   assign the head pointer to it.

5. If the list is not empty, add the data to a node and link to the

   current head. Assign the head to the newly added node.

6. END

Insertion at Ending

In this operation, we are adding an element at the ending of the list.

Algorithm

1. START

2. Create a new node and assign the data

3. Find the last node

4. Point the last node to new node

5. END

Insertion at a Given Position

In this operation, we are adding an element at any position within the list.

Algorithm

1. START

2. Create a new node and assign data to it

3. Iterate until the node at position is found

4. Point first to new first node

5. END

Linked List - Deletion Operation

Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the target node to be removed, by using searching algorithms.

The left (previous) node of the target node now should point to the next node of the target node −

LeftNode.next -> TargetNode.next;

This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.

TargetNode.next -> NULL;

We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory and wipe off the target node completely.

Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.

Deletion in linked lists is also performed in three different ways. They are as follows −

Deletion at Beginning

In this deletion operation of the linked, we are deleting an element from the beginning of the list. For this, we point the head to the second node.

Algorithm

1. START

2. Assign the head pointer to the next node in the list

3. END

Deletion at Ending

In this deletion operation of the linked, we are deleting an element from the ending of the list.

Algorithm

1. START

2. Iterate until you find the second last element in the list.

3. Assign NULL to the second last element in the list.

4. END

Deletion at a Given Position

In this deletion operation of the linked, we are deleting an element at any position of the list.

Algorithm

1. START

2. Iterate until find the current node at position in the list.

3. Assign the adjacent node of current node in the list to its previous node.

4. END

Linked List - Reversal Operation

This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.

First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −

We have to make sure that the last node is not the last node. So we'll have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.

Except the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.

We'll make the head node point to the new first node by using the temp node.

Algorithm

Step by step process to reverse a linked list is as follows −

1. START

2. We use three pointers to perform the reversing:  prev, next, head.

3. Point the current node to head and assign its next value to  the prev node.

4. Iteratively repeat the step 3 for all the nodes in the list.

5. Assign head to the prev node.

Linked List - Search Operation

Searching for an element in the list using a key element. This operation is done in the same way as array search; comparing every element in the list with the key element given.

Algorithm

1 START

2 If the list is not empty, iteratively check if the list contains the key

3 If the key element is not present in the list, unsuccessful  search

4 END

Linked List - Traversal Operation

The traversal operation walks through all the elements of the list in an order and displays the elements in that order.

Algorithm

1. START

2. While the list is not empty and did not reach the end of the list, print the data in each node

3. END

Applications of Linked List

Applications of linked list in computer science:

1.     Implementation of stacks and queues

2.     Implementation of graphs: Adjacency list representation of graphs is the most popular which uses a linked list to store adjacent vertices.

3.     Dynamic memory allocation: We use a linked list of free blocks.

4.     Maintaining a directory of names

5.     Performing arithmetic operations on long integers

6.     Manipulation of polynomials by storing constants in the node of the linked list

7.     Representing sparse matrices

Applications of linked list in the real world:

1.     Image viewer – Previous and next images are linked and can be accessed by the next and previous buttons.

2.     Previous and next page in a web browser – We can access the previous and next URL searched in a web browser by pressing the back and next buttons since they are linked as a linked list.

3.     Music Player – Songs in the music player are linked to the previous and next songs. So you can play songs either from starting or ending of the list.

4.     GPS navigation systems- Linked lists can be used to store and manage a list of locations and routes, allowing users to easily navigate to their desired destination.

5.     Robotics- Linked lists can be used to implement control systems for robots, allowing them to navigate and interact with their environment.

6.     Task Scheduling- Operating systems use linked lists to manage task scheduling, where each process waiting to be executed is represented as a node in the list.

7.     Image Processing- Linked lists can be used to represent images, where each pixel is represented as a node in the list.

8.     File Systems- File systems use linked lists to represent the hierarchical structure of directories, where each directory or file is represented as a node in the list.

9.     Symbol Table- Compilers use linked lists to build a symbol table, which is a data structure that stores information about identifiers used in a program.

10.  Undo/Redo Functionality- Many software applications implement undo/redo functionality using linked lists, where each action that can be undone is represented as a node in a doubly linked list.

11.  Speech Recognition-  Speech recognition software uses linked lists to represent the possible phonetic pronunciations of a word, where each possible pronunciation is represented as a node in the list.

12.  Polynomial Representation- Polynomials can be represented using linked lists, where each term in the polynomial is represented as a node in the list.

13.  Simulation of Physical Systems-  Linked lists can be used to simulate physical systems, where each element in the list represents a discrete point in time and the state of the system at that time.

Applications of Circular Linked Lists:

1.     Useful for implementation of a queue. Unlike this implementation, we don’t need to maintain two-pointers for the front and rear if we use a circular linked list. We can maintain a pointer to the last inserted node and the front can always be obtained as next of last.

2.     Circular lists are useful in applications to go around the list repeatedly. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.

3.     Circular Doubly Linked Lists are used for the implementation of advanced data structures like the Fibonacci Heap.

4.     Circular linked lists can be used to implement circular queues, which are often used in operating systems for scheduling processes and managing memory allocation.

5.     Used in database systems to implement linked data structures, such as B+ trees, which are used to optimize the storage and retrieval of data.

6.     Circular linked lists can be used in networking. For instance, to implement circular buffers for streaming data, such as video and audio, in networking applications.

7.     Video games use circular linked lists to manage sprite animations. Each frame of the animation is represented as a node in the list, and the last frame is connected to the first frame to create a loop.

8.     Circular linked lists can be used to represent a buffer of audio or signal data in signal processing applications. The last node is connected to the first node to create a loop, and the processing algorithms can efficiently iterate over the data.

9.     Traffic light control systems use circular linked lists to manage the traffic light cycles. Each phase of the traffic light cycle is represented as a node in the list, and the last node is connected to the first node to create a loop.

Application of Doubly Linked Lists:

1.     Redo and undo functionality.

2.     Use of the Back and forward button in a browser.

3.     The most recently used section is represented by the Doubly Linked list.

4.     Other Data structures like Stack, Hash Table, and Binary Tree can also be applied by Doubly Linked List.

5.     Used to implement game objects and their interactions in a game engine.

6.     Used in networking.

7.     Used in Graph algorithms.

8.     Operating systems use doubly linked lists to manage the process scheduling. Each process waiting to be executed is represented as a node in the doubly linked list, and the operating system can easily traverse the list in both directions to manage the process queue.

Binary Tree

A binary tree is a tree data structure in which each parent node can have at most two children. Each node of a binary tree consists of three items:

data item

address of left child

address of right child

Binary Tree Representation

A node of a binary tree is represented by a structure containing a data part and two pointers to other structures of the same type.

struct node

{

 int data;

 struct node *left;

 struct node *right;

};

TREE DATA STRUCTURE TERMINOLOGY

1.       Node: A node is a structure that may contain a value or condition, or represent a separate data structure.

2.   Root: The top node in a tree, the prime ancestor.

3.   Child: A node directly connected to another node when moving away from the root, an immediate descendant.

4.   Parent: The converse notion of a child, an immediate ancestor.

5.   Leaf: A node with no children.

6.   Internal node: A node with at least one child.

7.   Edge: The connection between one node and another.

8.   Depth: The distance between a node and the root.

9.   Level: the number of edges between a node and the root + 1

10.   Height: The number of edges on the longest path between a node and a descendant leaf.

11.   Breadth: The number of leaves.

12.   Subtree: A tree T is a tree consists of a node in T and all of its descendants in T.

Types of Binary Tree

1. Full Binary Tree

A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children

2. Perfect Binary Tree

A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.

3. Complete Binary Tree

A complete binary tree is just like a full binary tree, but with two major differences

1.     Every level must be completely filled

2.     All the leaf elements must lean towards the left.

3.     The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.

4. Degenerate or Pathological Tree

A degenerate or pathological tree is the tree having a single child either left or right.

5. Skewed Binary Tree

A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left nodes or the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed binary tree.

6. Balanced Binary Tree

It is a type of binary tree in which the difference between the height of the left and the right subtree for each node is either 0 or 1.

Tree traversal (Inorder, Preorder an Postorder)

The term 'tree traversal' means traversing or visiting each node of a tree. There is a single way to traverse the linear data structure such as linked list, queue, and stack. Whereas, there are multiple ways to traverse a tree that are listed as follows -

• Preorder traversal

• Inorder traversal

• Postorder traversal

Preorder traversal

This technique follows the 'root left right' policy. It means that, first root node is visited after that the left subtree is traversed recursively, and finally, right subtree is recursively traversed. As the root node is traversed before (or pre) the left and right subtree, it is called preorder traversal.

The applications of preorder traversal include -

• It is used to create a copy of the tree.

• It can also be used to get the prefix expression of an expression tree.

Algorithm

                     Until all nodes of the tree are not visited  

Step 1 - Visit the root node  

Step 2 - Traverse the left subtree recursively.  

Step 3 - Traverse the right subtree recursively.

Postorder traversal

This technique follows the 'left-right root' policy. It means that the first left subtree of the root node is traversed, after that recursively traverses the right subtree, and finally, the root node is traversed. As the root node is traversed after (or post) the left and right subtree, it is called postorder traversal.

The applications of postorder traversal include -

• It is used to delete the tree.

• It can also be used to get the postfix expression of an expression tree.

Algorithm

Until all nodes of the tree are not visited  

Step 1 - Traverse the left subtree recursively.  

Step 2 - Traverse the right subtree recursively.  

Step 3 - Visit the root node.  

Inorder traversal

This technique follows the 'left root right' policy. It means that first left subtree is visited after that root node is traversed, and finally, the right subtree is traversed. As the root node is traversed between the left and right subtree, it is named inorder traversal.

The applications of Inorder traversal includes -

• It is used to get the BST nodes in increasing order.

• It can also be used to get the prefix expression of an expression tree.

Algorithm

                          Until all nodes of the tree are not visited  

 Step 1 - Traverse the left subtree recursively.  

Step 2 - Visit the root node.  

Step 3 - Traverse the right subtree recursively.   

Threaded Binary Tree:

 In binary tree, the leaf nodes have no children. Therefore, the left and right fields of the leaf nodes are made NULL. But, NULL wastes memory space so to avoid NULL in the node we will set threads.

binary trees with threads are known as threaded binary trees. Each node in a threaded binary tree either contains a link to its child node or thread to other nodes in the tree.

Types of Threaded Binary Tree:

1.One-way threaded Binary trees:

In one-way threaded binary trees, a thread will appear either in the right or left link field of a node. If it appears in the right link field of a node then it will point to the next node that will appear on performing in order traversal. Such trees are called Right threaded binary trees. If thread appears in the left field of a node then it will point to the nodes inorder predecessor. Such trees are called Left threaded binary trees.

2.Two-way threaded Binary Trees:In two-way threaded Binary trees, the right link field of a node containing NULL values is replaced by a thread that points to nodes inorder successor and left field of a node containing NULL values is replaced by a thread that points to nodes inorder predecessor.

Advantages of Threaded Binary Tree:

• In threaded binary tree, linear and fast traversal of nodes in the tree so there is no requirement of stack. If the stack is used then it consumes a lot of memory and time.

• It is more general as one can efficiently determine the successor and predecessor of any node by simply following the thread and links. It almost behaves like a circular linked list.

Disadvantages of Threaded Binary Tree:

• When implemented, the threaded binary tree needs to maintain the extra information for each node to indicate whether the link field of each node points to an ordinary node or the node's successor and predecessor.

• Insertion into and deletion from a threaded binary tree are more time consuming since both threads and ordinary links need to be maintained.

Applications of threaded binary tree –

·         Expression evaluation: Threaded binary trees can be used to evaluate arithmetic expressions in a way that avoids recursion or a stack. The tree can be constructed from the input expression, and then traversed in-order or pre-order to perform the evaluation.

·         Database indexing: In a database, threaded binary trees can be used to index data based on a specific field (e.g. last name). The tree can be constructed with the indexed values as keys, and then traversed in-order to retrieve the data in sorted order.

·         Symbol table management: In a compiler or interpreter, threaded binary trees can be used to store and manage symbol tables for variables and functions. The tree can be constructed with the symbols as keys, and then traversed in-order or pre-order to perform various operations on the symbol table.

·         Disk-based data structures: Threaded binary trees can be used in disk-based data structures (e.g. B-trees) to improve performance. By threading the tree, it can be traversed in a way that minimizes disk seeks and improves locality of reference.

·         Navigation of hierarchical data: In certain applications, threaded binary trees can be used to navigate hierarchical data structures, such as file systems or web site directories.

Binary Search Tree

 In a Binary search tree, the value of left node must be smaller than the parent node, and the value of right node must be greater than the parent node. This rule is applied recursively to the left and right subtrees of the root.

Example of creating a binary search tree

Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50

Basic Operations

Following are the basic operations of a Binary Search Tree −

1.       Search − Searches an element in a tree.

2.   Insert − Inserts an element in a tree.

3.   Pre-order Traversal − Traverses a tree in a pre-order manner.

4.   In-order Traversal − Traverses a tree in an in-order manner.

5.       Post-order Traversal − Traverses a tree in a post-order

The complexity of the Binary Search tree

Let's see the time and space complexity of the Binary search tree. We will see the time complexity for insertion, deletion, and searching operations in best case, average case, and worst case.

1. Time Complexity

2. Space Complexity

Operations

Best case time complexity

Average case time complexity

Worst case time complexity

Insertion

O(log n)

O(log n)

O(n)

Deletion

O(log n)

O(log n)

O(n)

Search

O(log n)

O(log n)

O(n)

Operations

Space complexity

Insertion

O(n)

Deletion

O(n)

Search

O(n)

A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.

Following are the conditions for a height-balanced binary tree:

1.   difference between the left and the right subtree for any node is not more than one

2.   the left subtree is balanced

3. the right subtree is balanced

AVL Tree:

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. 

Example of AVL Tree:

The above tree is AVL because the differences between the heights of left and right subtrees for every node are less than or equal to 1.

Example of a Tree that is NOT an AVL Tree:

The above tree is not AVL because the differences between the heights of the left and right subtrees for 8 and 12 are greater than 1.

Comparison between Height Balanced Tree and Weight Balanced Tree

·          

·          

·          

What is Height Balanced Tree?

Self-Balancing binary search trees are the height-balanced binary tree is one for which at every node, the absolute value of the difference in heights of the left and right subtree is no larger than one. An empty tree is height-balanced. A non-empty binary tree T is balanced if:  

1.       The left subtree of T is balanced.

2.       The right subtree of T is balanced.

3.       The difference between the heights of the left subtree and the right subtree is not more than 1.

Note: 

Every complete binary tree is height-balanced.

Example: 

Red Black Tree, Splay Tree, and an AVL Tree is height-balanced binary search tree.

What is Weight Balanced Binary Tree?

A weight-balanced tree is a binary tree in which for each node the number of nodes in the left subtree is at least half and at most twice the number of nodes in the right subtree.  It is a binary tree that is balanced based on the knowledge of the probabilities of searching for each individual node. In each sub-tree, the node with the highest weight appears at the root thereby resulting in more efficient searching performance. The nodes which are most likely to be searched/accessed have the lowest search time.

Example:

Huffman Tree.

In the above diagram, the letters represent the node values and the numbers represent node weights.

Why different definitions of balanced

Binary Search Tree (BST) was invented to make searching a more efficient process, than searching in an unordered array. However, when the BST is unbalanced then that case searching was inefficient. For efficient searching, it is advisable to keep the tree balanced. But it is difficult and inefficient to keep a BST balanced as the values are added and deleted frequently. Thus, a way was invented to keep the BST balanced by adding more information to each node or by allowing a node to have more than two children. Some of the examples of such invented trees were AVL Tree, 2-3 Tree, B-Tree, Red-Black Tree, etc.

Comparison of Height Balanced and Weight Balanced Tree

A height-balanced tree improves the worst-case lookup time (for a binary tree, it will always be bounded by log2(n)), at the expense of making the typical case roughly one lookup less (approximately half of the nodes will be at the maximum depth).

If your weight is related to frequency-of-lookup, a weight-balanced tree will improve the average lookup time, at the expense of making the worst-case higher (more frequently requested items have a higher weight, and will thus tend to be in shallower trees, with the cost being deeper trees for less-frequently-requested items).

S No.

Height Balanced Tree

Weight Balanced Tree

1

It is the binary tree that is balanced based on the height of the subtrees.

It is the binary tree that is balanced based on the weight on the edges of the tree.

2

In a height-balanced tree, the absolute difference of height of the left subtree and the right subtree should be minimum.

In weight balanced tree, the absolute difference between the weight of the left subtree and the right subtree should be minimum.

3

It will improve the worst-case lookup time at the expense of making a typical case roughly one lookup less

It will improve the average lookup time at the expense of making the worst-case higher.

4

The restructuring operation on a node with n descendants happens every 2-O(lg n) operation.

The restructuring operation on a node with n descendants happens every O(1/n) operation.

Unit 4: Hashing and File structures : Hashing: The hash table concept, Hashing Functions, CollisionResolution Techniques, File Structure: Concepts of fields, records and files, Sequential, Indexed and Relative/Random File Organization, Indexing structure for index files, hashing for direct files, Multi-Key file organization and access methods.

What is Hash Table?

A Hash table is defined as a data structure used to insert, look up, and remove key-value pairs quickly. It operates on the hashing concept, where each key is translated by a hash function into a distinct index in an array. The index functions as a storage location for the matching value. In simple words, it maps the keys with the value.

What is Load factor?

A hash table’s load factor is determined by how many elements are kept there in relation to how big the table is. The table may be cluttered and have longer search times and collisions if the load factor is high. An ideal load factor can be maintained with the use of a good hash function and proper table resizing.

What is a Hash function?

A Function that translates keys to array indices is known as a hash function. The keys should be evenly distributed across the array via a decent hash function to reduce collisions and ensure quick lookup speeds.

·         Integer universe assumption: The keys are assumed to be integers within a certain range according to the integer universe assumption. This enables the use of basic hashing operations like division or multiplication hashing.

·         Hashing by division: This straightforward hashing technique uses the key’s remaining value after dividing it by the array’s size as the index. When an array size is a prime number and the keys are evenly spaced out, it performs well.

·         Hashing by multiplication: This straightforward hashing operation multiplies the key by a constant between 0 and 1 before taking the fractional portion of the outcome. After that, the index is determined by multiplying the fractional component by the array’s size. Also, it functions effectively when the keys are scattered equally.

Choosing a hash function:

Selecting a decent hash function is based on the properties of the keys and the intended functionality of the hash table. Using a function that evenly distributes the keys and reduces collisions is crucial.

Criteria based on which a hash function is chosen:

·         To ensure that the number of collisions is kept to a minimum, a good hash function should distribute the keys throughout the hash table in a uniform manner. This implies that for all pairings of keys, the likelihood of two keys hashing to the same position in the table should be rather constant.

·         To enable speedy hashing and key retrieval, the hash function should be computationally efficient.

·         It ought to be challenging to deduce the key from its hash value. As a result, attempts to guess the key using the hash value are less likely to succeed.

·         A hash function should be flexible enough to adjust as the data being hashed changes. For instance, the hash function needs to continue to perform properly if the keys being hashed change in size or format.

Collision resolution techniques:

Collisions happen when two or more keys point to the same array index. Chaining, open addressing, and double hashing are a few techniques for resolving collisions.

·         Open addressing: collisions are handled by looking for the following empty space in the table. If the first slot is already taken, the hash function is applied to the subsequent slots until one is left empty. There are various ways to use this approach, including double hashing, linear probing, and quadratic probing.

·         Separate Chaining: In separate chaining, a linked list of objects that hash to each slot in the hash table is present. Two keys are included in the linked list if they hash to the same slot. This method is rather simple to use and can manage several collisions.

·         Robin Hood hashing: To reduce the length of the chain, collisions in Robin Hood hashing are addressed by switching off keys. The algorithm compares the distance between the slot and the occupied slot of the two keys if a new key hashes to an already-occupied slot. The existing key gets swapped out with the new one if it is closer to its ideal slot. This brings the existing key closer to its ideal slot. This method tends to cut down on collisions and average chain length.

Applications of Hash Table:

·         Hash tables are frequently used for indexing and searching massive volumes of data. A search engine might use a hash table to store the web pages that it has indexed.

·         Data is usually cached in memory via hash tables, enabling rapid access to frequently used information. 

·         Hash functions are frequently used in cryptography to create digital signatures, validate data, and guarantee data integrity.

·         Hash tables can be used for implementing database indexes, enabling fast access to data based on key values. 

File:

It is the organisation of records in a file.

Record:- It is the collection of related fields.

Field:- It is the smallest logically meaningful unit of information in a file.

Types of files –

 1. Serial Files

2. Sequential Files

 3. Direct or Random Files

 4. Index Sequential Files

Serial Files –

 · This type of file was used in 1950-1960.

 · The records are arranged one after another.

· New record is added at the end of the file.

· These files were stored in magnetic tapes.

· When the size of the file increases, the time required to access data becomes more.

 This is because it can only apply linear search.

 · Logical ordering = Physical ordering ·

 These are used in secondary files ·

 Examples – A material without page no. Here searching will be difficult due to lack of page number.

Sequential File –

· The records are orders. ·

 . There is no key value.

 · Gaps are left so that new records can be added there to maintain ordering.

 · New record is added in gaps left between records according to ordering.

 · These files were stored in magnetic tapes.

 · When the size of the file increases, the time required to access data becomes more.

 This is because there are no key.

 · Logical ordering may not be equal to Physical ordering.

 · These are used in master files.

 · Examples – Arranging cards in sequential order (A 2 3 4 5 6 7 8 9 10 J Q K)

 Direct or Random Files- · Each record is associated with a direct function.

 · There are key values.

 · The records have mapping.

 · Disk device like CD are used.

 · Searching is quit faster.

 · Hashing is its extension.

 · Due to mapping more space is needed.

 · It is more complex than the previous 2 files.

 Index Sequential File –

 · This was invented by IBM.

 · These uses indices.

 · Access is sequential.

 · Indexing and sorting is random.

 · These have keys.

 · A group of keys are given one index.

 · Disk device is used for storage.

· Searching is fast as the index is searched and then the key is searched.

 · This is used in banking.

 · Example – Contents of a book. The topics are the keys. They have indices like page number. That topic can be found in that page no. When new information needs to be added, a pointer is taken to point to a new location like in appendix of a book. This saves the time and errors that occur due to shifting the later data after insertion.