Sequential Storage Concept of Linear Lists

A linear list is a finite sequence of data elements, denoted as $L=(a_0, a_1, \dots, a_{n-1})$, where $L$ is the list name, $a_i$ is the data element, and $n$ is the length of the list. When the elements of linear list $L$ are stored consecutively in computer memory, this is called sequential storage of the linear list.

Characteristics of Linear Lists

• For a non-empty list, $a_0$ is the head element with no predecessor, and $a_{n-1}$ is the tail element with no successor
• Each middle element $a_i$ has exactly one direct predecessor $a_{i-1}$ and one direct successor $a_{i+1}$

Features of Sequential Storage Structure

• Elements that are logically adjacent ($a_i, a_{i+1}$) also have adjacent storage locations
• Supports random access by memory address
• High storage density, defined as $\text{Storage Density} = \frac{\text{Storage space occupied by data elements}}{\text{Total storage space occupied by the data structure}}$

Sequential Storage Representation in C

We can use a struct combined with a one-dimensional array to describe the sequential storage structure of a linear list:

#define MAX_CAPACITY 100
typedef int elem_type;

typedef struct {
    elem_type data[MAX_CAPACITY];  // Storage space for the list
    int last_idx;                  // Index of the last element in the linear list
} SeqList;

Note: last_idx stores the index of the final element in the list, so the actual length of the list is last_idx + 1.

Basic Operations of Sequential Lists

1. Create Empty List

Creates and initializes an empty linear list, including memory allocation and member variable initialization.

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

SeqList* seq_list_create(void) {
    SeqList* new_list = (SeqList*)malloc(sizeof(SeqList));
    if (new_list == NULL) {
        printf("seq_list_create: Memory allocation failed\n");
        return NULL;
    }
    new_list->last_idx = -1;
    return new_list;
}

2. Clear List

Resets the list to an empty state by resetting the last element index and clearing stored data.

int seq_list_clear(SeqList* list) {
    if (list == NULL) {
        printf("seq_list_clear: Invalid null list pointer\n");
        return -1;
    }
    memset(list->data, 0, sizeof(elem_type) * (list->last_idx + 1));
    list->last_idx = -1;
    return 0;
}

3. Check if List is Empty

Determines if the list has no elements by checking if the last element index is -1.

int seq_list_is_empty(const SeqList* list) {
    if (list == NULL) return -1;
    return (list->last_idx == -1) ? 1 : 0;
}

4. Get List Length

Returns the total number of elements in the list.

int seq_list_get_length(const SeqList* list) {
    if (list == NULL) {
        printf("seq_list_get_length: Invalid null list pointer\n");
        return -1;
    }
    return list->last_idx + 1;
}

5. Display List Elements

Prints all elements of the list to standard output.

void seq_list_print(const SeqList* list) {
    if (list == NULL) {
        printf("seq_list_print: Invalid null list pointer\n");
        return;
    }
    if (list->last_idx == -1) {
        printf("Current list is empty\n");
        return;
    }
    for (int i = 0; i <= list->last_idx; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

6. Free List Memory

Releases the dynamically allocated memory for the list and nullifies the pointer to avoid dangling references.

int seq_list_free(SeqList* list) {
    if (list == NULL) {
        return -1;
    }
    free(list);
    list = NULL;
    return 0;
}

Core Operations of Sequential Lists

1. Get Element by Index

Retrieves the value of the element at the specified index.

elem_type seq_list_get_elem(const SeqList* list, int index) {
    if (list == NULL) {
        printf("seq_list_get_elem: Invalid null list pointer\n");
        return (elem_type)-1;
    }
    if (index < 0 || index > list->last_idx) {
        printf("seq_list_get_elem: Index out of bounds\n");
        return (elem_type)-1;
    }
    return list->data[index];
}

2. Locate Element by Value

Finds the index of the first occurrence of a specified value in the list, returns -1 if the value is not found.

int seq_list_locate_elem(const SeqList* list, elem_type value) {
    if (list == NULL) {
        return -1;
    }
    for (int i = 0; i <= list->last_idx; i++) {
        if (list->data[i] == value) {
            return i;
        }
    }
    return -1;
}

3. Insert Elements

Front Insert

Inserts an element at the start of the list, requires shifting all existing elements one position to the right.

int seq_list_push_front(SeqList* list, elem_type value) {
    if (list == NULL || list->last_idx >= MAX_CAPACITY - 1) {
        printf("seq_list_push_front: Invalid parameters or list is full\n");
        return -1;
    }
    list->last_idx++;
    for (int i = list->last_idx; i > 0; i--) {
        list->data[i] = list->data[i-1];
    }
    list->data[0] = value;
    return 0;
}

Back Insert

Inserts an element at the end of the list, no element shifting required for high efficiency.

int seq_list_push_back(SeqList* list, elem_type value) {
    if (list == NULL || list->last_idx >= MAX_CAPACITY -1) {
        printf("seq_list_push_back: Invalid parameters or list is full\n");
        return -1;
    }
    list->data[++list->last_idx] = value;
    return 0;
}

Arbitrary Position Insert

Inserts an element at the specified index, shifts subsequent elements to the right to make space. If the index exceeds the current list langth, inserts at the end.

int seq_list_insert(SeqList* list, int index, elem_type value) {
    if (list == NULL || list->last_idx >= MAX_CAPACITY -1) {
        printf("seq_list_insert: Invalid parameters or list is full\n");
        return -1;
    }
    if (index < 0) {
        printf("seq_list_insert: Index out of bounds\n");
        return -1;
    }
    if (index > list->last_idx) {
        list->data[++list->last_idx] = value;
        return 0;
    }
    list->last_idx++;
    for (int i = list->last_idx; i > index; i--) {
        list->data[i] = list->data[i-1];
    }
    list->data[index] = value;
    return 0;
}

4. Delete Element by Index

Removes the element at the specified index, shifts all subsequent elements one position to the left to fill the gap.

int seq_list_delete(SeqList* list, int index) {
    if (list == NULL || list->last_idx == -1 || index < 0 || index > list->last_idx) {
        printf("seq_list_delete: Invalid parameters or empty list\n");
        return -1;
    }
    for (int i = index; i < list->last_idx; i++) {
        list->data[i] = list->data[i+1];
    }
    list->last_idx--;
    return 0;
}

5. Merge Two Lists

Merges all unique elements from the second list into the first list, skipping dupliacte values.

int seq_list_merge(SeqList* list1, const SeqList* list2) {
    if (list1 == NULL || list2 == NULL) {
        return -1;
    }
    for (int i = 0; i <= list2->last_idx; i++) {
        if (seq_list_locate_elem(list1, list2->data[i]) == -1) {
            seq_list_push_back(list1, list2->data[i]);
        }
    }
    return 0;
}

6. Remove Duplicate Elements

Removes duplicate values from the list, retaining only the first occurrence of each element.

int seq_list_remove_duplicates(SeqList* list) {
    if (list == NULL) {
        printf("seq_list_remove_duplicates: Invalid null list pointer\n");
        return -1;
    }
    if (list->last_idx <= 0) {
        return 0;
    }
    int i = 1;
    while (i <= list->last_idx) {
        int j = i -1;
        int duplicate_found = 0;
        while (j >= 0) {
            if (list->data[i] == list->data[j]) {
                seq_list_delete(list, i);
                duplicate_found = 1;
                break;
            }
            j--;
        }
        if (!duplicate_found) {
            i++;
        }
    }
    return 0;
}

Test Cases

Insert and Delete Test

void test_insert_delete(void) {
    SeqList* my_list = seq_list_create();
    if (my_list == NULL) {
        printf("Failed to create list\n");
        return;
    }
    seq_list_push_back(my_list, 66);
    seq_list_push_back(my_list, 100);
    seq_list_push_back(my_list, 22);
    seq_list_push_front(my_list, 12);
    seq_list_insert(my_list, 3, 76);
    seq_list_print(my_list);

    seq_list_delete(my_list, 2);
    seq_list_print(my_list);

    seq_list_free(my_list);
}

List Merge Test

void test_merge(void) {
    SeqList* list_a = seq_list_create();
    seq_list_push_back(list_a, 10);
    seq_list_push_back(list_a, 20);
    seq_list_push_back(list_a, 30);

    SeqList* list_b = seq_list_create();
    seq_list_push_back(list_b, 30);
    seq_list_push_back(list_b, 50);

    seq_list_merge(list_a, list_b);
    seq_list_print(list_a);

    seq_list_free(list_a);
    seq_list_free(list_b);
}

Duplicate Removal Test

void test_remove_duplicates(void) {
    SeqList* my_list = seq_list_create();
    seq_list_push_back(my_list, 10);
    seq_list_push_back(my_list, 10);
    seq_list_push_back(my_list, 10);
    seq_list_push_back(my_list, 10);
    seq_list_push_back(my_list, 10);

    seq_list_print(my_list);
    seq_list_remove_duplicates(my_list);
    seq_list_print(my_list);

    seq_list_free(my_list);
}

Header File Definition

#ifndef SEQ_LIST_H
#define SEQ_LIST_H

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

#define MAX_CAPACITY 100
typedef int elem_type;

typedef struct {
    elem_type data[MAX_CAPACITY];
    int last_idx;
} SeqList;

// Basic operations
SeqList* seq_list_create(void);
int seq_list_clear(SeqList* list);
int seq_list_is_empty(const SeqList* list);
int seq_list_get_length(const SeqList* list);
void seq_list_print(const SeqList* list);
int seq_list_free(SeqList* list);

// Core operations
elem_type seq_list_get_elem(const SeqList* list, int index);
int seq_list_locate_elem(const SeqList* list, elem_type value);
int seq_list_push_front(SeqList* list, elem_type value);
int seq_list_push_back(SeqList* list, elem_type value);
int seq_list_insert(SeqList* list, int index, elem_type value);
int seq_list_delete(SeqList* list, int index);
int seq_list_merge(SeqList* list1, const SeqList* list2);
int seq_list_remove_duplicates(SeqList* list);

#endif