Linear Lisst: Dynamic Sequential Storage

A linear list is a finite sequence of n data elements. This implementation uses dynamic memory allocation to manage the underlying array, allowing the list to grow as elements are inserted.

Dynamic Sequential List Header (dynSqList.h)

#ifndef DYN_SQLIST_H
#define DYN_SQLIST_H

#include "errorRecord.h"

#define INITIAL_CAPACITY 10
#define CAPACITY_INCREMENT 2

typedef int ElementType;

typedef struct {
    ElementType *data;      // pointer to the array
    int size;               // current number of elements
    int capacity;           // allocated capacity
} DynamicSeqList;

typedef void (*VisitFunc)(ElementType *);
typedef int (*CompareFunc)(ElementType, ElementType);

Status InitializeList(DynamicSeqList *list);
Status DestroyList(DynamicSeqList *list);
Status ClearList(DynamicSeqList *list);
Status IsListEmpty(const DynamicSeqList *list, Boolean *empty);
Status GetListLength(const DynamicSeqList *list, int *len);
Status GetElement(const DynamicSeqList *list, int index, ElementType *value);
Status LocateElement(const DynamicSeqList *list, ElementType value,
                     Boolean(*match)(ElementType, ElementType), int *position);
Status GetPredecessor(const DynamicSeqList *list, ElementType current, ElementType *prev);
Status GetSuccessor(const DynamicSeqList *list, ElementType current, ElementType *next);
Status InsertElement(int index, ElementType value, DynamicSeqList *list);
Status DeleteElement(int index, DynamicSeqList *list, ElementType *removed);
Status TraverseList(const DynamicSeqList *list, VisitFunc visit);
Status InsertAscending(ElementType value, CompareFunc cmp, DynamicSeqList *list);
Status InsertDescending(ElementType value, CompareFunc cmp, DynamicSeqList *list);
Status InsertAtHead(ElementType value, DynamicSeqList *list);
Status InsertAtTail(ElementType value, DynamicSeqList *list);
Status RemoveFirst(DynamicSeqList *list, ElementType *removed);
Status RemoveLast(DynamicSeqList *list, ElementType *removed);
Status RemoveElement(ElementType value, Boolean(*match)(ElementType, ElementType),
                     DynamicSeqList *list);
Status ReplaceElement(const DynamicSeqList *list, int index, ElementType value);

#endif

Implementation (dynSqList.c)

#include "dynSqList.h"
#include <stdlib.h>

Status InitializeList(DynamicSeqList *list)
{
    if (!list) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    list->data = (ElementType *)malloc(sizeof(ElementType) * INITIAL_CAPACITY);
    if (!list->data) {
        ERR_RECORD(ERR_MEMORY_ALLOCATE);
        return ERR_MEMORY_ALLOCATE;
    }

    list->size = 0;
    list->capacity = INITIAL_CAPACITY;
    return RET_OK;
}

Status DestroyList(DynamicSeqList *list)
{
    if (!list) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    free(list->data);
    list->data = NULL;
    list->size = 0;
    list->capacity = 0;
    return RET_OK;
}

Status ClearList(DynamicSeqList *list)
{
    if (!list) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    list->size = 0;
    return RET_OK;
}

Status IsListEmpty(const DynamicSeqList *list, Boolean *empty)
{
    if (!list || !empty) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    *empty = (list->size == 0) ? TRUE : FALSE;
    return RET_OK;
}

Status GetListLength(const DynamicSeqList *list, int *len)
{
    if (!list || !len) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    *len = list->size;
    return RET_OK;
}

Status GetElement(const DynamicSeqList *list, int index, ElementType *value)
{
    if (!list || !value) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    if (index < 1 || index > list->size) {
        ERR_RECORD(ERR_NOT_EXIST);
        return ERR_NOT_EXIST;
    }

    *value = list->data[index - 1];
    return RET_OK;
}

Status LocateElement(const DynamicSeqList *list, ElementType value,
                     Boolean(*match)(ElementType, ElementType), int *position)
{
    if (!list || !match || !position) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    for (int i = 0; i < list->size; i++) {
        if (match(list->data[i], value)) {
            *position = i + 1;
            return RET_OK;
        }
    }

    *position = 0;
    ERR_RECORD(ERR_NOT_EXIST);
    return ERR_NOT_EXIST;
}

Status GetPredecessor(const DynamicSeqList *list, ElementType current, ElementType *prev)
{
    if (!list || !prev) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    for (int i = 1; i < list->size; i++) {
        if (list->data[i] == current) {
            *prev = list->data[i - 1];
            return RET_OK;
        }
    }

    ERR_RECORD(ERR_NOT_EXIST);
    return ERR_NOT_EXIST;
}

Status GetSuccessor(const DynamicSeqList *list, ElementType current, ElementType *next)
{
    if (!list || !next) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    for (int i = 0; i < list->size - 1; i++) {
        if (list->data[i] == current) {
            *next = list->data[i + 1];
            return RET_OK;
        }
    }

    ERR_RECORD(ERR_NOT_EXIST);
    return ERR_NOT_EXIST;
}

Status InsertElement(int index, ElementType value, DynamicSeqList *list)
{
    if (!list) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    if (index < 1 || index > list->size + 1) {
        ERR_RECORD(ERR_PARA_ILLEGAL);
        return ERR_PARA_ILLEGAL;
    }

    if (list->size == list->capacity) {
        ElementType *newBlock = (ElementType *)realloc(list->data,
            sizeof(ElementType) * (list->capacity + CAPACITY_INCREMENT));
        if (!newBlock) {
            ERR_RECORD(ERR_MEMORY_ALLOCATE);
            return ERR_MEMORY_ALLOCATE;
        }
        list->data = newBlock;
        list->capacity += CAPACITY_INCREMENT;
    }

    for (int i = list->size; i >= index; i--) {
        list->data[i] = list->data[i - 1];
    }

    list->data[index - 1] = value;
    list->size++;
    return RET_OK;
}

Status DeleteElement(int index, DynamicSeqList *list, ElementType *removed)
{
    if (!list || !removed) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    if (index < 1 || index > list->size) {
        ERR_RECORD(ERR_NOT_EXIST);
        return ERR_NOT_EXIST;
    }

    *removed = list->data[index - 1];

    for (int i = index; i < list->size; i++) {
        list->data[i - 1] = list->data[i];
    }

    list->size--;
    return RET_OK;
}

Status TraverseList(const DynamicSeqList *list, VisitFunc visit)
{
    if (!list || !visit) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    for (int i = 0; i < list->size; i++) {
        visit(&list->data[i]);
    }

    return RET_OK;
}

static int FindInsertPosition(const DynamicSeqList *list, ElementType value,
                               Boolean ascending, CompareFunc cmp)
{
    int pos = 0;
    while (pos < list->size) {
        int result = cmp(value, list->data[pos]);
        if ((ascending && result <= 0) || (!ascending && result >= 0)) {
            break;
        }
        pos++;
    }
    return pos + 1;
}

Status InsertAscending(ElementType value, CompareFunc cmp, DynamicSeqList *list)
{
    if (!cmp || !list) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    return InsertElement(FindInsertPosition(list, value, TRUE, cmp), value, list);
}

Status InsertDescending(ElementType value, CompareFunc cmp, DynamicSeqList *list)
{
    if (!cmp || !list) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    return InsertElement(FindInsertPosition(list, value, FALSE, cmp), value, list);
}

Status InsertAtHead(ElementType value, DynamicSeqList *list)
{
    return InsertElement(1, value, list);
}

Status InsertAtTail(ElementType value, DynamicSeqList *list)
{
    return InsertElement(list->size + 1, value, list);
}

Status RemoveFirst(DynamicSeqList *list, ElementType *removed)
{
    return DeleteElement(1, list, removed);
}

Status RemoveLast(DynamicSeqList *list, ElementType *removed)
{
    return DeleteElement(list->size, list, removed);
}

Status RemoveElement(ElementType value, Boolean(*match)(ElementType, ElementType),
                     DynamicSeqList *list)
{
    int pos;
    Status status = LocateElement(list, value, match, &pos);
    if (status != RET_OK) {
        return status;
    }
    return DeleteElement(pos, list, &value);
}

Status ReplaceElement(const DynamicSeqList *list, int index, ElementType value)
{
    if (!list) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    if (index < 1 || index > list->size) {
        ERR_RECORD(ERR_NOT_EXIST);
        return ERR_NOT_EXIST;
    }

    list->data[index - 1] = value;
    return RET_OK;
}

Algorithm Header (algorithm.h)

#ifndef ALGORITHM_H
#define ALGORITHM_H

#include "dynSqList.h"

Status UnionLists(const DynamicSeqList *source, DynamicSeqList *target);
Status MergeLists(const DynamicSeqList *listA, const DynamicSeqList *listB,
                  CompareFunc cmp, DynamicSeqList *listC);
Status MergeListsOptimized(const DynamicSeqList *listA, const DynamicSeqList *listB,
                           CompareFunc cmp, DynamicSeqList *listC);
Status MergeListsUnique(const DynamicSeqList *listA, const DynamicSeqList *listB,
                        CompareFunc cmp, DynamicSeqList *listC);

#endif

Algorithm Implementation (algorithm.c)

#include "algorithm.h"
#include "auxiliary.h"
#include <stdlib.h>

Status UnionLists(const DynamicSeqList *source, DynamicSeqList *target)
{
    if (!source || !target) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    int targetLen, sourceLen;
    GetListLength(target, &targetLen);
    GetListLength(source, &sourceLen);

    for (int i = 1; i <= sourceLen; i++) {
        ElementType value;
        GetElement(source, i, &value);

        int pos;
        Status result = LocateElement(target, value, Equal, &pos);
        if (result == RET_OK) {
            continue;
        }

        result = InsertElement(++targetLen, value, target);
        if (result != RET_OK) {
            return result;
        }
    }

    return RET_OK;
}

Status MergeLists(const DynamicSeqList *listA, const DynamicSeqList *listB,
                  CompareFunc cmp, DynamicSeqList *listC)
{
    if (!listA || !listB || !listC) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    Status status = InitializeList(listC);
    if (status != RET_OK) return status;

    int lenA, lenB;
    GetListLength(listA, &lenA);
    GetListLength(listB, &lenB);

    int i = 1, j = 1, k = 0;
    ElementType aVal, bVal;

    while (i <= lenA && j <= lenB) {
        GetElement(listA, i, &aVal);
        GetElement(listB, j, &bVal);

        if (cmp(aVal, bVal) <= 0) {
            InsertElement(++k, aVal, listC);
            i++;
        } else {
            InsertElement(++k, bVal, listC);
            j++;
        }
    }

    while (i <= lenA) {
        GetElement(listA, i++, &aVal);
        InsertElement(++k, aVal, listC);
    }

    while (j <= lenB) {
        GetElement(listB, j++, &bVal);
        InsertElement(++k, bVal, listC);
    }

    return RET_OK;
}

Status MergeListsOptimized(const DynamicSeqList *listA, const DynamicSeqList *listB,
                           CompareFunc cmp, DynamicSeqList *listC)
{
    if (!listA || !listB || !listC) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    int lenA, lenB;
    GetListLength(listA, &lenA);
    GetListLength(listB, &lenB);

    int totalLen = lenA + lenB;
    listC->data = (ElementType *)malloc(sizeof(ElementType) * totalLen);
    if (!listC->data) {
        ERR_RECORD(ERR_MEMORY_ALLOCATE);
        return ERR_MEMORY_ALLOCATE;
    }

    listC->capacity = totalLen;
    listC->size = totalLen;

    ElementType *pa = listA->data;
    ElementType *pb = listB->data;
    ElementType *pc = listC->data;
    ElementType *paEnd = listA->data + lenA - 1;
    ElementType *pbEnd = listB->data + lenB - 1;

    while (pa <= paEnd && pb <= pbEnd) {
        if (cmp(*pa, *pb) <= 0) {
            *pc++ = *pa++;
        } else {
            *pc++ = *pb++;
        }
    }

    while (pa <= paEnd) *pc++ = *pa++;
    while (pb <= pbEnd) *pc++ = *pb++;

    return RET_OK;
}

Status MergeListsUnique(const DynamicSeqList *listA, const DynamicSeqList *listB,
                        CompareFunc cmp, DynamicSeqList *listC)
{
    if (!listA || !listB || !listC) {
        ERR_RECORD(ERR_NULL_PTR);
        return ERR_NULL_PTR;
    }

    int lenA, lenB;
    GetListLength(listA, &lenA);
    GetListLength(listB, &lenB);

    int totalCapacity = lenA + lenB;
    listC->data = (ElementType *)malloc(sizeof(ElementType) * totalCapacity);
    if (!listC->data) {
        ERR_RECORD(ERR_MEMORY_ALLOCATE);
        return ERR_MEMORY_ALLOCATE;
    }

    listC->capacity = totalCapacity;

    ElementType *pa = listA->data;
    ElementType *pb = listB->data;
    ElementType *pc = listC->data;
    ElementType *paEnd = listA->data + lenA - 1;
    ElementType *pbEnd = listB->data + lenB - 1;

    while (pa <= paEnd && pb <= pbEnd) {
        int compResult = cmp(*pa, *pb);
        if (compResult < 0) {
            *pc++ = *pa++;
        } else if (compResult > 0) {
            *pc++ = *pb++;
        } else {
            *pc++ = *pa++;
            pb++;
        }
    }

    while (pa <= paEnd) *pc++ = *pa++;
    while (pb <= pbEnd) *pc++ = *pb++;

    listC->size = (int)(pc - listC->data);
    return RET_OK;
}

Helper Functions (auxiliary.c)

#include "auxiliary.h"

Boolean Equal(ElementType a, ElementType b)
{
    return (a == b) ? TRUE : FALSE;
}

void PrintElement(ElementType *element)
{
    printf("%d ", *element);
}

int Compare(ElementType a, ElementType b)
{
    if (a == b) return 0;
    return (a < b) ? -1 : 1;
}

Boolean IsSquare(ElementType a, ElementType b)
{
    return (a == b * b) ? TRUE : FALSE;
}

void DoubleValue(ElementType *element)
{
    *element *= 2;
}

Status CreateSequentialList(int n, Boolean ascending, CompareFunc cmp, DynamicSeqList *list)
{
    if (!list) return ERR_NULL_PTR;

    Status status = InitializeList(list);
    if (status != RET_OK) return status;

    printf("Enter %d elements: ", n);
    ElementType val;
    scanf_s("%d", &val);
    InsertElement(1, val, list);

    for (int i = 1; i < n; i++) {
        scanf_s("%d", &val);
        if (ascending) {
            InsertAscending(val, cmp, list);
        } else {
            InsertDescending(val, cmp, list);
        }
    }

    return RET_OK;
}

Status DisplayList(const char *label, const DynamicSeqList *list)
{
    printf("%s", label);
    Status status = TraverseList(list, PrintElement);
    putchar('\n');
    return status;
}

Main Entry Point (main.c)

#include "algorithm.h"
#include "auxiliary.h"

int main(void)
{
    // Test Union
    DynamicSeqList listA, listB, listC;
    InitializeList(&listA);
    InitializeList(&listB);

    for (int i = 1; i <= 5; i++) {
        InsertElement(i, i, &listA);
    }
    DisplayList("listA: ", &listA);

    for (int i = 1; i <= 5; i++) {
        InsertElement(i, 2 * i, &listB);
    }
    DisplayList("listB: ", &listB);

    UnionLists(&listB, &listA);
    DisplayList("listA after union: ", &listA);

    // Test Merge
    MergeLists(&listA, &listB, Compare, &listC);
    DisplayList("listC: ", &listC);

    // Basic operations
    int pos;
    LocateElement(&listC, 2, IsSquare, &pos);
    printf("Position of element matching square condition: %d\n", pos);

    TraverseList(&listC, DoubleValue);
    DisplayList("listC after doubling: ", &listC);

    DestroyList(&listA);
    DestroyList(&listB);
    DestroyList(&listC);

    // Interactive test for ascending
    DynamicSeqList list;
    int num;
    printf("\nCreate ascending list. Enter number of elements: ");
    scanf_s("%d", &num);
    CreateSequentialList(num, TRUE, Compare, &list);
    DisplayList("Ascending list: ", &list);

    InsertAscending(10, Compare, &list);
    printf("After inserting 10: ");
    DisplayList("", &list);

    InsertAtHead(12, &list);
    InsertAtTail(9, &list);
    printf("After head insert 12 and tail insert 9: ");
    DisplayList("", &list);

    ElementType delVal;
    printf("Enter value to delete: ");
    scanf_s("%d", &delVal);
    RemoveElement(delVal, Equal, &list);
    DisplayList("After deletion: ", &list);

    int idx;
    ElementType newVal;
    printf("Enter index and new value for replace: ");
    scanf_s("%d %d", &idx, &newVal);
    ReplaceElement(&list, idx, newVal);
    DisplayList("After replace: ", &list);

    DestroyList(&list);

    // Interactive test for descending
    printf("\nCreate descending list. Enter number of elements: ");
    scanf_s("%d", &num);
    CreateSequentialList(num, FALSE, Compare, &list);
    DisplayList("Descending list: ", &list);

    InsertDescending(10, Compare, &list);
    printf("After inserting 10: ");
    DisplayList("", &list);

    printf("Enter value to delete: ");
    scanf_s("%d", &delVal);
    RemoveElement(delVal, Equal, &list);
    DisplayList("After deletion: ", &list);

    ElementType first, last;
    RemoveFirst(&list, &first);
    RemoveLast(&list, &last);
    printf("Removed first %d and last %d: ", first, last);
    DisplayList("", &list);

    DestroyList(&list);
    return 0;
}