Fundamental Data Structures and C Programming Concepts

1. Understanding Arrays and Their Types

An array is a collection of elements of the same data type stored in contiguous memory locations. It is used to store multiple values in a single variable and can be accessed using index numbers. The indexing in an array starts from 0. Arrays help manage and process data efficiently, especially when dealing with large volumes of similar data.

Types of Arrays Based on Dimensions

1. One-Dimensional Array: It stores data in a linear list format.
2. Multi-Dimensional Array: It stores data in matrix form (like 2D, 3D arrays), which is useful in applications like image processing and tables.

Types of Arrays Based on Memory Allocation

1. Static Array: The size of the array is fixed at compile-time. Memory is allocated when the program starts. For example: int a[10];
2. Dynamic Array: The size of the array is decided at runtime using pointers and functions like malloc() or calloc(). This allows flexible memory use. Example:

   int *arr;
   arr = (int*)malloc(n * sizeof(int));

C Program: Sum of Static Array Elements

Here is a program to input 'n' numbers in a static array and display their sum:

#include <stdio.h>
int main() {
    int n, i, sum = 0;
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    int arr[n]; // Static array
    printf("Enter %d numbers:\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        sum += arr[i];
    }
    printf("Sum of elements = %d", sum);
    return 0;
}

If dynamic memory is required, we can use the malloc() function from <stdlib.h> instead of a static array.

2. Functions: Call by Value vs. Call by Reference

A function is a block of code in C that performs a specific task. It helps in breaking down a large program into smaller, manageable parts. Using functions avoids code repetition, improves readability, and makes debugging easier. Functions can be either built-in (like printf, scanf) or user-defined.

Syntax of Function Definition

return_type function_name(parameter_list) {
    // body of function
}

Example:

int add(int a, int b) {
    return a + b;
}

Call by Value

In call by value, a copy of the actual value is passed to the function. Any change made inside the function does not affect the original variable.

Example:

void change(int x) {
    x = x + 10;
}
int main() {
    int a = 5;
    change(a);
    printf("%d", a); // Output will be 5, original 'a' is not changed
}

Call by Reference

In call by reference, the address of the variable is passed. Thus, any changes made inside the function directly affect the original variable.

Example:

void change(int *x) {
    *x = *x + 10;
}
int main() {
    int a = 5;
    change(&a);
    printf("%d", a); // Output will be 15, because value at address is changed
}

The main difference is that call by value works on copies (safe but doesn't affect the original), while call by reference works on the original data through pointers (risky but efficient when updates are needed).

3. Structures and Arrays of Structures in C

A structure in C is a user-defined data type that allows grouping of variables of different data types under one name. It is used when we want to store related information together but of different types. Structures are very useful in real-life applications like storing student records, employee details, etc.

Syntax of Structure

struct structure_name {
    data_type member1;
    data_type member2; // Can add more members…
};

Example:

struct Student {
    int roll;
    char name[50];
    float marks;
};

Array of Structures

An array of structures is used when we want to store data of multiple entities (like multiple students) using the same structure format. It works like an array, but each element is a full structure.

C Program: Demonstrate Array of Structure

#include <stdio.h>

struct Student {
    int roll;
    char name[50];
    float marks;
};

int main() {
    int n, i;
    printf("Enter number of students: ");
    scanf("%d", &n);

    struct Student s[n]; // array of structure

    for(i = 0; i < n; i++) {
        printf("\nEnter details for student %d:\n", i + 1);
        printf("Roll No: ");
        scanf("%d", &s[i].roll);
        printf("Name: ");
        scanf("%s", s[i].name);
        printf("Marks: ");
        scanf("%f", &s[i].marks);
    }

    printf("\n--- Student Details ---\n");
    for(i = 0; i < n; i++) {
        printf("Roll: %d, Name: %s, Marks: %.2f\n", s[i].roll, s[i].name, s[i].marks);
    }
    return 0;
}

This program uses an array of structures to store and display details of n students. Each element of the array s[i] holds one student's full information.

4. Recursion vs. Looping: Key Differences

Recursion is when a function calls itself to solve smaller parts of a problem. It requires a base condition to stop calling itself.

Looping repeats a block of code using for, while, or do-while until a condition becomes false.

Recursion Example (Factorial)

int fact(int n) {
    if(n == 0)
        return 1;
    else
        return n * fact(n - 1);
}

Looping Example (Factorial)

int fact = 1;
for(int i = 1; i <= N; i++) { // Assuming N is the number
    fact *= i;
}

Summary of Differences

Recursion uses function calls and is useful for problems like trees or backtracking, often leading to cleaner code for complex problems. However, looping is better for performance and generally uses less memory (as it avoids the overhead of multiple function calls on the stack).

5. Linked Lists: Definition and Types

A linked list is a linear data structure where each element (called a node) contains two parts: data and a pointer to the next node. Unlike arrays, linked lists do not store data in contiguous memory locations. They allow dynamic memory allocation, making insertion and deletion easier.

Node Structure Definition

Each node is defined using a self-referential structure:

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

Types of Linked Lists

1. Singly Linked List: Each node points only to the next node. The last node’s pointer is NULL.

   Example: [10|*] → [20|*] → [30|NULL]

2. Doubly Linked List: Each node has two pointers – one to the next node and one to the previous node.

   Example: NULL ← [10|*|*] ↔ [20|*|*] ↔ [30|*|NULL]

3. Circular Linked List: In this list, the last node points back to the first node, forming a circle.

   Example: [10|*] → [20|*] → [30|*] → (back to first node)

4. Circular Doubly Linked List: It is like a doubly linked list, but the last node points back to the first, and the first node points to the last.

6. Essential Operations in Linked Lists

In a linked list, several operations can be performed to manage the nodes. Each operation handles the list by accessing or modifying the data and next pointers of the nodes.

1. Traversal

   Traversal means visiting each node of the linked list from the beginning to the end using a loop. It helps in displaying the data stored in all nodes.

   Example:

   struct Node* temp = head;
   while(temp != NULL) {
       printf("%d ", temp->data);
       temp = temp->next;
   }

2. Insertion

   Insertion means adding a new node. It can be done at the beginning, middle, or end. A new node is created, and its pointer is adjusted to link it properly with the list.

   Insert at Beginning Example:

   newNode->next = head;
   head = newNode;

3. Deletion

   Deletion removes a node from the list. Like insertion, it can be from the start, middle, or end. After deleting, pointers must be updated to maintain the structure.

   Delete First Node Example:

   struct Node* temp = head;
   head = head->next;
   free(temp);

4. Updation

   Updation means changing the data of a node at a specific position. We traverse to that node and simply change the data part.

   Example:

   temp->data = newValue;

5. Searching

   Searching finds whether a value exists in the list. We traverse through each node and compare its data.

   Example:

   while(temp != NULL) {
       if(temp->data == key) {
           // found
       }
       temp = temp->next;
   }

7. Stack Data Structure: LIFO Principle

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means the last element inserted is the first one to be removed. Think of it like a pile of plates – you always remove the top plate first.

A stack can be implemented using arrays or linked lists. It mainly supports two basic operations: push() to insert an element and pop() to remove the top element.

The push() Operation

push() is used to insert an element at the top of the stack.

Algorithm (using array):

1. Check if the stack is full (top == size - 1).
2. If not full, increment top.
3. Add the new element at stack[top].

Example:

if(top == size - 1)
    printf("Stack Overflow");
else {
    top++;
    stack[top] = value;
}

The pop() Operation

pop() removes the top element from the stack.

Algorithm:

1. Check if the stack is empty (top == -1).
2. If not empty, remove and return the element at stack[top].
3. Decrement top.

Example:

if(top == -1)
    printf("Stack Underflow");
else {
    value = stack[top];
    top--;
}

Stacks are widely used in expression evaluation, backtracking, recursion, and undo operations in editors.

8. Queue Data Structure: FIFO Principle

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. The element inserted first will be removed first, just like a line of people waiting for a service. It has two main operations:

• enqueue(): To add an element at the rear.
• dequeue(): To remove an element from the front.

The enqueue() Operation

Algorithm (using array):

1. Check if the queue is full (rear == size - 1).
2. If not full, increment rear.
3. Insert the new element at queue[rear].

Example:

if(rear == size - 1)
    printf("Queue Overflow");
else {
    rear++;
    queue[rear] = value;
}

Note: A complete queue implementation also requires managing the front pointer for dequeue operations, which typically involves checking for front == -1 or front > rear for emptiness.