C Programming Data Structures Operations Insertion Deletion Traversal Complete Guide

Arrays

Insertion:

In arrays, insertion involves adding an element at a specific position or at the end. Shifting elements to the right to accommodate the new element is necessary if the insertion is not at the end.

Example (Insertion at the end):

#include <stdio.h>

void insertAtEnd(int arr[], int* n, int newElement) {
    if (*n >= 100) { 
        printf("Array is full!\n");
        return;
    }
    arr[*n] = newElement;
    (*n)++;
}

int main() {
    int arr[100] = {1, 2, 3, 4};
    int n = 4; // Size of array
    int newElement = 5;

    insertAtEnd(arr, &n, newElement);

    printf("Array after insertion at the end: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Important Information:

• Time Complexity: O(1) for inserting at the end, O(n) for inserting at the beginning or middle.
• Space Complexity: O(1). No additional space required beyond what the array already has allocated.

Deletion:

Deletion from an array involves removing an element by shifting subsequent elements leftwards.

Example (Deletion from a given index):

#include <stdio.h>

void deleteFromIndex(int arr[], int* n, int index) {
    if (index >= *n || index < 0) {
        printf("Invalid Index!\n");
        return;
    }
    for (int i = index; i < *n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    (*n)--;
}

int main() {
    int arr[100] = {1, 2, 3, 4, 5};
    int n = 5; // Size of array
    int index = 2;

    deleteFromIndex(arr, &n, index);

    printf("Array after deletion from index %d: ", index);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Important Information:

• Time Complexity: O(n) because all elements to the right of the deleted index must be shifted.
• Space Complexity: O(1).

Traversal:

Traversal in an array involves visiting each element one after another.

Example:

#include <stdio.h>

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5; 

    printf("Traversing the array:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Important Information:

• Time Complexity: O(n) since every element is visited exactly once.
• Space Complexity: O(1).

Linked Lists

Insertion:

There are three types of insertions in linked lists:

• Beginning.
• Specific Position.
• End.

Example (Insert at Beginning):

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

struct Node {
    int data;
    struct Node* next;
};

void insertAtBeginning(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = *head;
    *head = newNode;
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 16);

    printList(head); 

    return 0;
}

Important Information:

• Time Complexity: O(1) for inserting at the beginning, O(n) for inserting at the end.
• Space Complexity: O(1) for each node added.

Deletion:

Deletion involves removing a node based on its value or position. It includes updating pointers to bypass the deleted node.

Example (Delete node with a specific value):

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

void deleteNodeByValue(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) { // If head holds the key
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) { // Key was not present in list
        printf("Value not found!\n");
        return;
    }

    prev->next = temp->next;
    free(temp);
}

int main() {
    struct Node* head = NULL;

    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 1);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);

    printf("Created Linked List: ");
    printList(head);
    deleteNodeByValue(&head, 1);
    printf("Linked List after Deletion of 1: ");
    printList(head);
    return 0;
}

Important Information:

• Time Complexity: O(n) for deleting a node by value.
• Space Complexity: O(1).

Traversal:

Traversal involves iterating through the list by moving from the head to the last node.

Example:

PrintList function in the above example.

Important Information:

• Time Complexity: O(n), where n is the number of elements.
• Space Complexity: O(1).

Stacks

Insertion (Push):

Push adds an element to the top of the stack.

Example:

#include <stdio.h>
#define MAX 100

int top = -1;
int stack[MAX];

void push(int x) {
    if (top >= MAX - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack[++top] = x;
}

void printStack() {
    if (top == -1) {
        printf("Stack is empty!\n");
        return;
    }
    for (int i = top; i >= 0; i--)
        printf("%d ", stack[i]);
    printf("\n");
}

int main() {
    push(10);
    push(20);
    push(30);

    printStack();
    return 0;
}

Important Information:

• Time Complexity: O(1).
• Space Complexity: O(MAX) when initializing the stack.

Deletion (Pop):

Pop removes an element from the top of the stack.

Example:

void pop() {
    if (top < 0) {
        printf("Stack Underflow\n");
        return;
    }
    printf("%d popped from stack\n", stack[top--]);
}

Important Information:

• Time Complexity: O(1).

Traversal:

Displaying the elements in the stack from top to bottom.

Important Information:

• Time Complexity: O(n).

Queues

Queues involve inserting elements at one end and deleting elements from the other end.

Insertion (Enqueue):

Adds an element at the rear of the queue.

Example:

#include <stdio.h>
#define MAX 100

int front = -1, rear = -1;
int queue[MAX];

void enqueue(int item) {
    if (rear == MAX - 1) {
        printf("Queue Overflow\n");
        return;
    }
    if (front == -1)
        front = 0;
    rear++;
    queue[rear] = item;
}

void printQueue() {
    if (front == -1) {
        printf("Queue is empty!\n");
        return;
    }
    printf("Printing queue:\n");
    for (int i = front; i <= rear; i++) {
        printf("%d ", queue[i]);
    }
    printf("\n");
}

Important Information:

• Time Complexity: O(1).

Deletion (Dequeue):

Removes an element from the front of the queue.

Example:

void dequeue() {
    if (front > rear || front == -1) {
        printf("Queue is empty!\n");
        return;
    } else {
        printf("%d dequeued from queue\n", queue[front]);
        front++;
    }
}

Important Information:

• Time Complexity: O(1).

Traversal:

Iterate through the queue from front to rear.

Important Information:

• Time Complexity: O(n).

Trees

For binary search trees, we perform different types of insertions and deletions.

Insertion:

Insert a node as per BST rules: smaller values go to the left, larger values to the right.

Example:

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

struct TNode {
    int data;
    struct TNode* left, *right;
};

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

struct TNode* insert(struct TNode* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }
    if (data < root->data)
        root->left = insert(root->left, data);
    else
        root->right = insert(root->right, data);
    return root;
}

Important Information:

• Time Complexity: O(h), where h is the height of the tree.

Deletion:

Remove a node based on value. Handle three cases: no children, one child, two children.

Example:

struct TNode* minValueNode(struct TNode* node) {
    struct TNode* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

struct TNode* deleteNode(struct TNode* root, int data) {
    if (root == NULL)
        return root;
    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        if (root->left == NULL) {
            struct TNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TNode* temp = root->left;
            free(root);
            return temp;
        }

        struct TNode* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Important Information:

• Time Complexity: O(h), where h is the height of the tree.

Traversal:

Visit nodes in a systematic manner: Inorder, Preorder, Postorder.

Example (Inorder Traversal):

void inorder(struct TNode* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

Important Information:

• Time Complexity: O(n), where n is the number of nodes.
• Space Complexity: O(h) due to recursive call stack.

Graphs

Graphs can be represented using adjacency lists or matrices.

Insertion:

Adding an edge between two nodes.

Example (Adjacency List Representation):

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

struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

struct AdjList {
    struct AdjListNode* head;
};

struct Graph {
    int V;
    struct AdjList* array;
};

struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = 
     (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;

    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->V; ++v) {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("Adjacency list of vertex %d\n head ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

Important Information:

• Time Complexity: O(1) for adding an edge in an adjacency list.

Deletion:

Removing an edge between two nodes.

Example:

// Function to delete an edge
void deleteEdge(struct Graph* graph, int src, int dest) {
    struct AdjListNode* temp = graph->array[src].head;
    struct AdjListNode* prev = NULL;

    // Traverse adjacency list of src to find and delete destination 
    while (temp && temp->dest != dest) {
        prev = temp;
        temp = temp->next;
    }
    if (temp) { 
        if (prev) {
            prev->next = temp->next;
        } else {
            graph->array[src].head = temp->next;
        }

        free(temp);
    }

    // Traverse adjacency list of dest to find and delete source
    temp = graph->array[dest].head;
    prev = NULL;

    while (temp && temp->dest != src) {
        prev = temp;
        temp = temp->next;
    }
    if (temp) {
        if (prev) {
            prev->next = temp->next;
        } else {
            graph->array[dest].head = temp->next;
        }

        free(temp);
    }
}

Important Information:

• Time Complexity: O(E/V), where E is edges and V is vertices.

Traversal:

Common methods are Depth First Search (DFS) and Breadth First Search (BFS).

Example (DFS):

Use a recursive helper function.