Arrays, stacks, queues and linked lists

An array is a fixed-size, contiguous block of memory holding elements of the same type. Every element occupies the same number of bytes and the elements are laid out back to back. So the address of any element can be computed directly from its index, which gives arrays O(1) random access, unlike linked structures. The two recurring calculations are an element's address (1-D or 2-D, row-major or column-major) and the cost of insertion or deletion, which requires shifting elements.

Conventions used throughout these notes, unless a question says otherwise: C semantics, int is 4 bytes and char is 1 byte, arrays are 0-indexed and stored row-major (as C stores them), and complexities are worst case.

A stack is a LIFO (last-in, first-out) structure supporting push (insert at top), pop (remove from top), peek/top (read the top without removing it), and isEmpty/isFull. Each is O(1) whether the stack is built on a fixed-size array or on a linked list. The array version keeps a top index and is full when top == capacity-1; a push in that state overflows. The linked-list version pushes and pops at the head, so no traversal is ever needed.

#define MAXSIZE 100
int stackArr[MAXSIZE];
int top = -1;

int isEmpty(void) { return top == -1; }
int isFull(void)  { return top == MAXSIZE - 1; }

void push(int x) {
    if (isFull()) { /* overflow */ return; }
    stackArr[++top] = x;
}

int pop(void) {
    if (isEmpty()) { /* underflow */ return -1; } /* -1 is only an illustrative sentinel */
    return stackArr[top--];
}

Stacks are used for expression conversion and evaluation, function-call and recursion bookkeeping, parenthesis matching and backtracking. They also answer whether a given output order can be produced from an input order using only push and pop.

In these infix-expression questions ^ means exponentiation. It is NOT C's ^ operator, which is bitwise XOR and has a much lower precedence.

Two stacks in one array. Two stacks can share an array of size N without wasting space: stack 1 grows upward from index 0 and stack 2 grows downward from index N-1. Overflow happens only when the whole array is used.

#define N 100
int arr[N];
int top1 = -1;
int top2 = N;

void push1(int x) {
    if (top1 + 1 == top2) { /* overflow: array full */ return; }
    arr[++top1] = x;
}

void push2(int x) {
    if (top1 + 1 == top2) { /* overflow: array full */ return; }
    arr[--top2] = x;
}

The array is full exactly when top1 + 1 == top2.

A queue is FIFO (first-in, first-out): enqueue inserts at the rear and dequeue removes from the front. A naive array-based linear queue only ever moves front and rear forward. After some dequeues the freed slots at the start of the array are never reused, so the queue can report 'full' while space exists. Treating the array as circular fixes this.

Convention 2 in C:

#define SIZE 100
int q[SIZE];
int front = 0, rear = -1, count = 0;

void enqueue(int x) {
    if (count == SIZE) { /* full */ return; }
    rear = (rear + 1) % SIZE;
    q[rear] = x;
    count++;
}

int dequeue(void) {
    if (count == 0) { /* empty */ return -1; } /* -1 is only an illustrative sentinel */
    int x = q[front];
    front = (front + 1) % SIZE;
    count--;
    return x;
}

A deque (double-ended queue) allows insertion and deletion at BOTH ends. An input-restricted deque allows insertion at only one end but deletion at both. An output-restricted deque allows deletion at only one end but insertion at both. A deque can act as a stack (use only one end) or as a plain queue (insert at one end, delete at the other).

/* amortized O(1) queue using two stacks (pseudo-code) */
Stack in, out;

enqueue(x):
    push(in, x)

dequeue():
    if isEmpty(out):
        while not isEmpty(in):
            push(out, pop(in))
    return pop(out)    /* underflow if both stacks are empty */

A linked list stores elements as nodes that can sit anywhere in memory. Each node holds data plus one or more pointers to neighbouring nodes. The list gives up O(1) random access, since you must walk from a known pointer. In exchange, insertion and deletion are O(1) once you hold a pointer to the right node, with no shifting.

/* singly linked list node */
struct SNode {
    int data;
    struct SNode *next;
};

/* doubly linked list node */
struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
};

In a circular singly linked list the last node's next points back to the head instead of NULL. A circular doubly linked list also has the head's prev pointing to the last node. Circular lists suit any traversal that should wrap around, for example round-robin scheduling.

O(1) deletion of a given node p (p must not be the last node):

struct SNode *t = p->next;
p->data = t->data;
p->next = t->next;
free(t);

Doubly linked list: insert node q after node p, and delete node p. The NULL checks cover the ends of the list.

/* insert q after p */
q->prev = p;
q->next = p->next;
if (p->next != NULL)
    p->next->prev = q;
p->next = q;

/* delete p */
if (p->prev != NULL)
    p->prev->next = p->next;
else
    head = p->next;
if (p->next != NULL)
    p->next->prev = p->prev;
free(p);

In the insertion, p->next = q; must come last, because the lines before it still need the old p->next.

Iterative in-place reversal of a singly linked list:

struct SNode* reverse(struct SNode *head) {
    struct SNode *prev = NULL;
    struct SNode *curr = head;
    while (curr != NULL) {
        struct SNode *nextNode = curr->next; /* save before overwriting */
        curr->next = prev;
        prev = curr;
        curr = nextNode;
    }
    return prev; /* new head */
}

Traversing a circular singly linked list. The next pointers never become NULL, so the loop stops on returning to the head. A do-while visits the head exactly once:

if (head != NULL) {
    struct SNode *p = head;
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);
}

Floyd's cycle detection ('tortoise and hare') walks two pointers through the list at different speeds: slow advances one node per iteration and fast advances two. If the list has no cycle, fast reaches NULL. If it has a cycle, both pointers eventually enter it. From then on the gap between them shrinks by exactly one link per iteration, so fast cannot jump over slow and they must land on the same node. The method takes O(n) time and O(1) extra space; a hash-set approach needs O(n) extra space.

int hasCycle(struct SNode *head) {
    struct SNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return 1; /* cycle found */
    }
    return 0; /* fast reached the end: no cycle */
}

Where they meet. Let $a$ be the number of links from the head to the first node of the cycle, and $c$ the number of nodes in the cycle. Suppose they meet after slow has taken $a+k$ steps, where $k$ is the meeting node's distance past the cycle start ($0\le k<c$). fast has taken $2(a+k)$ steps, and the difference $a+k$ must be a whole number of laps, a multiple of $c$. So $c-k\equiv a(\mathrm{mod}c)$: walking $a$ links forward from the meeting node lands exactly on the cycle start, possibly after going round the loop.