Data structures organize and store data in specific arrangements defining the relationships between elements. Linear structures establish a one-to-one sequential relationship among elements, encompassing arrays, linked lists, stacks, and queues.

Arrays

An array allocates a contiguous block of memory to hold a collection of identical data types. Elements are retrieved using zero-based indexing.

#include <stdio.h>

#define CAPACITY 5

int main() {
    int values[CAPACITY] = {10, 20, 30, 40, 50};
    
    printf("First item: %d\n", values[0]);
    printf("Third item: %d\n", values[2]);
    
    values[1] = 99;
    printf("Modified contents: ");
    for (int idx = 0; idx < CAPACITY; idx++) {
        printf("%d ", values[idx]);
    }
    puts("");
    return 0;
}

Advantages

• Constant time O(1) element lookup due to contiguous allocation.
• Straightforward implementation.

Disadvantages

• Static capacity requires predetermined sizing.
• Slow O(n) modifications (insertions/deletions) due to element shifting.

Use Cases

Situations demanding high-frequency lookups with minimal structural modifications and predictable memory requirements.

Linked Lists

Linked lists consist of independant nodes scattered in memory. Each node encapsulates a payload and a reference (pointer) to the subsequent node. Variations include singly, doubly, and circular configurations.

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

typedef struct ListItem {
    int value;
    struct ListItem* nextPtr;
} ListItem;

ListItem* construct_item(int val) {
    ListItem* freshItem = (ListItem*)malloc(sizeof(ListItem));
    freshItem->value = val;
    freshItem->nextPtr = NULL;
    return freshItem;
}

void attach_end(ListItem** headRef, int val) {
    ListItem* freshItem = construct_item(val);
    if (*headRef == NULL) {
        *headRef = freshItem;
        return;
    }
    ListItem* current = *headRef;
    while (current->nextPtr != NULL) {
        current = current->nextPtr;
    }
    current->nextPtr = freshItem;
}

void display(ListItem* node) {
    while (node != NULL) {
        printf("[%d] -> ", node->value);
        node = node->nextPtr;
    }
    printf("END\n");
}

void cleanup(ListItem* node) {
    ListItem* temp;
    while (node != NULL) {
        temp = node;
        node = node->nextPtr;
        free(temp);
    }
}

int main() {
    ListItem* start = NULL;
    attach_end(&start, 5);
    attach_end(&start, 10);
    attach_end(&start, 15);
    display(start);
    cleanup(start);
    return 0;
}

Advantages

• Elastic sizing allows runtime memory allocation.
• Rapid O(1) insertions and deletions by merely redirecting pointers.

Disadvantages

• Sequential O(n) traversal required for element access.
• Memory overhead from storing pointer references alongside data.

Use Cases

Environments with unpredictable data volumes, frequent structural alterations, and where direct indexing is unnecessary.

Stacks

A stack enforces a Last-In-First-Out (LIFO) discipline. Modifications are strict restricted to the top extremity of the structure.

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

#define LIMIT 100

typedef struct {
    int buffer[LIMIT];
    int topPos;
} LifoStack;

void initialize(LifoStack* s) {
    s->topPos = -1;
}

int check_empty(LifoStack* s) {
    return s->topPos == -1;
}

int check_full(LifoStack* s) {
    return s->topPos == LIMIT - 1;
}

void insert(LifoStack* s, int val) {
    if (check_full(s)) {
        printf("Stack limit reached\n");
        return;
    }
    s->buffer[++s->topPos] = val;
}

int remove_top(LifoStack* s) {
    if (check_empty(s)) {
        printf("Stack is vacant\n");
        return -1;
    }
    return s->buffer[s->topPos--];
}

int view_top(LifoStack* s) {
    if (check_empty(s)) {
        printf("No items in stack\n");
        return -1;
    }
    return s->buffer[s->topPos];
}

int main() {
    LifoStack myStack;
    initialize(&myStack);
    
    insert(&myStack, 100);
    insert(&myStack, 200);
    insert(&myStack, 300);
    
    printf("Top value: %d\n", view_top(&myStack));
    printf("Removed: %d\n", remove_top(&myStack));
    printf("New Top: %d\n", view_top(&myStack));
    
    return 0;
}

Advantages

• Uncomplicated operational logic confined to a single endpoint.
• Automated memory administration in typical implementations.

Disadvantages

• Prone to overflow if capacity bounds are exceeded.
• Inaccessible internal elements without popping upper layers.

Use Cases

Depth-first traversal algorithms, postfix expression evaluation, syntax validation (bracket pairing), undo mechanisms, and navigation history.

Queues

A queue operates on a First-In-First-Out (FIFO) principle. Elements enter at the rear and exit from the front.

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

#define MAX_BOUND 100

typedef struct {
    int storage[MAX_BOUND];
    int frontIdx;
    int backIdx;
    int count;
} FifoQueue;

void setup(FifoQueue* q) {
    q->frontIdx = 0;
    q->backIdx = -1;
    q->count = 0;
}

int queue_empty(FifoQueue* q) {
    return q->count == 0;
}

int queue_full(FifoQueue* q) {
    return q->count == MAX_BOUND;
}

void add_item(FifoQueue* q, int val) {
    if (queue_full(q)) {
        printf("Queue capacity exceeded\n");
        return;
    }
    q->backIdx = (q->backIdx + 1) % MAX_BOUND;
    q->storage[q->backIdx] = val;
    q->count++;
}

int remove_item(FifoQueue* q) {
    if (queue_empty(q)) {
        printf("Queue has no elements\n");
        return -1;
    }
    int frontVal = q->storage[q->frontIdx];
    q->frontIdx = (q->frontIdx + 1) % MAX_BOUND;
    q->count--;
    return frontVal;
}

int view_front(FifoQueue* q) {
    if (queue_empty(q)) {
        printf("Queue is vacant\n");
        return -1;
    }
    return q->storage[q->frontIdx];
}

int main() {
    FifoQueue myQueue;
    setup(&myQueue);
    
    add_item(&myQueue, 11);
    add_item(&myQueue, 22);
    add_item(&myQueue, 33);
    
    printf("Head value: %d\n", view_front(&myQueue));
    printf("Extracted: %d\n", remove_item(&myQueue));
    printf("New Head: %d\n", view_front(&myQueue));
    
    return 0;
}

Advatnages

• Guarantees sequential processing aligning with arrival time.
• Straightforward design focused on two endpoints.
• Adaptable resource handling.

Disadvantages

• Rigid capacity limits risk overflow conditions.
• Internal elements cannot be queried directly.

Use Cases

Process scheduling in operating systems, asynchronous message brokering, breadth-first graph traversal, producer-consumer buffering, and network packet sequencing.