List and its operations

A list is a finite, ordered collection of elements of the same type, where each element has a position (first, second, ... last). Elements may be repeated and the list can grow or shrink: L = (a₁, a₂, ..., aₙ); n = 0 gives the empty list. It can be implemented with an array (contiguous list) or with links (linked list).

Operations on a list

1. Create / initialise – make an empty list (n = 0).
2. Empty / Full test – check whether the list has no element or no free space (full applies only to array lists).
3. Size (length) – return the number of elements.
4. Traverse (display) – visit every element once from first to last.
5. Insert – add a new element at the beginning, end or at a given position k. Elements from position k onward move one place right (array) or a link is changed (linked list).
6. Delete – remove the element at a given position or with a given value. Later elements move one place left (array).
7. Search / retrieve – find the position of a value, or fetch the element at position k.
8. Replace (update) – change the value at position k.
9. Sort / Merge / Copy – arrange elements in order, join two lists, or duplicate a list.

Example (array list, n = 4)

Index :  0   1   2   3   4
List  : 10  20  30  40   _
Insert 25 at position 2  -> shift 30, 40 right
List  : 10  20  25  30  40
Delete position 0        -> shift all left
List  : 20  25  30  40

Insertion or deletion in an array list costs O(n) because of shifting; retrieval by position is O(1). In a linked list, insertion/deletion after a known node is O(1), but reaching the k-th element is O(n).

Insert/delete in C

#include <stdio.h>
#define MAX 10

int list[MAX];          /* contiguous storage */
int n = 0;              /* number of elements currently in the list */

int insert(int pos, int x) {          /* pos = 0..n */
    if (n == MAX || pos < 0 || pos > n) return 0;   /* overflow / bad position */
    for (int i = n - 1; i >= pos; i--) list[i + 1] = list[i];  /* shift right */
    list[pos] = x;
    n++;
    return 1;
}

int delete_at(int pos) {              /* pos = 0..n-1 */
    if (n == 0 || pos < 0 || pos >= n) return 0;    /* underflow / bad position */
    for (int i = pos; i < n - 1; i++) list[i] = list[i + 1];   /* shift left */
    n--;
    return 1;
}

void traverse(void) {
    for (int i = 0; i < n; i++) printf("%d ", list[i]);
    printf("\n");
}

int main(void) {
    insert(0, 10); insert(1, 30); insert(1, 20);   /* 10 20 30 */
    traverse();
    delete_at(0);                                    /* 20 30 */
    traverse();
    return 0;
}