Implementing a Dynamic Sequential List in C

Introduction too Linear Data Structures

A linear data structure is a finite sequence of elements with similar properties. This fundamental structure finds widespread application in practice, with common implementations including sequential lists, linked lists, stacks, queues, and strings. Logically, the structure is linear, representing a continuous sequence. However, its physical storage in memory may not be contiguous, typically employing either array-based or node-based (linked) storage schemes.

The Sequential List

A sequential list is a linear structure where elements are stored consecutively in a contiguous block of memory. It is commmonly implemented using an array, upon which operations for insertion, deletion, searching, and modification are performed.

Types of Sequential Lists

Sequential lists can be categorized into two types:

Static Sequential List: Uses a fixed-size array for element storage.
Dynamic Sequential List: Uses a dynamically allocated array for storage, allowing its capacity to adjust as needed.

Static lists are suitable only when the required data size is known in advance. A fixed array size can lead to wasted memory if too large or insufficient space if too small. Consequently, dynamic sequential lists, which allocate memory flexibly, are predominantly used in real-world applications.

Interface Design

The following header file defines the structure and function prototypes for managing a dynamic sequential list.

#pragma once

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

// Type definition for list elements
typedef int ListElementType;

typedef struct DynamicList {
    ListElementType* dataArray; // Pointer to dynamically allocated array
    int elementCount;          // Number of valid elements
    int totalCapacity;         // Current capacity of the array
} DList;

// Function prototypes for list management
void listInitialize(DList* list);
void listDestroy(DList* list);
void checkAndExpand(DList* list);
void displayList(DList* list);
void appendElement(DList* list, ListElementType value);
void prependElement(DList* list, ListElementType value);
void removeLast(DList* list);
void removeFirst(DList* list);
void insertAtPosition(DList* list, int pos, ListElementType value);
void eraseAtPosition(DList* list, int pos);
int locateElement(DList* list, ListElementType value);
void updateElement(DList* list, int pos, ListElementType value);

Function Implementations

Initialization and Cleanup

The initialization function allocates memory for the underlying array, while the destroy function releases it.

void listInitialize(DList* list) {
    list->dataArray = (ListElementType*)malloc(sizeof(ListElementType) * 4);
    if (list->dataArray == NULL) {
        perror("Memory allocation failed");
        return;
    }
    list->totalCapacity = 4;
    list->elementCount = 0;
}

void listDestroy(DList* list) {
    free(list->dataArray);
    list->dataArray = NULL;
    list->totalCapacity = 0;
    list->elementCount = 0;
}

Capacity Management

This function checks if the list is full and doubles its capacity when necessary.

void checkAndExpand(DList* list) {
    if (list->elementCount == list->totalCapacity) {
        ListElementType* temp = (ListElementType*)realloc(list->dataArray,
                                    sizeof(ListElementType) * list->totalCapacity * 2);
        if (temp == NULL) {
            perror("Memory reallocation failed");
            return;
        }
        list->dataArray = temp;
        list->totalCapacity *= 2;
    }
}

Display Function

Prints all current elemants in the list.

void displayList(DList* list) {
    for (int i = 0; i < list->elementCount; i++) {
        printf("%d ", list->dataArray[i]);
    }
    printf("\n");
}

Insertion Operations

Functions for adding elements at the end, beginning, or a specific position.

void appendElement(DList* list, ListElementType value) {
    checkAndExpand(list);
    list->dataArray[list->elementCount++] = value;
    // Could reuse: insertAtPosition(list, list->elementCount - 1, value);
}

void prependElement(DList* list, ListElementType value) {
    checkAndExpand(list);
    int currentEnd = list->elementCount - 1;
    while (currentEnd >= 0) {
        list->dataArray[currentEnd + 1] = list->dataArray[currentEnd];
        --currentEnd;
    }
    list->dataArray[0] = value;
    list->elementCount++;
    // Could reuse: insertAtPosition(list, 0, value);
}

void insertAtPosition(DList* list, int pos, ListElementType value) {
    assert(pos >= 0 && pos <= list->elementCount);
    checkAndExpand(list);
    int currentEnd = list->elementCount - 1;
    while (currentEnd >= pos) {
        list->dataArray[currentEnd + 1] = list->dataArray[currentEnd];
        --currentEnd;
    }
    list->dataArray[pos] = value;
    list->elementCount++;
}

Deletion Operations

Functions for removing elements from the end, beginning, or a specific position.

void removeLast(DList* list) {
    assert(list->elementCount > 0);
    list->elementCount--;
    // Could reuse: eraseAtPosition(list, list->elementCount - 1);
}

void removeFirst(DList* list) {
    assert(list->elementCount > 0);
    int startIndex = 1;
    while (startIndex < list->elementCount) {
        list->dataArray[startIndex - 1] = list->dataArray[startIndex];
        startIndex++;
    }
    list->elementCount--;
    // Could reuse: eraseAtPosition(list, 0);
}

void eraseAtPosition(DList* list, int pos) {
    assert(pos >= 0 && pos < list->elementCount);
    assert(list->elementCount > 0);
    int startIndex = pos + 1;
    while (startIndex < list->elementCount) {
        list->dataArray[startIndex - 1] = list->dataArray[startIndex];
        ++startIndex;
    }
    list->elementCount--;
}

Search and Modify

int locateElement(DList* list, ListElementType value) {
    for (int i = 0; i < list->elementCount; i++) {
        if (list->dataArray[i] == value) {
            return i;
        }
    }
    return -1;
}

void updateElement(DList* list, int pos, ListElementType value) {
    assert(pos >= 0 && pos < list->elementCount);
    list->dataArray[pos] = value;
}

Complete Source Code

Header File (DynamicList.h)

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int ListElementType;
typedef struct DynamicList {
    ListElementType* dataArray;
    int elementCount;
    int totalCapacity;
} DList;

void listInitialize(DList* list);
void listDestroy(DList* list);
void checkAndExpand(DList* list);
void displayList(DList* list);
void appendElement(DList* list, ListElementType value);
void prependElement(DList* list, ListElementType value);
void removeLast(DList* list);
void removeFirst(DList* list);
void insertAtPosition(DList* list, int pos, ListElementType value);
void eraseAtPosition(DList* list, int pos);
int locateElement(DList* list, ListElementType value);
void updateElement(DList* list, int pos, ListElementType value);

Implementation File (DynamicList.c)

#include "DynamicList.h"

void listInitialize(DList* list) {
    list->dataArray = (ListElementType*)malloc(sizeof(ListElementType) * 4);
    if (list->dataArray == NULL) {
        perror("Memory allocation failed");
        return;
    }
    list->totalCapacity = 4;
    list->elementCount = 0;
}

void listDestroy(DList* list) {
    free(list->dataArray);
    list->dataArray = NULL;
    list->totalCapacity = 0;
    list->elementCount = 0;
}

void checkAndExpand(DList* list) {
    if (list->elementCount == list->totalCapacity) {
        ListElementType* temp = (ListElementType*)realloc(list->dataArray,
                                    sizeof(ListElementType) * list->totalCapacity * 2);
        if (temp == NULL) {
            perror("Memory reallocation failed");
            return;
        }
        list->dataArray = temp;
        list->totalCapacity *= 2;
    }
}

void displayList(DList* list) {
    for (int i = 0; i < list->elementCount; i++) {
        printf("%d ", list->dataArray[i]);
    }
    printf("\n");
}

void appendElement(DList* list, ListElementType value) {
    checkAndExpand(list);
    list->dataArray[list->elementCount++] = value;
}

void prependElement(DList* list, ListElementType value) {
    checkAndExpand(list);
    int currentEnd = list->elementCount - 1;
    while (currentEnd >= 0) {
        list->dataArray[currentEnd + 1] = list->dataArray[currentEnd];
        --currentEnd;
    }
    list->dataArray[0] = value;
    list->elementCount++;
}

void removeLast(DList* list) {
    assert(list->elementCount > 0);
    list->elementCount--;
}

void removeFirst(DList* list) {
    assert(list->elementCount > 0);
    int startIndex = 1;
    while (startIndex < list->elementCount) {
        list->dataArray[startIndex - 1] = list->dataArray[startIndex];
        startIndex++;
    }
    list->elementCount--;
}

void insertAtPosition(DList* list, int pos, ListElementType value) {
    assert(pos >= 0 && pos <= list->elementCount);
    checkAndExpand(list);
    int currentEnd = list->elementCount - 1;
    while (currentEnd >= pos) {
        list->dataArray[currentEnd + 1] = list->dataArray[currentEnd];
        --currentEnd;
    }
    list->dataArray[pos] = value;
    list->elementCount++;
}

void eraseAtPosition(DList* list, int pos) {
    assert(pos >= 0 && pos < list->elementCount);
    assert(list->elementCount > 0);
    int startIndex = pos + 1;
    while (startIndex < list->elementCount) {
        list->dataArray[startIndex - 1] = list->dataArray[startIndex];
        ++startIndex;
    }
    list->elementCount--;
}

int locateElement(DList* list, ListElementType value) {
    for (int i = 0; i < list->elementCount; i++) {
        if (list->dataArray[i] == value) {
            return i;
        }
    }
    return -1;
}

void updateElement(DList* list, int pos, ListElementType value) {
    assert(pos >= 0 && pos < list->elementCount);
    list->dataArray[pos] = value;
}

Test File (TestList.c)

#include "DynamicList.h"
#include <stdio.h>

void testAppend() {
    DList myList;
    listInitialize(&myList);
    appendElement(&myList, 10);
    appendElement(&myList, 20);
    appendElement(&myList, 30);
    appendElement(&myList, 40);
    appendElement(&myList, 50);
    displayList(&myList);
    listDestroy(&myList);
}

void testPrepend() {
    DList myList;
    listInitialize(&myList);
    appendElement(&myList, 10);
    appendElement(&myList, 20);
    appendElement(&myList, 30);
    prependElement(&myList, 40);
    prependElement(&myList, 50);
    prependElement(&myList, 60);
    displayList(&myList);
    listDestroy(&myList);
}

void testRemoveLast() {
    DList myList;
    listInitialize(&myList);
    appendElement(&myList, 10);
    appendElement(&myList, 20);
    appendElement(&myList, 30);
    prependElement(&myList, 40);
    prependElement(&myList, 50);
    prependElement(&myList, 60);
    displayList(&myList);
    removeLast(&myList);
    removeLast(&myList);
    removeLast(&myList);
    displayList(&myList);
    listDestroy(&myList);
}

void testRemoveFirst() {
    DList myList;
    listInitialize(&myList);
    appendElement(&myList, 10);
    appendElement(&myList, 20);
    appendElement(&myList, 30);
    prependElement(&myList, 40);
    prependElement(&myList, 50);
    prependElement(&myList, 60);
    displayList(&myList);
    removeFirst(&myList);
    removeFirst(&myList);
    removeFirst(&myList);
    displayList(&myList);
    listDestroy(&myList);
}

void testInsertAt() {
    DList myList;
    listInitialize(&myList);
    appendElement(&myList, 10);
    appendElement(&myList, 20);
    appendElement(&myList, 30);
    prependElement(&myList, 40);
    prependElement(&myList, 50);
    prependElement(&myList, 60);
    displayList(&myList);
    insertAtPosition(&myList, 1, 99);
    insertAtPosition(&myList, 3, 22);
    displayList(&myList);
    listDestroy(&myList);
}

void testEraseAt() {
    DList myList;
    listInitialize(&myList);
    appendElement(&myList, 10);
    appendElement(&myList, 20);
    appendElement(&myList, 30);
    appendElement(&myList, 40);
    appendElement(&myList, 50);
    appendElement(&myList, 60);
    displayList(&myList);
    eraseAtPosition(&myList, 2);
    eraseAtPosition(&myList, 4);
    displayList(&myList);
    listDestroy(&myList);
}

void testLocate() {
    DList myList;
    listInitialize(&myList);
    appendElement(&myList, 10);
    appendElement(&myList, 20);
    appendElement(&myList, 30);
    appendElement(&myList, 40);
    appendElement(&myList, 50);
    appendElement(&myList, 60);
    displayList(&myList);
    int result1 = locateElement(&myList, 20);
    int result2 = locateElement(&myList, 60);
    printf("Found 20 at index: %d\n", result1);
    printf("Found 60 at index: %d\n", result2);
    listDestroy(&myList);
}

void testUpdate() {
    DList myList;
    listInitialize(&myList);
    appendElement(&myList, 10);
    appendElement(&myList, 20);
    appendElement(&myList, 30);
    appendElement(&myList, 40);
    appendElement(&myList, 50);
    appendElement(&myList, 60);
    displayList(&myList);
    updateElement(&myList, 2, 99);
    updateElement(&myList, 0, 11);
    displayList(&myList);
    listDestroy(&myList);
}

int main() {
    // Uncomment to run specific tests
    // testAppend();
    // testPrepend();
    // testRemoveLast();
    // testRemoveFirst();
    // testInsertAt();
    // testEraseAt();
    // testLocate();
    // testUpdate();
    return 0;
}

Tags: C Data Structures Sequential List Dynamic Array Memory Management

Posted on Tue, 19 May 2026 06:27:51 +0000 by smithmr8

Freaks City