Arrays, Strings, Linked Lists, Stacks, Queues & Pointers in C: DSA Fundamentals with Code Examples

1. What is an array in C?

An array is a fixed-size, ordered collection of elements of the same data type, stored in contiguous memory locations, accessed by an index starting at 0.

2. How do you declare an array in C?

Declare an array by specifying the data type, name, and size. Example:

int arr[5]; // Declares an array of 5 integers
int arr[5] = {1, 2, 3, 4, 5}; // Initialized array
      

3. How do you traverse an array in C?

Traversal involves accessing each element using a loop. Example:

#include 

void traverse(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    traverse(arr, 5); // Output: 1 2 3 4 5
    return 0;
}
      

4. How do you insert an element into an array?

Shift elements to the right to make space at the desired index, then insert the new element. Example:

#include 

void insert(int arr[], int *n, int pos, int value) {
    if (*n >= pos && pos >= 0) {
        for (int i = *n; i > pos; i--) { // Shift elements
            arr[i] = arr[i - 1];
        }
        arr[pos] = value; // Insert value
        (*n)++; // Increase size
    }
}

int main() {
    int arr[10] = {1, 2, 3, 4, 5};
    int n = 5;
    insert(arr, &n, 2, 99); // Insert 99 at index 2
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]); // Output: 1 2 99 3 4 5
    }
    return 0;
}
      

5. How do you delete an element from an array?

Shift elements to the left to fill the gap at the desired index. Example:

#include 

void delete(int arr[], int *n, int pos) {
    if (pos >= 0 && pos < *n) {
        for (int i = pos; i < *n - 1; i++) { // Shift elements
            arr[i] = arr[i + 1];
        }
        (*n)--; // Decrease size
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    delete(arr, &n, 2); // Delete element at index 2
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]); // Output: 1 2 4 5
    }
    return 0;
}
      

6. What are the advantages and disadvantages of arrays?

• Advantages: Fast access (O(1)), simple to implement, cache-friendly due to contiguous memory.
• Disadvantages: Fixed size, costly insertion/deletion (O(n)), no dynamic resizing.

7. What is the time complexity of array operations?

• Access: O(1)
• Traversal: O(n)
• Insertion/Deletion: O(n) (due to shifting elements)

8. What is a string in C?

A string in C is an array of characters terminated by a null character (\0). Example: char str[] = "Hello";.

9. How do you declare and initialize a string in C?

Declare as a char array or pointer, initialized with a string literal or character-by-character. Example:

char str1[] = "Hello"; // Array
char *str2 = "World"; // Pointer (read-only)
char str3[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
      

10. What are common string operations in C?

Common operations (using <string.h>):

• strlen(str): Returns string length (excluding \0).
• strcpy(dest, src): Copies source to destination.
• strcat(dest, src): Concatenates source to destination.
• strcmp(str1, str2): Compares two strings (returns 0 if equal).
• Custom operations: Reverse, convert case, etc.

11. Can you give an example of string manipulation in C?

Example: Reverse a string.

#include 
#include 

void reverseString(char str[]) {
    int n = strlen(str);
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}

int main() {
    char str[] = "Hello";
    reverseString(str);
    printf("%s\n", str); // Output: olleH
    return 0;
}
      

12. What are the challenges with strings in C?

• No built-in string type; relies on char arrays.
• Manual null-termination management.
• Risk of buffer overflow with improper handling.
• Immutable string literals when using pointers.

13. What is the time complexity of string operations?

• Length (strlen): O(n)
• Copy/Concatenate (strcpy, strcat): O(n)
• Compare (strcmp): O(n)
• Custom operations (e.g., reverse): O(n)

14. What is a linked list?

A linked list is a dynamic data structure where nodes (containing data and a pointer to the next node) are linked sequentially. Unlike arrays, nodes are not stored contiguously.

15. What is a singly linked list?

A singly linked list has nodes with a data element and a pointer to the next node. Example:

#include 
#include 

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

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

int main() {
    struct Node* head = malloc(sizeof(struct Node));
    head->data = 1;
    head->next = malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->next = NULL;
    printList(head); // Output: 1 2
    free(head->next);
    free(head);
    return 0;
}
      

16. What is a doubly linked list?

A doubly linked list has nodes with pointers to both the next and previous nodes, allowing bidirectional traversal. Example structure:

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

17. What is a circular linked list?

A circular linked list is a singly or doubly linked list where the last node points back to the first node, forming a loop. Example (singly circular):

#include 
#include 

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

void printCircularList(struct Node* head) {
    if (head == NULL) return;
    struct Node* temp = head;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

int main() {
    struct Node* head = malloc(sizeof(struct Node));
    head->data = 1;
    head->next = malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->next = head; // Circular link
    printCircularList(head); // Output: 1 2
    free(head->next);
    free(head);
    return 0;
}
      

18. What are the operations on linked lists?

• Insertion: At beginning, end, or specific position (O(1) at head, O(n) elsewhere).
• Deletion: Remove a node (O(1) at head, O(n) elsewhere).
• Traversal: Visit all nodes (O(n)).
• Search: Find a node by value (O(n)).

19. What are the advantages and disadvantages of linked lists?

• Advantages: Dynamic size, efficient insertion/deletion at known positions.
• Disadvantages: No random access (O(n) for access), extra memory for pointers, not cache-friendly.

20. What is the time complexity of linked list operations?

• Access/Search: O(n)
• Insertion/Deletion at head: O(1)
• Insertion/Deletion at end or specific position: O(n) (needs traversal)

21. What is a stack?

A stack is a linear data structure following the Last-In-First-Out (LIFO) principle, where elements are added (pushed) and removed (popped) from the top.

22. How do you implement a stack in C?

Implement using an array or linked list. Example (array-based):

#include 
#define MAX 100

struct Stack {
    int arr[MAX];
    int top;
};

void init(struct Stack* s) {
    s->top = -1;
}

void push(struct Stack* s, int value) {
    if (s->top < MAX - 1) {
        s->arr[++(s->top)] = value;
    }
}

int pop(struct Stack* s) {
    if (s->top >= 0) {
        return s->arr[(s->top)--];
    }
    return -1; // Stack empty
}

int main() {
    struct Stack s;
    init(&s);
    push(&s, 1);
    push(&s, 2);
    printf("%d\n", pop(&s)); // Output: 2
    printf("%d\n", pop(&s)); // Output: 1
    return 0;
}
      

23. What are the applications of stacks?

• Function call management (call stack).
• Undo/redo in editors.
• Expression evaluation (e.g., postfix expressions).
• Backtracking algorithms (e.g., maze solving).
• Browser history (back/forward navigation).

24. What is the time complexity of stack operations?

• Push/Pop: O(1)
• Peek (get top element): O(1)
• Search: O(n) (not typical for stacks)

25. What are the advantages and disadvantages of stacks?

• Advantages: Simple, fast for LIFO operations.
• Disadvantages: Limited access (only top), fixed size in array-based implementation.

26. What is a queue?

A queue is a linear data structure following the First-In-First-Out (FIFO) principle, where elements are added (enqueued) at the rear and removed (dequeued) from the front.

27. How do you implement a simple queue in C?

Example (array-based simple queue):

#include 
#define MAX 100

struct Queue {
    int arr[MAX];
    int front, rear;
};

void init(struct Queue* q) {
    q->front = q->rear = -1;
}

void enqueue(struct Queue* q, int value) {
    if (q->rear < MAX - 1) {
        if (q->front == -1) q->front = 0;
        q->arr[++(q->rear)] = value;
    }
}

int dequeue(struct Queue* q) {
    if (q->front <= q->rear && q->front != -1) {
        return q->arr[(q->front)++];
    }
    return -1; // Queue empty
}

int main() {
    struct Queue q;
    init(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    printf("%d\n", dequeue(&q)); // Output: 1
    printf("%d\n", dequeue(&q)); // Output: 2
    return 0;
}
      

28. What is a circular queue?

A circular queue connects the rear to the front, reusing empty spaces in an array to avoid overflow. Example:

#include 
#define MAX 5

struct CircularQueue {
    int arr[MAX];
    int front, rear;
};

void init(struct CircularQueue* q) {
    q->front = q->rear = -1;
}

void enqueue(struct CircularQueue* q, int value) {
    if ((q->rear + 1) % MAX == q->front) return; // Full
    if (q->front == -1) q->front = 0;
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = value;
}

int dequeue(struct CircularQueue* q) {
    if (q->front == -1) return -1; // Empty
    int value = q->arr[q->front];
    if (q->front == q->rear) q->front = q->rear = -1;
    else q->front = (q->front + 1) % MAX;
    return value;
}

int main() {
    struct CircularQueue q;
    init(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    printf("%d\n", dequeue(&q)); // Output: 1
    return 0;
}
      

29. What is a priority queue?

A priority queue assigns priorities to elements, dequeuing the highest-priority element first. It can be implemented using arrays, linked lists, or heaps (heap is most efficient).

30. What are the applications of queues?

• Task scheduling (e.g., CPU processes).
• Print job management.
• Breadth-first search in graphs.
• Buffering in streaming or networking.
• Priority queues for Dijkstra's algorithm.

31. What is the time complexity of queue operations?

Simple/Circular Queue (array-based):

• Enqueue/Dequeue: O(1)
• Search: O(n)

Priority Queue (heap-based):

• Enqueue/Dequeue: O(log n)
• Peek: O(1)

32. What is a pointer in C?

A pointer is a variable that stores the memory address of another variable. It allows direct memory manipulation and is essential for dynamic data structures like linked lists.

33. How do you declare and use a pointer in C?

Declare with *, assign an address with &, and dereference with *. Example:

#include 

int main() {
    int x = 10;
    int* ptr = &x; // Pointer to x
    printf("%d\n", *ptr); // Output: 10 (dereference)
    *ptr = 20; // Change x via pointer
    printf("%d\n", x); // Output: 20
    return 0;
}
      

34. What is dynamic memory allocation in C?

Dynamic memory allocation uses malloc, calloc, realloc, and free to manage memory at runtime. Example:

#include 
#include 

int main() {
    int* arr = (int*)malloc(5 * sizeof(int)); // Allocate for 5 integers
    for (int i = 0; i < 5; i++) {
        arr[i] = i + 1;
    }
    printf("%d\n", arr[0]); // Output: 1
    free(arr); // Deallocate memory
    return 0;
}
      

35. What are common pointer-related errors?

• Dangling pointers: Accessing freed memory.
• Null pointer dereference: Using uninitialized pointers.
• Memory leaks: Forgetting to free allocated memory.
• Buffer overflow: Writing beyond allocated memory.

36. How do pointers relate to data structures?

Pointers enable dynamic structures like linked lists, stacks, and queues by linking nodes or managing memory allocation for arrays and trees.

37. What is the difference between malloc and calloc?

• malloc(size): Allocates uninitialized memory.
• calloc(n, size): Allocates memory for n elements, initializes to zero.

38. How do you avoid memory leaks in C?

Always call free() for dynamically allocated memory, avoid losing pointers to allocated memory, and use tools like Valgrind to detect leaks.

39. What is the difference between stack and heap memory?

• Stack: Fixed-size, used for local variables and function calls, automatically managed.
• Heap: Dynamic, used for malloc/calloc, manually managed with free.