Linked list considerations; array list in C

Considerations while developing a linked-list algorithm

1. Empty list: check start == NULL before deleting, traversing or searching; handle the first insertion into an empty list separately.
2. Insertion/deletion at the beginning: the external pointer start itself must be changed.
3. Insertion/deletion at the end: reach the last node (or keep a rear pointer); the last node's next must be NULL.
4. Pointer order: when inserting, set the new node's link first and then change the predecessor's link, otherwise the rest of the list is lost. When deleting, save the node in a temporary pointer before bypassing it and then free() it.
5. Memory allocation: check that malloc did not return NULL (no space); release deleted nodes to avoid memory leaks.
6. Single node list: first node and last node are the same.
7. Traversal safety: never use a pointer after it becomes NULL; keep a trailing pointer (prev) when the previous node is needed.
8. Dangling pointers: do not access a node after freeing it.
9. Doubly/circular lists: update both links (prev and next), and in circular lists make sure the loop terminates when the start is reached again.
10. Choose the variant (singly, doubly, circular, header node) suited to the operations needed.

Array implementation of a list in C

The elements are kept in an array; n stores the number of elements. Insert and delete shift the elements to keep them contiguous.

#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;
}

Output:

10 20 30
20 30

Insertion of 20 at position 1 shifts 30 right; deleting position 0 shifts 20, 30 left.