Implementing Lists, Stacks and Queues

In Chapter 4 you used ArrayList, LinkedList and ArrayDeque. Now you build them. Writing a list, a stack and a queue from scratch shows you where their Big-O costs come from, and it is the best practice there is for reasoning about references — the skill behind every tree and graph in the rest of the course.

The List ADT

An abstract data type (ADT) says what operations a type offers and what they do, not how they are stored. The List ADT is an ordered sequence with positions 0..size−1:

interface MyList<E> extends Iterable<E> {
    void add(E e);                 // append at the end
    void add(int index, E e);      // insert, shifting later elements right
    E get(int index);
    E set(int index, E e);         // returns the old element
    E remove(int index);           // returns the removed element
    int size();
    boolean isEmpty();
}

Two classic implementations satisfy this contract with very different costs: an array-based list (like java.util.ArrayList) and a linked list (like java.util.LinkedList). Client code written against MyList<E> works with either.

MyArrayList: an array that grows

A Java array has a fixed length, so the list keeps an array that is usually larger than needed and a separate size: slots 0..size-1 are in use, the rest are spare capacity.

index:    0    1    2    3    4    5    6    7
data:   [ A ][ B ][ C ][ D ][ E ][    ][    ][    ]
          <---- in use: size = 5 --->  <- spare ->
                                   capacity = data.length = 8

private static final int INITIAL_CAPACITY = 4;
private E[] data;
private int size;                  // number of slots in use: data[0..size-1]

@SuppressWarnings("unchecked")
public MyArrayList() {
    data = (E[]) new Object[INITIAL_CAPACITY];   // new E[..] does not compile
}

private void ensureCapacity() {
    if (size == data.length) {
        data = Arrays.copyOf(data, data.length * 2);   // double: O(size) copy
    }
}

public void add(E e) {
    ensureCapacity();
    data[size++] = e;
}

Adding five elements A to E to a new list (capacity 4), step by step:

call	array afterwards (_ = empty slot)	size	capacity	elements copied
add A	[A, _, _, _]	1	4	0
add B	[A, B, _, _]	2	4	0
add C	[A, B, C, _]	3	4	0
add D	[A, B, C, D]	4	4	0
add E	array full: copy 4 elements into a new array of 8, then store → [A, B, C, D, E, _, _, _]	5	8	4

The same thing in summary:

call	size before	action	capacity after
add #1–#4	0–3	store in the next free slot	4
add #5	4	array full: copy 4 elements into a new array of 8, then store	8

You cannot write new E[n]: the type parameter is erased at run time, so the compiler rejects generic array creation. The standard work-around is to create an Object[] and cast it to E[] (an unchecked cast, safe as long as the array never escapes the class).

Why add is amortized O(1)

One add can cost O(n) — the one that triggers a resize. But resizes are rare. Start with capacity 1 and double: to reach n elements you copy 1 + 2 + 4 + … + n/2 < n elements in total (when n is a power of 2; for any n the total is still less than 2n), plus n stores. So n adds cost less than 3n steps: O(1) amortized per add (Chapter 6's aggregate method). The same argument works for any constant factor: java.util.ArrayList grows by 1.5×.

Growing by a constant amount instead (say +10 slots) is a trap: the resizes happen every 10 adds and copy 10, 20, 30, … elements, which sums to about n²/20. That is Θ(n²) for n adds — Θ(n) amortized per add.

Real numbers for n = 1 000 adds:

growth rule	resizes	elements copied in total	copies per add
double (start at 1)	10	1 + 2 + … + 512 = 1 023	about 1
+10 (start at 10)	99	10 + 20 + … + 990 = 49 500	about 50

With 10 times more elements, the doubling column grows about 10 times; the +10 column grows about 100 times.

Adding and removing at an index

Inserting at position index must first open a gap by shifting data[index..size-1] one place right; removing closes the gap by shifting left.

public void add(int index, E e) {
    if (index < 0 || index > size)               // index == size is allowed
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    ensureCapacity();
    for (int i = size - 1; i >= index; i--) {    // shift right, starting at the BACK
        data[i + 1] = data[i];
    }
    data[index] = e;
    size++;
}

public E remove(int index) {
    checkIndex(index);
    E old = data[index];
    for (int i = index; i < size - 1; i++) {     // shift left, starting at the FRONT
        data[i] = data[i + 1];
    }
    data[--size] = null;                         // drop the stale reference
    return old;
}

public E get(int index) { checkIndex(index); return data[index]; }

public E set(int index, E e) {
    checkIndex(index);
    E old = data[index];
    data[index] = e;
    return old;
}

private void checkIndex(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}

add(1, X) on [A, B, C, D, E, _] (size 5, capacity 6), one shift at a time:

start               [A, B, C, D, E, _]
i=4: data[5]=data[4] [A, B, C, D, E, E]
i=3: data[4]=data[3] [A, B, C, D, D, E]
i=2: data[3]=data[2] [A, B, C, C, D, E]
i=1: data[2]=data[1] [A, B, B, C, D, E]
data[1] = X          [A, X, B, C, D, E]   size = 6

For a moment an element appears twice — that is fine, the next step overwrites the extra copy. Now remove(1) on the result, shifting from the front:

start               [A, X, B, C, D, E]   old = X
i=1: data[1]=data[2] [A, B, B, C, D, E]
i=2: data[2]=data[3] [A, B, C, C, D, E]
i=3: data[3]=data[4] [A, B, C, D, D, E]
i=4: data[4]=data[5] [A, B, C, D, E, E]
data[5] = null       [A, B, C, D, E, _]   size = 5, returns X

The direction of the shift loop matters. Shifting right must start at the back, otherwise each copy overwrites the element that is needed next. Shifting left must start at the front for the same reason. Both operations are O(n − index): cheap at the end of the list, O(n) at the front.

What goes wrong with the wrong direction? add(1, X) on [A, B, C, D, _] with the loop running forwards:

i=1: data[2]=data[1]  [A, B, B, D, _]    C is overwritten and lost
i=2: data[3]=data[2]  [A, B, B, B, _]
i=3: data[4]=data[3]  [A, B, B, B, B]
data[1] = X           [A, X, B, B, B]    wrong!

MyLinkedList: nodes and references

A linked list stores each element in its own node that holds a reference to the next node. The list keeps head (first node), tail (last node) and size. There are no shifts and no resizes — but also no way to jump to position i without walking.

 head                          tail
  |                             |
  v                             v
[ A | *-]--->[ B | *-]--->[ C | / ]        size = 3
 element next                   next = null

private static class Node<E> {
    E element;
    Node<E> next;
    Node(E element) { this.element = element; }
}

private Node<E> head, tail;
private int size;

public void addFirst(E e) {
    Node<E> n = new Node<>(e);
    n.next = head;          // 1. hook the new node onto the old first node
    head = n;               // 2. only then move head
    if (tail == null) tail = n;       // the list was empty
    size++;
}

public void addLast(E e) {
    Node<E> n = new Node<>(e);
    if (tail == null) {
        head = tail = n;              // empty list: n is first AND last
    } else {
        tail.next = n;
        tail = n;
    }
    size++;
}

public E removeFirst() {
    if (size == 0) throw new NoSuchElementException();
    E e = head.element;
    head = head.next;
    if (head == null) tail = null;    // removed the only node
    size--;
    return e;
}

public E removeLast() {
    if (size == 0) throw new NoSuchElementException();
    if (size == 1) return removeFirst();
    Node<E> p = head;
    while (p.next != tail) p = p.next;   // O(n): walk to the node before tail
    E e = tail.element;
    p.next = null;
    tail = p;
    size--;
    return e;
}

Each operation, before and after. Start from an empty list and follow the arrows:

empty:            head = null, tail = null, size = 0

addLast(B):       list was empty, so head = tail = the new node
                  head -> [B] -> null            tail = B, size 1

addFirst(A):      1. A.next = head (B)           [A] -> [B] -> null
                  2. head = A
                  head -> [A] -> [B] -> null     tail = B, size 2

addLast(D):       1. tail.next = D               [B] -> [D]
                  2. tail = D
                  head -> [A] -> [B] -> [D] -> null     tail = D, size 3

Removing:

before:           head -> [B] -> [C] -> [D] -> null     tail = D, size 3

removeLast():     p walks from B: B.next is C (not tail), move; C.next is D (tail), stop
                  p.next = null, tail = p
                  head -> [B] -> [C] -> null            tail = C, size 2

removeFirst():    head = head.next
                  head -> [C] -> null                   tail = C, size 1

removeFirst():    head = head.next = null, and head == null, so tail = null too
                  head = null, tail = null, size 0      (empty again)

addFirst, addLast and removeFirst are O(1). removeLast is O(n) in a singly linked list: removing the tail means making its predecessor the new tail, and the only way to find the predecessor is to walk from head. (The treasure-hunt notes only point forwards: from the last clue you cannot go back.)

Always check the edge cases with each method: the empty list, the one-element list (where head == tail), and the first and last positions.

Inserting in the middle

To insert at position index, walk to the node before it (index − 1 steps), then relink:

public void add(int index, E e) {
    if (index < 0 || index > size) throw new IndexOutOfBoundsException();
    if (index == 0) { addFirst(e); return; }
    if (index == size) { addLast(e); return; }       // keeps tail correct
    Node<E> prev = head;
    for (int i = 0; i < index - 1; i++) prev = prev.next;   // node at index-1
    Node<E> n = new Node<>(e);
    n.next = prev.next;     // 1. new node points at the rest of the list
    prev.next = n;          // 2. predecessor points at the new node
    size++;
}

add(2, C) on A -> B -> D: walk 1 step, so prev is B (index 1).

before:     head -> [A] -> [B] -> [D] -> null
                            prev

new node:           [C] -> null

step 1:     n.next = prev.next           [C] ---------+
                                                      v
            head -> [A] -> [B] ----------------> [D] -> null

step 2:     prev.next = n
            head -> [A] -> [B] -> [C] -> [D] -> null      size 4

The order of the two assignments is essential. n.next = prev.next must come first: it copies the only reference to the rest of the list into the new node. Do prev.next = n first and prev.next no longer leads to the rest; n.next = prev.next then makes n point to itself, and every node after it is lost:

wrong order, step 1:  prev.next = n     head -> [A] -> [B] -> [C] -> null
                                        [D] -> null   (nobody points to D any more!)
wrong order, step 2:  n.next = prev.next  (which is n itself)
                      head -> [A] -> [B] -> [C] --+
                                             ^    |
                                             +----+   C points to itself; D is lost

Doubly linked lists

In a doubly linked list each node also has a prev reference. That costs one extra reference per node but makes both ends symmetric: removeLast becomes O(1) (tail = tail.prev; tail.next = null;), you can walk backwards, and a node you already hold can be unlinked in O(1):

private static class Node<E> {
    E element;
    Node<E> prev, next;
    Node(E element) { this.element = element; }
}

// unlink a node p that is neither the first nor the last
private void unlinkMiddle(Node<E> p) {
    p.prev.next = p.next;
    p.next.prev = p.prev;
}

Unlinking B from A ⇄ B ⇄ C:

before:   null <- [A] <=> [B] <=> [C] -> null
                           p

p.prev.next = p.next      A.next now skips B:   [A] ------> [C]
p.next.prev = p.prev      C.prev now skips B:   [A] <------ [C]

after:    null <- [A] <=> [C] -> null           (B is no longer reachable)

Every insertion or removal now updates up to four references, and each of them is a chance for a bug: after any change, x.next.prev == x and x.prev.next == x must hold for every node. java.util.LinkedList is a doubly linked list with first and last. Some implementations add a sentinel (dummy) node before the first element so that "empty" and "at the ends" stop being special cases.

get(i) in a doubly linked list can start from whichever end is nearer, but that is still O(n).

Iterators as inner classes

Walking a linked list with get(i) in a loop is O(n²): get(0) walks 0 steps, get(1) walks 1 step, …, get(n−1) walks n − 1 steps — about n²/2 in total. An iterator remembers where it is, so a full traversal costs O(n). Implementing Iterable<E> also makes the list usable in a for-each loop.

public Iterator<E> iterator() {
    return new LinkedIterator();
}

// Inner (non-static) class: it can read the enclosing list's head
private class LinkedIterator implements Iterator<E> {
    private Node<E> current = head;

    public boolean hasNext() {
        return current != null;
    }

    public E next() {
        if (current == null) throw new NoSuchElementException();
        E e = current.element;
        current = current.next;
        return e;
    }
}

On the list A → B → C, the bookmark current moves like this:

call	current before	returns	current after
hasNext()	A	true	A
next()	A	A	B
next()	B	B	C
next()	C	C	null
hasNext()	null	false	null

LinkedIterator is an inner class (no static): each iterator object is tied to the list that created it and can read that list's head. A static nested class has no enclosing list, so head would not compile there. Node, on the other hand, should be static: a node needs nothing from the list, and a non-static node would carry a hidden reference to it.

With the iterator in place, for (String s : list) compiles to calls of iterator(), hasNext() and next().

Stacks on an array and on a linked list

A stack is last-in, first-out: push, pop and peek all work at one end, the top.

• Array stack: the top is data[size-1], so push and pop never shift. Push is amortized O(1) (doubling), pop is O(1).

class ArrayStack<E> {
    private E[] data;
    private int size;       // top element is data[size-1]

    @SuppressWarnings("unchecked")
    ArrayStack() { data = (E[]) new Object[4]; }

    void push(E e) {
        if (size == data.length) data = Arrays.copyOf(data, 2 * size);
        data[size++] = e;
    }

    E pop() {
        if (size == 0) throw new RuntimeException("stack is empty");
        E e = data[--size];
        data[size] = null;
        return e;
    }

    E peek() {
        if (size == 0) throw new RuntimeException("stack is empty");
        return data[size - 1];
    }

    boolean isEmpty() { return size == 0; }
}

Trace (the top is the right end of the array):

operation	returns	stack afterwards	size
push 1		[1]	1
push 2		[1, 2]	2
push 3		[1, 2, 3]	3
pop	3	[1, 2]	2
peek	2	[1, 2]	2
push 4		[1, 2, 4]	3
pop	4	[1, 2]	2
pop	2	[1]	1

• Linked stack: the top is the head of a singly linked list. Push is addFirst, pop is removeFirst, both O(1) in the worst case, and no tail is needed. Putting the top at the tail instead would make every pop O(n) (it is removeLast in a singly linked list).

class LinkedStack<E> {
    private static class Node<E> {
        E element; Node<E> next;
        Node(E element, Node<E> next) { this.element = element; this.next = next; }
    }
    private Node<E> top;    // the head of the list is the top of the stack

    void push(E e) { top = new Node<>(e, top); }

    E pop() {
        if (top == null) throw new RuntimeException("stack is empty");
        E e = top.element;
        top = top.next;
        return e;
    }

    E peek() {
        if (top == null) throw new RuntimeException("stack is empty");
        return top.element;
    }

    boolean isEmpty() { return top == null; }
}

The same pushes 1, 2, 3 in the linked stack:

push 1:   top -> [1] -> null
push 2:   top -> [2] -> [1] -> null      new node points to the old top
push 3:   top -> [3] -> [2] -> [1] -> null
pop:      top -> [2] -> [1] -> null      returns 3

top = new Node<>(e, top) does both steps in one line: the right-hand side is evaluated first, so the new node receives the old top as its next, and only then does top change.

Queues on a circular array

A queue is first-in, first-out: enqueue at the back, dequeue at the front. On a plain array, dequeuing data[0] and shifting everything left costs O(n). The fix is to let the front move: keep the index front of the oldest element and the size, and treat the array as a circle, wrapping indices with % data.length.

            [0]
       [3]       [1]       the index after 3 is (3 + 1) % 4 = 0
            [2]

private E[] data;
private int front;      // index of the oldest element
private int size;

@SuppressWarnings("unchecked")
public ArrayQueue(int capacity) { data = (E[]) new Object[capacity]; }

public void enqueue(E e) {
    if (size == data.length) resize();
    data[(front + size) % data.length] = e;    // first free slot, wrapping round
    size++;
}

public E dequeue() {
    if (size == 0) throw new NoSuchElementException();
    E e = data[front];
    data[front] = null;
    front = (front + 1) % data.length;
    size--;
    return e;
}

public E peek() {
    if (size == 0) throw new NoSuchElementException();
    return data[front];
}

Trace with capacity 4 (dequeue nulls its slot):

operation	data	front	size
enqueue A, B, C	[A, B, C, _]	0	3
dequeue → A	[_, B, C, _]	1	2
dequeue → B	[_, _, C, _]	2	1
enqueue D	[_, _, C, D]	2	2
enqueue E	[E, _, C, D]	2	3

E went to slot (2 + 2) % 4 = 0: the queue wraps round, and in queue order it reads C, D, E.

Why keep size rather than a rear index? With only front and rear, the state front == rear would mean both "empty" and "full". A size field (or deliberately leaving one slot unused) removes the ambiguity.

Resizing cannot simply copy the array with Arrays.copyOf: if the queue has wrapped, its later elements sit at the start of the old array and would end up before the front. resize() must copy the elements in queue order — data[(front + k) % data.length] for k = 0..size−1 — into positions 0..size−1 of the new array and reset front to 0. With doubling, enqueue is amortized O(1) and dequeue is O(1).

Continuing the trace above:

operation	data	front	size	note
enqueue F	[E, F, C, D]	2	4	slot (2 + 3) % 4 = 1; now full
enqueue G	[C, D, E, F, G, _, _, _]	0	5	full, so resize first: copy C, D, E, F in queue order, front = 0; G goes to slot 4
dequeue → C	[_, D, E, F, G, _, _, _]	1	4

A plain Arrays.copyOf at the resize would have given [E, F, C, D, _, _, _, _] with front 2, and G would go to slot (2 + 4) % 8 = 6: the queue would read C, D, _, _, G — E and F would be lost behind the new free slots.

Queues on a linked list

A singly linked list with head and tail is a natural queue: enqueue at the tail (addLast, O(1)) and dequeue at the head (removeFirst, O(1)). The other way round, dequeuing would be removeLast, which is O(n) in a singly linked list.

class LinkedQueue<E> {
    private static class Node<E> { E element; Node<E> next; Node(E e) { element = e; } }
    private Node<E> head, tail;    // dequeue at head, enqueue at tail
    private int size;

    void enqueue(E e) {
        Node<E> n = new Node<>(e);
        if (tail == null) head = tail = n;
        else { tail.next = n; tail = n; }
        size++;
    }

    E dequeue() {
        if (head == null) throw new NoSuchElementException();
        E e = head.element;
        head = head.next;
        if (head == null) tail = null;     // the same trap as removeFirst
        size--;
        return e;
    }
}

enqueue A:   head -> [A] -> null                  tail = A
enqueue B:   head -> [A] -> [B] -> null           tail = B
dequeue:     head -> [B] -> null                  tail = B    returns A
dequeue:     head = null                          tail = null returns B   (both reset!)

Comparing the implementations

Operation	MyArrayList	Singly linked (head + tail)	Doubly linked (head + tail)
get(i) / set(i, e)	O(1)	O(n)	O(n)
add at the end	O(1) amortized	O(1)	O(1)
add / remove at the front	O(n)	O(1)	O(1)
remove at the end	O(1)	O(n)	O(1)
add / remove at index i	O(n − i) shifting	O(i) walking	O(min(i, n − i)) walking
extra memory per element	spare capacity	1 reference + node object	2 references + node object

ADT	Array implementation	Linked implementation
Stack	push amortized O(1), pop O(1) (top = end of array)	push/pop O(1) (top = head)
Queue	circular array: enqueue amortized O(1), dequeue O(1)	enqueue at tail, dequeue at head: O(1)

Key takeaways

• An ADT (List, Stack, Queue) says what the operations do; an array or a linked list decides how fast they are.
• An array list keeps size ≤ data.length and doubles when full: one add may cost O(n), but n adds cost O(n) in total — amortized O(1). Growing by +c is amortized O(n).
• Inserting shifts right starting at the back; removing shifts left starting at the front, then nulls the freed slot.
• In a linked list, always save the reference to the rest of the list before you overwrite a link (n.next = prev.next before prev.next = n).
• Keep head, tail and size consistent in every method, and test the empty list, the one-element list, the first and the last position.
• Singly linked: removeLast is O(n). Doubly linked: O(1), at the price of one extra reference per node.
• Linked stack: top = head. Linked queue: enqueue at tail, dequeue at head. Array queue: a circular array with front, size and % data.length; resize by copying in queue order.
• Walk a linked list with an iterator (O(n)), never with get(i) in a loop (O(n²)).