This article covers a practical implemantation of a dynamic sequential list (dynamic array) in C++, focusing on core data structure operations with complete, runnable code and detailed explanations.

1. Sequential List Structure Definition

// Header structure for the sequential list
typedef struct {
    Element* array;            // Pointer to the dynamic data storage
    int count;                 // Current number of stored elements
    int capacity;              // Maximum capacity before resizing is needed
} SeqList;

// 'count' always indicates the next available insertion position

2. Function Declarations

2.1. Creation and Deletion

SeqList* initSeqList(int n);                   // Allocate and initialize a new list
void destroySeqList(SeqList* list);            // Free the list header and its data

2.2. Resizing Function

int expandCapacity(SeqList* list);             // Double the current capacity

2.3. Insertion Operations

int appendElement(SeqList* list, Element value);        // Insert at the end
int prependElement(SeqList* list, Element value);       // Insert at the beginning
int insertElement(SeqList* list, int position, Element value);  // Insert at a specific index

2.4. Display and Search

void displayList(const SeqList* list);                 // Traverse and print all elements
int findElement(const SeqList* list, Element value);   // Search by value, returns index or -1

2.5. Deletion Operations

int removeByValue(SeqList* list, Element value);       // Delete first occurrence of a value
int removeFirst(SeqList* list);                        // Delete the first element
int removeLast(SeqList* list);                         // Delete the last element

3. Function Implementations

3.1. initSeqList - Initialize a Sequential List

Declaration:

SeqList* initSeqList(int n);

Purpose: Allocates a list with a specified capacity and returns a pointer to it.

Implementation Logic:

1. Allocate memory for the list header.
2. Allocate memory for the element storage array.
3. Initialize count to 0 and set capacity to n.
4. If any allocation fails, return NULL.

Code:

SeqList* initSeqList(int n) {
    SeqList* list = (SeqList*)malloc(sizeof(SeqList));
    if (list == NULL) {
        printf("Failed to allocate list header\n");
        return NULL;
    }

    list->array = (Element*)malloc(sizeof(Element) * n);
    if (list->array == NULL) {
        printf("Failed to allocate data array\n");
        free(list);
        return NULL;
    }

    list->count = 0;
    list->capacity = n;
    return list;
}

Test Example:

int main() {
    SeqList* myList = initSeqList(10);
    if (myList == NULL) {
        printf("List creation failed\n");
        return 1;
    }
    printf("List created successfully\n");
    destroySeqList(myList);
    return 0;
}

Test Result:

---

3.2. destroySeqList - Release Resources

Declaration:

void destroySeqList(SeqList* list);

Purpose: Safely frees all memory associated with the list to prevent leaks.

Implementation Logic:

1. Check if the list pointer is valid.
2. If the data array exists, free it.
3. Free the list header itself.

Code:

void destroySeqList(SeqList* list) {
    if (list) {
        if (list->array) {
            free(list->array);
            list->array = NULL;
        }
        free(list);
        printf("List destroyed\n");
    }
}

Test Example:

int main() {
    SeqList* myList = initSeqList(10);
    if (myList == NULL) {
        printf("List creation failed\n");
        return 1;
    }
    printf("List created successfully\n");
    destroySeqList(myList);
    return 0;
}

Test Result:

---

3.3. expandCapacity - Dynamic Resizing

Declaration:

int expandCapacity(SeqList* list);

Purpose: Doubles the storage capacity of the list when it becomes full.

Implementation Logic:

1. Allocate a new memory block twice the current capacity.
2. Copy all existing elements from the old memory to the new block.
3. Release the old memory.
4. Update the data pointer to the new block.
5. Update the capacity value.

Code:

int expandCapacity(SeqList* list) {
    Element* newBlock = (Element*)malloc(sizeof(Element) * 2 * list->capacity);
    if (!newBlock) {
        printf("Resizing failed: allocation error\n");
        return -1;
    }

    for (int i = 0; i < list->count; i++) {
        newBlock[i] = list->array[i];
    }

    free(list->array);          // Release old memory
    list->array = newBlock;     // Assign new memory
    list->capacity *= 2;
    printf("Capacity expanded\n");
    return 0;
}

Test Example:

int main() {
    SeqList* myList = initSeqList(3);
    for (int i = 0; i < 3; i++) {
        appendElement(myList, i);
    }
    appendElement(myList, 42);  // Triggers resize
    displayList(myList);
    printf("Capacity: %d\n", myList->capacity);
    destroySeqList(myList);
    return 0;
}

Test Result:

---

3.4. displayList and findElement

Declarations:

void displayList(const SeqList* list);
int findElement(const SeqList* list, Element value);

Purpose:

• displayList: Prints all elements in the list.
• findElement: Searches for a value and returns its index, or -1 if not found.

Implementation Logic:

1. displayList: Validate the list and data pointer, then iterate through count elements.
2. findElement: Validate the list, then loop through elements. If a match is found, return the index immediately. Otherwise, return -1.

Code:

void displayList(const SeqList* list) {
    if (list == NULL || list->array == NULL) {
        printf("List is empty or invalid\n");
        return;
    }
    for (int i = 0; i < list->count; i++) {
        printf("%d ", list->array[i]);
    }
    printf("\n");
}

int findElement(const SeqList* list, Element value) {
    if (!list || !list->array || list->count <= 0) {
        printf("List is empty or invalid\n");
        return -1;
    }
    for (int i = 0; i < list->count; i++) {
        if (list->array[i] == value) {
            return i;
        }
    }
    printf("Value not found\n");
    return -1;
}

Test Example:

int main() {
    SeqList* myList = initSeqList(5);
    for (int i = 0; i < 5; i++) {
        appendElement(myList, i);
    }
    displayList(myList);

    int index1 = findElement(myList, 99);
    int index2 = findElement(myList, 2);
    printf("Index of 99: %d\n", index1);
    printf("Index of 2: %d\n", index2);

    destroySeqList(myList);
    return 0;
}

Test Result:

---

3.5. appendElement, prependElement, and insertElement - Insertions

Declarations:

int appendElement(SeqList* list, Element value);
int prependElement(SeqList* list, Element value);
int insertElement(SeqList* list, int position, Element value);

Purpose:

• appendElement: Inserts an element at the end.
• prependElement: Inserts an element at the beginning.
• insertElement: Inserts an element at a given index.

Implementation Logic:

1. Comon Checks: Validate pointers and trigger resizing if count >= capacity.
2. appendElement: Place the value at index count, then increment count.
3. prependElement: Shift all elements one position to the right starting from the end, place the value at index 0, and increment count.
4. insertElement: Validate the posision (0 to count). Shift elements from position to count-1 one step right, insert the value, and increment count.

Code:

int appendElement(SeqList* list, Element value) {
    if (!list || !list->array) {
        printf("List is null\n");
        return -1;
    }
    if (list->count >= list->capacity) {
        if (expandCapacity(list) == -1) return -1;
    }
    list->array[list->count] = value;
    list->count++;
    return 0;
}

int prependElement(SeqList* list, Element value) {
    if (!list || !list->array) {
        printf("List is null\n");
        return -1;
    }
    if (list->count >= list->capacity) {
        if (expandCapacity(list) == -1) return -1;
    }
    for (int i = list->count; i > 0; i--) {
        list->array[i] = list->array[i - 1];
    }
    list->array[0] = value;
    list->count++;
    return 0;
}

int insertElement(SeqList* list, int position, Element value) {
    if (!list || !list->array) {
        printf("List is null\n");
        return -1;
    }
    if (position < 0 || position > list->count) {
        printf("Invalid insertion position\n");
        return -1;
    }
    if (list->count >= list->capacity) {
        if (expandCapacity(list) == -1) return -1;
    }
    for (int i = list->count - 1; i >= position; i--) {
        list->array[i + 1] = list->array[i];
    }
    list->array[position] = value;
    list->count++;
    return 0;
}

Test Example:

int main() {
    SeqList* myList = initSeqList(5);
    for (int i = 0; i < 5; i++) {
        appendElement(myList, i);
    }
    displayList(myList);

    insertElement(myList, 5, 100);
    displayList(myList);

    insertElement(myList, 0, 200);
    displayList(myList);

    prependElement(myList, 300);
    displayList(myList);

    appendElement(myList, 400);
    displayList(myList);

    destroySeqList(myList);
    return 0;
}

Test Result:

---

3.6. removeByValue, removeFirst, and removeLast - Deletions

Declarations:

int removeByValue(SeqList* list, Element value);
int removeFirst(SeqList* list);
int removeLast(SeqList* list);

Purpose:

• removeByValue: Finds and deletes the first occurrence of a specific value.
• removeFirst: Deletes the element at index 0.
• removeLast: Deletes the last element (logically moves the count backward).

Implementation Logic:

1. Common Checks: Validate the list and ensure it is not empty.
2. removeByValue: Use findElement to get the index. If found, shift all subsequent elements one step to the left and decrement count.
3. removeFirst: Shift elements from index 1 to count-1 left by one, then decrement count.
4. removeLast: Simply decrement count (the element becomes overwritable later).

Code:

int removeByValue(SeqList* list, Element value) {
    if (!list || !list->array) {
        printf("List is null\n");
        return -1;
    }
    int index = findElement(list, value);
    if (index == -1) {
        printf("Value not found for deletion\n");
        return -1;
    }
    for (int i = index + 1; i < list->count; i++) {
        list->array[i - 1] = list->array[i];
    }
    list->count--;
    return 0;
}

int removeFirst(SeqList* list) {
    if (!list || !list->array) {
        printf("List is null\n");
        return -1;
    }
    if (list->count <= 0) {
        printf("Cannot remove from empty list\n");
        return -1;
    }
    for (int i = 1; i < list->count; i++) {
        list->array[i - 1] = list->array[i];
    }
    list->count--;
    return 0;
}

int removeLast(SeqList* list) {
    if (!list || !list->array) {
        printf("List is null\n");
        return -1;
    }
    if (list->count <= 0) {
        printf("Cannot remove from empty list\n");
        return -1;
    }
    list->count--;
    return 0;
}

Test Example:

int main() {
    SeqList* myList = initSeqList(5);
    for (int i = 0; i < 5; i++) {
        appendElement(myList, i);
    }

    removeFirst(myList);
    displayList(myList);

    removeLast(myList);
    displayList(myList);

    removeByValue(myList, 99);  // Attempt to delete non-existent value
    displayList(myList);

    removeByValue(myList, 2);
    displayList(myList);

    destroySeqList(myList);
    return 0;
}

Test Result: