C Programming Data Structures Implementation Using Arrays And Linked Lists Complete Guide

Last Update:2025-06-23T00:00:00 .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION. 9 mins read Difficulty-Level: beginner

Understanding the Core Concepts of C Programming data structures Implementation using Arrays and Linked Lists

C Programming Data Structures Implementation using Arrays and Linked Lists

Arrays

An array in C is a collection of elements of the same data type stored in contiguous memory locations. Arrays provide a systematic way to access and manipulate data.

Characteristics of Arrays:

Fixed Size: The size of an array must be specified at the time of its declaration and cannot be changed during runtime.
Contiguous Memory: All elements are stored adjacently in memory, allowing for efficient random access.
Direct Access: Elements can be accessed directly using an index, which makes operations like getting, setting, and iterating over elements very fast.

Implementation Example:

#include <stdio.h>

int main() {
    int arr[5];  // Declare an integer array of size 5
    arr[0] = 10; // Set the first element to 10
    printf("First element: %d\n", arr[0]); // Output the first element
    for (int i = 0; i < 5; i++) {
        arr[i] = i * 10; // Initialize array elements
        printf("Element %d: %d\n", i, arr[i]); // Print each element
    }
    return 0;
}

Advantages:

Efficient Access: Quick access to elements using indexing.
Simplicity: Easy to declare and use.

Disadvantages:

Fixed Size: Cannot resize dynamically.
Wastage of Memory: If the array size is too large, it may lead to unused memory.

Linked Lists

A linked list is a linear data structure where elements, called nodes, are not stored in contiguous memory locations. Each node contains a data part and a reference (or link) to the next node in the sequence.

Types of Linked Lists:

Singly Linked List: Each node contains data and a pointer to the next node.
Doubly Linked List: Each node contains data, a pointer to the next node, and a pointer to the previous node.
Circular Linked List: The last node points back to the first node, forming a circular chain.

Characteristics of Linked Lists:

Dynamic Size: Nodes can be added or removed easily, which allows for dynamic memory allocation.
Non-Contiguous Memory: Nodes are scattered throughout memory, linked together through pointers.
Sequential Access: Elements can only be accessed sequentially, starting from the head node.

Implementation Example (Singly Linked List):

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

// Define the structure of a node
struct Node {
    int data;
    struct Node *next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to print the linked list
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = createNode(10); // Create the head node
    head->next = createNode(20);       // Add a second node
    head->next->next = createNode(30); // Add a third node
    printList(head);                   // Print the linked list
    return 0;
}

Advantages:

Dynamic Size: Can easily grow or shrink.
Memory Efficiency: Only the necessary memory is used for each node.

Disadvantages:

Inefficient Access: Accessing elements requires traversing from the head node.
Complexity: More complex to implement and manage compared to arrays.

Conclusion

Arrays and linked lists each have their unique strengths and weaknesses. Arrays are ideal for scenarios where data size is fixed and fast random access is required. Linked lists are more suitable for dynamic data where insertions and deletions are frequent and memory usage should be optimized. Understanding when to use each data structure is key to writing efficient C programs.

Online Code run

🔔 Note: Select your programming language to check or run code at

💻 Run Code Compiler

Step-by-Step Guide: How to Implement C Programming data structures Implementation using Arrays and Linked Lists

Data Structure 1: Stack

Using Arrays

Step-by-Step Example:

Define the Stack structure and constants:

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

#define MAX 5  // Maximum size of the stack

typedef struct {
    int items[MAX];
    int top;  
} Stack;

Initialize the Stack:

void initStack(Stack *s) {
    s->top = -1;  // Indicates the stack is empty
}

Check if the Stack is full:

int isFull(Stack *s) {
    return s->top == MAX - 1;
}

Check if the Stack is empty:

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

Push an item onto the Stack:

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack is full!\n");
    } else {
        s->items[++s->top] = value;
    }
}

Pop an item from the Stack:

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;  // Return some error code or value
    } else {
        return s->items[s->top--];  
    }
}

Display all elements in the Stack:

void displayStack(Stack *s) {
    for (int i = s->top; i >= 0; i--) {
        printf("%d\n", s->items[i]);
    }
}

Example usage:

int main() {
    Stack s;
    initStack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    displayStack(&s);  // Displays: 3 2 1
    printf("Popped item: %d\n", pop(&s));  // Pops 3, prints: Popped item: 3
    displayStack(&s);  // Displays: 2 1
    return 0;
}

Using Linked Lists

Step-by-Step Example:

Define the Node structure:

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

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

Define the Stack structure:

typedef struct {
    Node *top;
} LStack;

Initialize the Stack (linked list):

void initLStack(LStack *ls) {
    ls->top = NULL;
}

Check if the Stack is empty:

int LispEmpty(LStack *ls) {
    return ls->top == NULL;
}

Push an item onto the Stack:

void lPush(LStack *ls, int value) {
    Node *newNode = malloc(sizeof(Node));
    if (!newNode) {
        printf("Stack overflow!\n");
    } else {
        newNode->data = value;
        newNode->next = ls->top;
        ls->top = newNode;
    }
}

Pop an item from the Stack:

int lPop(LStack *ls) {
    Node *temp;
    int value;

    if (LispEmpty(ls)) {
        printf("Stack underflow!\n");
        return -1;
    } else {
        temp = ls->top;
        ls->top = ls->top->next;
        value = temp->data;
        free(temp);
        return value;
    }
}

Display all elements in the Stack:

void displayLStack(LStack *ls) {
    Node *current = ls->top;
    while (current) {
        printf("%d\n", current->data);
        current = current->next;
    }
}

Example usage:

int main() {
    LStack ls;
    initLStack(&ls);
    lPush(&ls, 1);
    lPush(&ls, 2);
    lPush(&ls, 3);
    displayLStack(&ls);  // Displays: 3 2 1
    printf("Popped item: %d\n", lPop(&ls));  // Pops 3, prints: Popped item: 3
    displayLStack(&ls);  // Displays: 2 1
    return 0;
}

Data Structure 2: Queue

Using Arrays

Step-by-Step Example:

Define the Queue structure and constants:

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

#define MAX 5  // Maximum size of the queue

typedef struct {
    int items[MAX];
    int front; 
    int rear;  
} Queue;

Initialize the Queue:

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

Check if the Queue is full:

int isQFull(Queue *q) {
    return q->rear == MAX - 1;
}

Check if the Queue is empty:

int isQEmpty(Queue *q) {
    return (q->front == -1 && q->rear == -1) || (q->front > q->rear);
}

Enqueue an item to the Queue:

void enqueue(Queue *q, int value) {
    if (isQFull(q)) {
        printf("Queue is full!\n");
    } else if (isQEmpty(q)) { // If Queue is empty, point fron and rear to 0 index
        q->front = 0;
        q->rear = 0;
        q->items[q->rear] = value;
    } else { // Otherwise just move front index and insert new value there
        q->items[++q->rear] = value;
    }
}

Dequeue an item from the Queue:

int dequeue(Queue *q) {
    int value = -1;
    if (isQEmpty(q)) {
        printf("Queue is empty!\n");
    } else if (q->front == q->rear) { // If only one element in Queue
        value = q->items[q->front];
        q->front = -1;
        q->rear = -1;
    } else { // Otherwise just move rear index and remove last element
        value = q->items[q->front++];
    }
    return value;
}

Display all elements in the Queue:

void displayQueue(Queue *q) {
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->items[i]);
    }
    printf("\n");
}

Example usage:

int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    displayQueue(&q);  // Displays: 1 2 3
    printf("Dequeued item: %d\n", dequeue(&q));  // Dequeues 1, prints: Dequeued item: 1
    displayQueue(&q);  // Displays: 2 3
    return 0;
}

Using Linked Lists

Step-by-Step Example:

Define the Node structure:

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

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

Define the Queue structure:

typedef struct {
    Node *head;
    Node *tail;  
} LQueue;

Initialize the Queue (linked list):

void initLQueue(LQueue *lq) {
    lq->head = NULL;
    lq->tail = NULL;
}

Check if the Queue is empty:

int lQIsEmpty(LQueue *lq) {
    return lq->head == NULL;
}

Enqueue an item to the Queue:

void lEnqueue(LQueue *lq, int value) {
    Node *newNode = malloc(sizeof(Node));
    if (!newNode) {
        printf("Queue overflow!\n");
    } else {
        newNode->data = value;
        newNode->next = NULL;
        if (lQIsEmpty(lq)) {
            lq->head = lq->tail = newNode;
        } else {
            lq->tail->next = newNode;
            lq->tail = newNode;
        }
    }
}

Dequeue an item from the Queue:

int lDequeue(LQueue *lq) {
    Node *temp;
    int value;

    if (lQIsEmpty(lq)) {
        printf("Queue underflow!\n");
        return -1;
    } else {
        temp = lq->head;
        lq->head = lq->head->next;
        value = temp->data;
        free(temp);
        if (!lq->head)  // Make sure to set tail to NULL if head became NULL
            lq->tail = NULL;
        return value;
    }
}

Display all elements in the Queue:

void displayLQueue(LQueue *lq) {
    Node *current = lq->head;

    while (current) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

Example usage:

int main() {
    LQueue lq;
    initLQueue(&lq);
    lEnqueue(&lq, 1);
    lEnqueue(&lq, 2);
    lEnqueue(&lq, 3);
    displayLQueue(&lq);  // Displays: 1 2 3
    printf("Dequeued item: %d\n", lDequeue(&lq));  // Dequeues 1, prints: Dequeued item: 1
    displayLQueue(&lq);  // Displays: 2 3
    return 0;
}

Data Structure 3: Singly Linked List

Single Linked List

Step-by-Step Example:

Define the Node structure:

Top 10 Interview Questions & Answers on C Programming data structures Implementation using Arrays and Linked Lists

1. What are the main differences between arrays and linked lists in C?

Answer: Arrays are contiguous blocks of memory holding elements of the same type, allowing for direct access to elements via their index. They have a fixed size, defined at compile time. Linked lists, on the other hand, are sequences of elements (nodes) where each node points to the next node. They are dynamic in size, allowing for efficient insertions and deletions but require additional memory for pointers.

2. How do you implement a stack using an array in C?

Answer: To implement a stack using an array in C, you define an array to hold stack elements and use an integer index (let’s call it top) to indicate the top of the stack. Key operations include push, pop, and isEmpty. Here's a simple implementation:

#define MAX 100
int stack[MAX];
int top = -1;

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

int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}

int isEmpty() {
    return top == -1;
}

3. How do you implement a queue using a linked list in C?

Answer: In a queue implemented using a linked list, you maintain two pointers: front pointing to the first node, and rear to the last node. Adding an element (enqueue) involves appending it to the end (using the rear pointer), while removing an element (dequeue) involves removing it from the front (front pointer). Here's a simple implementation:

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

Node* front = NULL;
Node* rear = NULL;

void enqueue(int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = value;
    new_node->next = NULL;

    if (rear == NULL) {
        front = rear = new_node;
        return;
    }
    rear->next = new_node;
    rear = new_node;
}

void dequeue() {
    if (front == NULL) {
        printf("Queue is empty\n");
        return;
    }
    Node* temp = front;
    front = front->next;

    if (front == NULL) rear = NULL;

    free(temp);
}

4. Describe the advantages and disadvantages of using arrays to implement data structures.

Answer: Advantages:

Fast access to elements via indexing (constant time, O(1)).
Memory is contiguous, reducing cache misses.
Simplicity and readability.

Disadvantages:

Fixed size, memory allocation happens at compile time, and resizing can be inefficient.
Insertions and deletions within arrays can be costly (O(n) time complexity).

5. What are the pros and cons of using linked lists for data structure implementation?

Answer: Advantages:

Dynamic size; can grow and shrink as required.
Efficient insertions and deletions at arbitrary positions, especially considering node addresses (O(1) if the position is known).

Disadvantages:

Overhead of pointers (additional memory usage).
Slower access times (O(n)) for accessing elements.

6. How can circular linked lists be used to optimize certain operations?

Answer: Circular linked lists enhance some functionalities, particularly for operations that require wrapping around to the beginning after reaching the end. For example, they optimize:

Efficient rotation of elements (useful in round-robin scheduling).
Simplification of algorithms that involve loops and cyclic data structures.

7. Explain the difference between singly and doubly linked lists.

Answer: In a singly linked list, each element (node) has a pointer to the next node and no connection back to the previous one. Doubly linked list nodes, however, have two pointers: one to the next node and another pointing back to the previous node. This allows traversal in both directions and can make certain operations like backward deletion more efficient, at the expense of memory overhead.

8. How would you implement a resizable array in C?

Answer: A resizable array, often called a dynamic array, can be implemented using malloc and realloc. You start with an array of some size, and whenever the array gets full, you allocate a larger piece of memory using realloc and copy the data to the new array. Below is a simple example:

int *arr;
int size = 0, capacity = 1;

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

void add(int element) {
    if (size == capacity) {
        capacity *= 2;
        arr = (int*)realloc(arr, capacity * sizeof(int));
    }
    arr[size++] = element;
}

9. What is the difference in memory usage between arrays and linked lists?

Answer: Arrays use a single contiguous block of memory to store their elements. The size of the memory block is the sum of the sizes of all elements plus some space for metadata (if any, which is language/compiler-specific).

In contrast, linked lists allocate memory for each element separately (including space for pointers). Each node in a linked list is often spread out in memory, leading to higher overall memory usage due to fragmentation and overhead for pointers.

10. Can a linked list have dynamic memory allocation in C?

Answer: Yes, a linked list in C can be entirely dynamically allocated. This means that each node is created and managed using functions like malloc and free. As opposed to static memory allocation where node space is reserved at compile time, dynamic memory allocation allows the linked list’s size to change at runtime. This is a significant advantage of linked list over arrays for applications requiring managing memory efficiently with varying data size requirements.

C Programming Data Structures Implementation Using Arrays And Linked Lists Complete Guide