Introduction to Data Structures

A data structure fundamentally consists of two components: data and structure.

Data encompasses all information processed by computers—numeric values, user records (names, ages, profiles), or multimedia content (text, images, videos). Structure defines how this data is organized. Without proper structure, searching through large datasets becomes inefficient. Consider finding a specific sheep in an unordered flock versus locating sheep #10 in a numbered sequence. Structure provides the organizational scheme that makes data manageable and accessible.

Definition: A data structure is a specific way of organizing, storing, and managing data to enable efficient access and modification.

Understanding Sequential Lists

A sequential list stores elements in a contiguous memory block, maintaining a logical sequence. It represents a physical implementation of a linear list.

A linear list is a finite sequence of $n$ data elements sharing the same characteristics. While linear lists are logical linear (forming a continuous line), their physical storage may vary. Sequential lists specifically utilize contiguous memory allocation (arrays), enabling $O(1)$ random access but requiring $O(n)$ time for insertions and deletions at arbitrary positions (except at the end).

Static vs. Dynamic Sequential Lists

Sequential lists are categorized based on memory allocation strategies:

Static Sequential Lists

Utilize fixed-size arrays defined at compile time. The primary limitation is inflexibility: predetermined capacity either wastes memory (if too large) or causes overflow (if too small).

Dynamic Sequential Lists

Allocate memory dynamically during runtime using pointers and realloc. This approach expands capacity on demand—typically doubling when full—eliminating both overflow risks and excessive memory waste.

Implementation: Dynamic Sequential List

The following implementation demonstrates a complete dynamic array structure with encapsulated memory management, providing $O(1)$ amortized insertion at the end and safe bounds checking.

Core Data Structure

typedef int ElemType;

typedef struct {
    ElemType* elements;  // Pointer to dynamic array
    int count;           // Current number of elements
    int capacity;        // Total allocated capacity
} SeqList;

Memory Management

Initialization prepares an empty list with zero capacity, while Destruction releases allocated memory to prevent leaks. An internal capacity check automatically resizes the array (doubling strategy) when full, ensuring amortized constant-time appends.

Operation Complexity

• PushBack (Append): $O(1)$ amortized
• PushFront (Prepend): $O(n)$ — requires shifting all existing elements
• Insert at position: $O(n)$ — shifts elements from position onward
• PopBack: $O(1)$ — simply decrements count
• PopFront: $O(n)$ — shifts all elements left
• Erase at position: $O(n)$ — shifts subsequent elements left
• Find (Linear Search): $O(n)$

Complete Source Code

Header File (SeqList.h)

#ifndef SEQLIST_H
#define SEQLIST_H

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

typedef int ElemType;

typedef struct {
    ElemType* elements;
    int count;
    int capacity;
} SeqList;

/* Lifecycle Management */
void SeqListInit(SeqList* list);
void SeqListDestroy(SeqList* list);

/* Utility */
void SeqListPrint(const SeqList* list);

/* Insertion Operations */
void SeqListPushBack(SeqList* list, ElemType value);
void SeqListPushFront(SeqList* list, ElemType value);
void SeqListInsert(SeqList* list, int position, ElemType value);

/* Deletion Operations */
void SeqListPopBack(SeqList* list);
void SeqListPopFront(SeqList* list);
void SeqListErase(SeqList* list, int position);

/* Search */
int SeqListFind(const SeqList* list, ElemType value);

#endif

Implementation (SeqList.c)

#include "SeqList.h"

/* Internal helper: Ensures sufficient capacity, doubling when needed */
static void EnsureCapacity(SeqList* list) {
    if (list->count >= list->capacity) {
        int newCapacity = (list->capacity == 0) ? 4 : list->capacity * 2;
        ElemType* newElements = (ElemType*)realloc(list->elements, 
                                                    newCapacity * sizeof(ElemType));
        if (newElements == NULL) {
            perror("Memory reallocation failed");
            exit(EXIT_FAILURE);
        }
        list->elements = newElements;
        list->capacity = newCapacity;
    }
}

void SeqListInit(SeqList* list) {
    assert(list != NULL);
    list->elements = NULL;
    list->count = 0;
    list->capacity = 0;
}

void SeqListDestroy(SeqList* list) {
    assert(list != NULL);
    free(list->elements);
    list->elements = NULL;
    list->count = 0;
    list->capacity = 0;
}

void SeqListPrint(const SeqList* list) {
    assert(list != NULL);
    for (int i = 0; i < list->count; i++) {
        printf("%d ", list->elements[i]);
    }
    printf("\n");
}

void SeqListPushBack(SeqList* list, ElemType value) {
    assert(list != NULL);
    EnsureCapacity(list);
    list->elements[list->count++] = value;
}

void SeqListPushFront(SeqList* list, ElemType value) {
    assert(list != NULL);
    EnsureCapacity(list);
    /* Shift elements right to make room at index 0 */
    for (int i = list->count; i > 0; i--) {
        list->elements[i] = list->elements[i - 1];
    }
    list->elements[0] = value;
    list->count++;
}

void SeqListPopBack(SeqList* list) {
    assert(list != NULL);
    assert(list->count > 0);
    list->count--;
}

void SeqListPopFront(SeqList* list) {
    assert(list != NULL);
    assert(list->count > 0);
    /* Shift elements left to fill index 0 */
    for (int i = 0; i < list->count - 1; i++) {
        list->elements[i] = list->elements[i + 1];
    }
    list->count--;
}

void SeqListInsert(SeqList* list, int position, ElemType value) {
    assert(list != NULL);
    assert(position >= 0 && position <= list->count);
    EnsureCapacity(list);
    /* Shift elements from position onward to the right */
    for (int i = list->count; i > position; i--) {
        list->elements[i] = list->elements[i - 1];
    }
    list->elements[position] = value;
    list->count++;
}

void SeqListErase(SeqList* list, int position) {
    assert(list != NULL);
    assert(position >= 0 && position < list->count);
    /* Shift elements from position onward to the left */
    for (int i = position; i < list->count - 1; i++) {
        list->elements[i] = list->elements[i + 1];
    }
    list->count--;
}

int SeqListFind(const SeqList* list, ElemType value) {
    assert(list != NULL);
    for (int i = 0; i < list->count; i++) {
        if (list->elements[i] == value) {
            return i;
        }
    }
    return -1;  /* Not found */
}

Test Program (main.c)

#include "SeqList.h"

void TestSequentialList() {
    SeqList list;
    SeqListInit(&list);
    
    /* Append elements */
    SeqListPushBack(&list, 10);
    SeqListPushBack(&list, 20);
    SeqListPushBack(&list, 30);
    SeqListPushBack(&list, 40);
    printf("After PushBack: ");
    SeqListPrint(&list);
    
    /* Prepend element */
    SeqListPushFront(&list, 5);
    printf("After PushFront: ");
    SeqListPrint(&list);
    
    /* Remove from end */
    SeqListPopBack(&list);
    printf("After PopBack: ");
    SeqListPrint(&list);
    
    /* Remove from front */
    SeqListPopFront(&list);
    printf("After PopFront: ");
    SeqListPrint(&list);
    
    /* Insert at specific position */
    SeqListInsert(&list, 1, 99);
    printf("After Insert at 1: ");
    SeqListPrint(&list);
    
    /* Erase from specific position */
    SeqListErase(&list, 1);
    printf("After Erase at 1: ");
    SeqListPrint(&list);
    
    /* Search operation */
    int idx = SeqListFind(&list, 30);
    if (idx != -1) {
        printf("Element 30 found at index: %d\n", idx);
    }
    
    SeqListDestroy(&list);
}

int main() {
    TestSequentialList();
    return 0;
}

This implementation provides a robust, reusable dynamic array suitable for applications requiring fast random access and automatic memory management, serving as a foundation for more complex data structures like stacks, queues, and heaps.