Lists

Read this page when position is part of the contract. The list API is the right tool when the caller chooses the insertion index or when indexed reads matter after insertion.

Constructor and Shared Interface

The constructor is:

list *create_list(ListType type, int initial_capacity, comparator cmp);

Every list exposes the same method table:

Field	Meaning
insert(self, item, index)	inserts one item at an index
get(self, index)	returns the stored pointer at an index or NULL
remove(self, index)	removes one item at an index
size(self)	returns the current element count
free(self)	frees the list and internal storage

The method-table field insert_bulk(self, elements, count) appends all pointers from the array. It is called as list->insert_bulk(list, elements, count). If the list is NULL, the array is NULL, or count <= 0, it does nothing.

Choose the Variant

Variant	Use it when...	Order rule	Read cost	Middle insert or remove
ARRAY_LIST	indexed reads matter	caller-controlled	direct by index	shifts the tail
LINKED_LIST	node insertion and removal matter more than direct indexing	caller-controlled	traversal to the index	no array shift
SORTED_LIST	the list must stay ordered after every insert	comparator-controlled	direct by index after insertion	shifts the tail after comparator placement

ARRAY_LIST

ARRAY_LIST stores a void ** buffer and grows geometrically.

Use it when appending and indexed reads dominate the workload. Appending at size is the clean path. Inserting in the middle still works, but every element after the insertion point shifts.

get returns NULL when the index is out of range. Inserting with an invalid index leaves the list unchanged in the shipped tests.

LINKED_LIST

LINKED_LIST stores linked nodes and keeps the same public interface as ARRAY_LIST.

Use it when insertion or removal in the middle matters more than direct index lookup. There is still no constant-time random access. get must walk nodes to the requested index.

Out-of-range get returns NULL. Inserting with an invalid index leaves the list unchanged in the shipped tests.

SORTED_LIST

SORTED_LIST maintains order on every insertion. The comparator is therefore part of the contract and is required in practice.

The index argument passed to insert is ignored. Placement is decided by the comparator, not by the caller. That point matters because code that assumes insert(..., 0) means front insertion will be wrong for SORTED_LIST.

After insertion, get reads the ordered position. remove deletes by index and the remaining elements stay ordered.

Ownership and Cleanup

Lists store pointers. They do not copy or destroy the pointed-to payloads.

Destroy the list with list->free(list). Free the payloads in your own code if your program owns them.

Example

#include "list.h"

int main(void) {
    list *names = create_list(ARRAY_LIST, 2, NULL);
    char *a = "alpha";
    char *b = "beta";

    names->insert(names, a, 0);
    names->insert(names, b, 1);

    char *first = (char *)names->get(names, 0);
    names->free(names);
    return first && first[0] == 'a' ? 0 : 1;
}

When Not to Use a List

If the main operation is FIFO removal, move to Queues-and-Stacks.

If the main operation is “give me the top-priority item,” move to Heaps-and-Priority-Queues.

If the main operation is push and pop at both ends, move to Deque.