Implementation of Basic Sequence List Operations

Overview

1. Initializing a Sequence List

The initialization procedure differs between staticaly and dynamically allocated lists.

1.1 Initializing a Statical Allocated List

With static allocation, the array space is pre-allocated upon declaration. Initialization simply involves setting the current length to zero.

// SqList L; // Declare a sequence list
void InitList(SqList &L) {
    L.length = 0; // Set initial length to 0
}

1.2 Initializing a Dynamically Allocated List

Dynamic allocation requires allocating an array of a predefined size during initialization. The MaxSize field tracks the current capacity, which can be reallocated if insertion requires more space.

void InitList(SeqList &L) {
    L.data = (ElemType *)malloc(InitialSize * sizeof(ElemType)); // Allocate storage space
    L.length = 0;      // Set initial length to 0
    L.MaxSize = InitialSize; // Set initial storage capacity
}

2. Insert Operation

2.1 Insert Operation Procedure

Inserts a new element e at position i (where 1 ≤ i ≤ L.length+1) in sequence list L. If i is invalid, return false indicating failure. Otherwise, shift all elements from position i onward one position to the right to create space, insert the new element e, increment the list length, and return true.

bool ListInsert(SqList &L, int i, ElemType e) {
    // Validate index range
    if (i < 1 || i > L.length + 1) {
        return false;
    }
    // Check if storage is full
    if (L.length >= MaxCapacity) {
        return false;
    }
    // Shift elements to the right
    for (int pos = L.length; pos >= i; pos--) {
        L.data[pos] = L.data[pos - 1];
    }
    // Insert the new element
    L.data[i - 1] = e;
    L.length++; // Increment length
    return true;
}

2.2 Time Complexity of Insertion

The worst-case time complexity is O(n), occurring when inserting at the first position, requiring all n existing elements to be shifted.

3. Delete Operation

3.1 Delete Operation Procedure

Deletes the element at position i (1 ≤ i ≤ L.length) from sequence list L. If i is invalid, return false. Otherwise, store the deleted element (if needed), shift all elements after position i one position to the left, decrement the list length, and return true.

bool ListDelete(SqList &L, int i, ElemType &deletedElem) {
    if (i < 1 || i > L.length) {
        return false; // Invalid position
    }
    deletedElem = L.data[i - 1]; // Store the element to be deleted
    // Shift elements to the left
    for (int pos = i; pos < L.length; pos++) {
        L.data[pos - 1] = L.data[pos];
    }
    L.length--; // Decrement length
    return true;
}

3.2 Time Complexity of Deletion

The worst-case time complexity is O(n), occurrign when deleting the first element, requiring n-1 elements to be shifted.

4. Search Operations

4.1 Search by Position (Get)

Retrieves the element at a specified position i.

ElemType GetElem(SqList L, int i) {
    if (i < 1 || i > L.length) {
        // Handle error: invalid position
        return ERROR; // Assuming ERROR is a defined constant
    }
    return L.data[i - 1];
}

4.2 Time Complexity of Search by Position

This operation has a constant time complexity of O(1) due to direct array indexing.

4.3 Search by Value (Sequential Search)

Finds the first occurrence of a specific value e in the list.

int LocateElem(SqList L, ElemType e) {
    for (int idx = 0; idx < L.length; idx++) {
        if (L.data[idx] == e) {
            return idx + 1; // Return position (1-based)
        }
    }
    return 0; // Return 0 if not found
}

4.4 Time Complexity of Search by Value

The average and worst-case time complexity is O(n), as it may require examining all n elements.