Data Structures in C

In computer jargon, a data structure is a method of storing and organising data in a computer's memory so that it may be used effectively later. Data can be organised in a number of different ways. A data structure is a logical or mathematical representation of how data is organised.

A data model's variety is defined by two factors:

• To begin, it must be well-structured in order to accurately portray the data's true relationships with real-world objects.
• Second, the structure should be basic enough that anyone can readily process the data as needed.

Data structures can be divided into two categories:

1. 1. Linear data structures: The organisation of linear data structures is similar to that of computer memory. In a linear approach, linear data structures store elements one after the other. Arrays, Queues, Linked Lists, and Stacks are common examples.

2. 2. Non linear data structures: Data structures that are not linear are stored in a sequential order. In non linear data structures, data elements may have relationships with one or more elements at the same time. Tree and graph are common examples.

Data structures are important in almost every field you can think of. Here are scenarios where they're frequently used:

• Artificial Intelligence
• Database Management Systems
• Operating Systems
• Numerical Analysis
• Graphics
• Compiler Design
• Simulation etc.

Arrays are groups of data elements of similar types stored in memory regions that are contiguous. It is the most basic data structure in which the index number of each data element can be used to get it at random.

A Linked List is a collection of nodes, or data objects that are randomly stored. A pointer connects each node in a Linked List to its neighbouring node. In a node, there are two fields: Data Field and Link Field.

A queue is a collection of data organised according to the FIFO principle (First in, First Out). It's a linear data structure where only the elements at the front of a queue are removed, and only the elements at the back are added.

Consider a line of people forming in front of a movie theatre to purchase tickets. People who want to skip to the front of the queue for tickets must wait in the back. People leave the line only after collecting their tickets at the front.

#include<stdio.h>
#define SIZE 5
void enQueue(int);
void deQueue();
void display();
int items[SIZE], front = -1, rear = -1;

int main() {
    deQueue();
    enQueue(1);
    enQueue(2);
    enQueue(3);
    enQueue(4);
    enQueue(5);
    enQueue(6);
    display();
    deQueue();
    display();
    return 0;
}

void enQueue(int value) {
    if(rear == SIZE-1)
        printf("\nQueue is Full!!");
    else {
        if(front == -1)
            front = 0;
        rear++;
        items[rear] = value;
        printf("\nInserted -> %d", value);
    }
}

void deQueue() {
    if(front == -1)
        printf("\nQueue is Empty!!");
    else {
        printf("\nDeleted : %d", items[front]);
        front++;
        if(front > rear)
            front = rear = -1;
    }
}

void display() {
    if(rear == -1)
        printf("\nQueue is Empty!!!");
    else {
        int i;
        printf("\nQueue elements are:\n");
        for(i=front; i<=rear; i++)
            printf("%d\t",items[i]);
    }
}

A linear data structure referred to as a stack follows the strategy of "last in, first out" (LIFO). A new item is added to the top of a stack. Both insert and delete actions are performed from one end of the stack.

There are two different uses for stacks. Use the push method to add components to the stack, and the pop function to remove parts from the stack.

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

struct Stack {
    int top;
    unsigned capacity;
    int* array;
};

struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

int isFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

void push(struct Stack* stack, int item) {
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}

int pop(struct Stack* stack) {
    if (isEmpty(stack))
        return INT_MIN;
    return stack->array[stack->top--];
}

int peek(struct Stack* stack) {
    if (isEmpty(stack))
        return INT_MIN;
    return stack->array[stack->top];
}

int main() {
    struct Stack* stack = createStack(100);
    push(stack, 11);
    push(stack, 12);
    push(stack, 33);
    printf("%d popped from stack\n", pop(stack));
    return 0;
}

It's a type of linked list (double-ended LL) in which each node has two links, one to the next node in the sequence and the other to the previous node in the series. This allows traversal of the data elements in both directions.

Examples:

• A music playlist with next and previous track navigation options.
• Recently visited pages in the browser cache
• Undo and redo functions in the browser, which let you to return to a previous page by reversing the node.

The fundamental difference between the two data structures is the memory space that is accessed. The phrase "storage structure" refers to the structure that houses the computer system's main memory. When interacting with auxiliary structures, we refer to them as file structures.

Some examples of queue applications are as follows:

• Queues are commonly used to build queues for a single shared resource, such as a printer, disc, or CPU.
• Queues are used for asynchronous data transfer in pipes, file IO, and sockets.
• Queues are used as buffers by most programmes, such as MP3 players and CD players.
• In media players, queues are used to maintain track of the playlist.
• Interrupts are handled by queues in operating systems.

A Binary Search Tree is a binary tree where the value at the root node is smaller than all elements on the left and larger than all elements on the right.

#include<stdio.h>
#include<stdlib.h>

struct node {
    int value;
    struct node* left;
    struct node* right;
};

struct node* createNode(int data) {
    struct node* newNode = malloc(sizeof(struct node));
    newNode->value = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct node* insertNode(struct node* current, int data) {
    if (current == NULL)
        return createNode(data);
    if (current->value < data)
        current->right = insertNode(current->right, data);
    else if (current->value > data)
        current->left = insertNode(current->left, data);
    return current;
}

🚀 Because items can only be placed at the front end, the array space used to store queue elements can never be reused.

🚀 Array Size: When creating a queue with an array, figuring out the right size is always a challenge.

A postfix expression is composed of operators and operands, with the operator arriving after the operands. The correct postfix phrase is A B + C *.

Merge sort is a divide and conquer sorting algorithm. It works by merging and sorting neighbouring data to create larger sorted lists.

Selection sort repeatedly selects the smallest number from the list and places it at the beginning.

void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        swap(&arr[min_idx], &arr[i]);
    }
}

Bubble sort compares adjacent elements and swaps their values if they are out of order.

void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

An AVL tree is a binary search tree that is always in a partially balanced state. The difference in heights of subtrees is used to calculate the balance.

A priority queue is an abstract data type that contains entries of varying priority. Components with higher priority are processed first.

• Lexical analysis
• Hierarchical data modeling
• Arithmetic expression handling
• Symbol table creation

Two data structures are crucial in graph implementation:

• Adjacency list: Used to represent linked data
• Adjacency matrix: Used to represent sequential data

The new item must be unique. If the tree is empty, the new item becomes the root. If not empty, compare with root: if less, add to left subtree; if greater, add to right subtree.

🚀 On maps, cities/states/regions are represented as vertices, adjacency relationships as edges.

🚀 In programme flow analysis, procedures are vertices, calls are edges.

🚀 In transportation networks, stations are vertices, routes are edges.

🚀 In circuit networks, connection points are vertices, cables are edges.

A graph G represents an ordered collection G(V, E), where V(G) represents vertices and E(G) represents edges connecting these vertices.

The AVL tree controls the height of the binary search tree, preventing it from being skewed. By limiting the height to log n, the AVL tree imposes an upper bound of O(log n) on each operation.

A B tree of order m has the following characteristics:

🚀 All leaf nodes must have the same level.

🚀 At least two root nodes are required.

🚀 Every node has at least m/2 children, except root and leaf nodes.

🚀 Each node can have up to m children.