LIST

Defined in header list.h
(included via #include "opencstl.h")

---

#define LIST(TYPE)     TYPE**
#define new_list(TYPE) cstl_list(TYPE)

LIST is a sequence container that supports constant time insertion and removal of elements from anywhere in the container. Fast random access is not supported.

Elements are not stored contiguously — LIST is a doubly-linked list. Each element lives in its own dynamically allocated node, linked to its predecessor and successor. Because of this, [] subscript access and standard C functions (qsort, bsearch) are not available. Traversal must be done with iterators using next() and prev().

The complexity (efficiency) of common operations on lists is as follows:

• Accessing the first or last element — constant O(1).
• Insertion or removal of elements (given an iterator) — constant O(1).
• Search (linear scan) — O(n).
• No random access.

---

Contents

1. Macro Parameters
2. Iterator Invalidation
3. Functions
   • Constructor / Destructor
   • Element Access
   • Iterators
   • Capacity
   • Modifiers
   • Lookup
4. Notes
5. Example
6. See Also

---

Macro Parameters

LIST(TYPE)

Parameter	Description
TYPE	The type of the elements stored in the list.

Expands to TYPE**. The handle is a pointer-to-pointer because each node is heap-allocated and linked. This is different from VECTOR (TYPE*).

LIST(int)   lst;   // expands to: int**  lst;
LIST(char*) slst;  // expands to: char*** slst;

new_list(TYPE)

Parameter	Description
TYPE	The type of the elements stored in the list.

Creates and returns a new empty list. The returned handle must be released with destroy when no longer needed.

LIST(int) lst = new_list(int);
// ... use lst ...
destroy(lst);

---

Iterator Invalidation

Unlike VECTOR, insertion and erasure in LIST do not invalidate any existing iterators, because nodes are independent heap objects.

Operation	Iterators Invalidated
All read-only operations	Never
assign, clear	All
push_back, push_front	None
pop_back, pop_front	Only the erased element
insert	None (other iterators remain valid)
erase	Only the erased element(s)
resize	Only erased elements (if shrinking)
destroy	All

---

Functions

Constructor / Destructor

new_list

LIST(TYPE) new_list(TYPE);

Constructs an empty doubly-linked list.

LIST(int) lst = new_list(int);
printf("%zu\n", size(lst));   // 0
destroy(lst);

---

destroy

void destroy(LIST(TYPE) lst);

Destroys the list, freeing all nodes and internal bookkeeping memory. Must be called for every list created with new_list.

LIST(int) lst = new_list(int);
push_back(lst, 1);
destroy(lst);

---

Element Access

front

TYPE front(LIST(TYPE) lst);

Returns the value of the first element. Calling front on an empty list is undefined behavior.

LIST(int) lst = new_list(int);
push_back(lst, 10);
push_back(lst, 20);
printf("%d\n", front(lst));   // 10
destroy(lst);

---

back

TYPE back(LIST(TYPE) lst);

Returns the value of the last element. Calling back on an empty list is undefined behavior.

LIST(int) lst = new_list(int);
push_back(lst, 10);
push_back(lst, 20);
printf("%d\n", back(lst));   // 20
destroy(lst);

---

Iterators

For LIST, the iterator type is TYPE*. Unlike VECTOR, pointer arithmetic (it++, it--) does not work because elements are not contiguous. You must use next() and prev() to advance the iterator.

begin

TYPE* begin(LIST(TYPE) lst);

Returns an iterator to the first element. Returns end(lst) if the list is empty.

LIST(int) lst = new_list(int);
for (int i = 0; i < 5; i++)
    push_back(lst, i * 10);

for (int *it = begin(lst); it != end(lst); it = next(it))
    printf("[%3d]", *it);   // [  0][ 10][ 20][ 30][ 40]
puts("");
destroy(lst);

---

end

TYPE* end(LIST(TYPE) lst);

Returns a sentinel iterator representing the position past the last element. Must not be dereferenced.

---

rbegin

TYPE* rbegin(LIST(TYPE) lst);

Returns a reverse iterator pointing to the last element. Use prev() to advance backward.

LIST(int) lst = new_list(int);
for (int i = 0; i < 5; i++)
    push_back(lst, i);

for (int *it = rbegin(lst); it != rend(lst); it = prev(it))
    printf("[%3d]", *it);   // [  4][  3][  2][  1][  0]
puts("");
destroy(lst);

---

rend

TYPE* rend(LIST(TYPE) lst);

Returns a sentinel reverse iterator before the first element. Must not be dereferenced.

---

next

TYPE* next(TYPE* iter);

Advances the iterator to the next element and returns it. This is the only correct way to move forward through a LIST.

for (int *it = begin(lst); it != end(lst); it = next(it))
    printf("%d\n", *it);

---

prev

TYPE* prev(TYPE* iter);

Moves the iterator to the previous element and returns it. Used for reverse traversal.

for (int *it = rbegin(lst); it != rend(lst); it = prev(it))
    printf("%d\n", *it);

---

Capacity

empty

bool empty(LIST(TYPE) lst);

Returns true if the list contains no elements.

LIST(int) lst = new_list(int);
printf("%d\n", empty(lst));   // 1
push_back(lst, 1);
printf("%d\n", empty(lst));   // 0
destroy(lst);

---

size

size_t size(LIST(TYPE) lst);

Returns the number of elements currently in the list.

LIST(int) lst = new_list(int);
push_back(lst, 1);
push_back(lst, 2);
printf("%zu\n", size(lst));   // 2
destroy(lst);

---

Modifiers

assign

void assign(LIST(TYPE) lst, size_t n);
void assign(LIST(TYPE) lst, size_t n, TYPE value);

Replaces the contents with n elements. Elements are set to value if provided, otherwise zero-initialized.

Overload	Description
assign(lst, n)	n zero-initialized elements
assign(lst, n, value)	n elements each set to value

LIST(int) lst = new_list(int);
assign(lst, 4, 7);   // [7][7][7][7]
destroy(lst);

---

push_back

void push_back(LIST(TYPE) lst, TYPE value);

Appends value to the end of the list. O(1). No reallocation occurs.

LIST(int) lst = new_list(int);
push_back(lst, 1);
push_back(lst, 2);
push_back(lst, 3);   // [1][2][3]
destroy(lst);

---

pop_back

void pop_back(LIST(TYPE) lst);

Removes the last element. O(1). Calling on an empty list is undefined behavior.

LIST(int) lst = new_list(int);
push_back(lst, 1);
push_back(lst, 2);
pop_back(lst);
printf("%d\n", back(lst));   // 1
destroy(lst);

---

push_front

void push_front(LIST(TYPE) lst, TYPE value);

Inserts value at the beginning of the list. O(1).

LIST(int) lst = new_list(int);
push_back(lst, 2);
push_front(lst, 1);
push_front(lst, 0);   // [0][1][2]
destroy(lst);

---

pop_front

void pop_front(LIST(TYPE) lst);

Removes the first element. O(1). Calling on an empty list is undefined behavior.

LIST(int) lst = new_list(int);
push_back(lst, 10);
push_back(lst, 20);
pop_front(lst);
printf("%d\n", front(lst));   // 20
destroy(lst);

---

insert

void insert(LIST(TYPE) lst, TYPE* pos, TYPE value);
void insert(LIST(TYPE) lst, TYPE* pos, size_t n, TYPE value);

Inserts element(s) before the node pointed to by pos. Does not invalidate any existing iterators.

Overload	Description
insert(lst, pos, value)	Insert a single element before pos
insert(lst, pos, n, value)	Insert n copies of value before pos

LIST(int) lst = new_list(int);
push_back(lst, 1);
push_back(lst, 3);

int *it = begin(lst);
it = next(it);               // point to 3
insert(lst, it, 2);          // [1][2][3]

for (int *p = begin(lst); p != end(lst); p = next(p))
    printf("[%d]", *p);
puts("");
destroy(lst);

---

erase

void erase(LIST(TYPE) lst, TYPE* pos);
void erase(LIST(TYPE) lst, TYPE* first, TYPE* last);

Removes element(s) from the list. Only the erased iterator(s) are invalidated.

Overload	Description
erase(lst, pos)	Remove the element at pos
erase(lst, first, last)	Remove all elements in [first, last)

LIST(int) lst = new_list(int);
for (int i = 0; i < 5; i++)
    push_back(lst, i);   // [0][1][2][3][4]

int *it = begin(lst);
it = next(it);
it = next(it);
erase(lst, it);          // [0][1][3][4]

for (int *p = begin(lst); p != end(lst); p = next(p))
    printf("[%d]", *p);
puts("");
destroy(lst);

---

resize

void resize(LIST(TYPE) lst, size_t n);
void resize(LIST(TYPE) lst, size_t n, TYPE value);

Resizes the list to contain exactly n elements.

• If n > size(lst): new elements are appended (zero or value).
• If n < size(lst): excess elements are removed from the end.

LIST(int) lst = new_list(int);
push_back(lst, 1);
push_back(lst, 2);
push_back(lst, 3);

resize(lst, 5, 99);   // [1][2][3][99][99]
resize(lst, 2);        // [1][2]
printf("size: %zu\n", size(lst));   // 2
destroy(lst);

---

clear

void clear(LIST(TYPE) lst);

Removes all elements. size(lst) becomes 0. All nodes are freed.

LIST(int) lst = new_list(int);
push_back(lst, 1);
push_back(lst, 2);
clear(lst);
printf("size: %zu\n", size(lst));   // 0
destroy(lst);

---

Lookup

find

TYPE* find(LIST(TYPE) lst, TYPE value);
TYPE* find(LIST(TYPE) lst, TYPE* start, TYPE value);

Performs a linear search for value. Returns an iterator to the first matching element, or end(lst) if not found.

Complexity: Linear — O(n).

LIST(int) lst = new_list(int);
for (int i = 0; i < 5; i++)
    push_back(lst, i * 10);   // [0][10][20][30][40]

int *it = find(lst, 20);
if (it != end(lst))
    printf("found: %d\n", *it);   // found: 20

destroy(lst);

---

Notes

• The handle type for LIST is TYPE** (node-based container).
  Contiguous containers (VECTOR, DEQUE) use TYPE*.
• Do not use it++ or it-- on a list iterator — use next(it) and prev(it) instead.
• LIST does not support [] subscript access or capacity().
• LIST is not compatible with qsort or bsearch since elements are not contiguous.

---

Example

#include "opencstl.h"

int main() {
    LIST(int) lst = new_list(int);

    for (int i = 0; i < 10; i++) {
        int val = 10 - i;
        push_back(lst, val);
    }

    // Forward traversal
    for (int *it = begin(lst); it != end(lst); it = next(it))
        printf("[%3d]", *it);
    puts("");

    // Reverse traversal
    for (int *it = rbegin(lst); it != rend(lst); it = prev(it))
        printf("[%3d]", *it);
    puts("");

    printf("size:  %zu\n", size(lst));
    printf("front: %d\n",  front(lst));
    printf("back:  %d\n",  back(lst));

    destroy(lst);
    return 0;
}

Output:

[ 10][  9][  8][  7][  6][  5][  4][  3][  2][  1]
[  1][  2][  3][  4][  5][  6][  7][  8][  9][ 10]
size:  10
front: 10
back:  1

---

See Also

Container	Description
VECTOR	Contiguous dynamic array; O(1) random access via []
DEQUE	Double-ended queue; [] access, O(1) insert/erase at both ends
STACK	LIFO adapter
QUEUE	FIFO adapter