Dynamic Arrays and Resizing

A stack can be implemented with an array or with a linked list, and both versions expose the same push, pop, and isEmpty operations.

Programming

Interactive lab

Try it: Linked List

How a singly linked list stores values in separate nodes joined by next pointers, and how inserting or deleting only rewires pointers.

How it works

HEAD points at the first node; each node holds a value and a pointer to the next node; the last node points to NULL.
To insert, create a node, store its value, point it at its successor, then point its predecessor (or HEAD) at it.
To delete, walk to the node and make its predecessor skip over it.
Searching means following next pointers from HEAD until the value or NULL is reached.

Default run (9 steps): HEAD → 10 → 20 → 30 → NULL. 3 of 10 nodes. Choose an operation. Example: append 40. … Done: HEAD → 10 → 20 → 30 → 40 → NULL.

Educational simulation

Loading the simulation…

Predicting Which Value Comes Out First

A stack is an abstract data type that follows the Last-In-First-Out principle: the item added most recently is the first one removed. Because a stack is defined only by its operations, the same idea can be built in more than one way. This article looks at two concrete implementations of a stack of ints, one built from a linked list and one built from an array, and shows exactly how each one tracks its top. Both versions expose the same three operations, push, pop, and isEmpty, so a caller cannot tell them apart from the outside. The difference lies inside, in how each version finds the top.

What do you think happens?

You start with an empty stack, push 3, push 7, and push 9, and then call pop. Which value does pop return?

Reveal answer

Answer:

A stack is Last-In-First-Out, so the item added most recently is removed first. The most recent push was 9, so pop returns 9. Keep this answer in mind, because the array and linked list versions must both produce it.

Before reading either implementation, it helps to test a belief many learners bring to the array version. The usual picture of an array stack is drawn upside down, so it is tempting to assume the top must sit at the front of the array, at index 0. Keep that belief in mind. The rest of the article checks it against the actual definitions.

Where the Top Lives in an Array

The number of items on an array-based stack changes over time, so the array has many slots that may or may not be in use at any moment. A counter, conventionally named top, records how many of those slots are in use. If top is the counter, the items live in positions 0, 1, up to top-1. The item in position 0 is at the bottom of the stack, and the item in position top-1 is at the top.

After pushing 3, 7, and 9, which array index holds the top element, and what does the counter point to?

Notice what the diagram shows. The counter is not simply the index of the newest item. It is the count of items in use, and because the first slot is index 0, that same number is also the index of the next free slot. That double role is why the top item sits at top-1 rather than at top. Once you hold this picture, the upside-down drawing stops being confusing: the bottom and top are determined by positions 0 and top-1, whichever way the array is drawn on paper.

Tracing Push, Pop, and isEmpty on an Array

In the array version, push places the new item at position top and then adds 1 to top. Pop does the reverse in order: it reads the item at position top-1, subtracts 1 from top, and returns the item it read. Because both operations work through the counter, the array never needs to be searched. Each operation touches a fixed position computed from top. The isEmpty method returns true exactly when top equals 0.

Worked example

Tracing an array stack through three pushes and one pop

Start with an empty array stack where top is 0. Perform push(3), push(7), push(9), pop(), and isEmpty() in that order. Track the array contents, the value of top, and each return value.

1
Initial state
top is 0, so isEmpty() returns true. No positions are in use.
2
push(3)
The item 3 goes into position 0, and top increases from 0 to 1.
3
push(7)
The item 7 goes into position 1, and top increases from 1 to 2.
4
push(9)
The item 9 goes into position 2, and top increases from 2 to 3.
5
pop()
pop reads position top-1, which is position 2, and gets 9. It subtracts 1 from top, so top becomes 2. It returns 9.
6
isEmpty()
top is 2, which is not 0, so isEmpty() returns false.

Result

pop returns 9, which matches the Last-In-First-Out prediction. After the pop, top is 2, the stack holds 3 and 7, and isEmpty() returns false.

Operation	Array contents in use	top after	Return value
Start	none	0	isEmpty() returns true
push(3)	3	1	none
push(7)	3, 7	2	none
push(9)	3, 7, 9	3	none
pop()	3, 7	2	9
isEmpty()	3, 7	2	false

Trace of the array stack. Only the positions counted by top are in use.

Why Index 0 Is the Wrong Top

The belief from the introduction can now be tested. In the array version, the bottom of the stack is position 0 and the top is position top-1. Since the top moves as items are pushed and popped, the top is never fixed at index 0. Treating position 0 as the top would make the first item pushed the first item popped, which breaks Last-In-First-Out order. Under the correct definitions, the stack from the trace above has its top at index 2, not index 0, because top is 3.

Growing a Full Dynamic Array

A fixed-size array would limit how many items the stack can hold. If that limit is not wanted, the dynamic array technique removes it. Before each push, the implementation checks whether top equals the length of the items array. If it does, the array is full. The code then creates a new, larger array and copies the current stack items into it. The source resizes by doubling the array, using Arrays.copyOf with twice the current length. The new item is stored in the next available spot, and top goes up by one as usual.

What does the underlying array look like before and after a push triggers resizing, and how are the existing items carried over?

java

if (top == items.length) {
    items = Arrays.copyOf(items, 2 * items.length);
}
items[top] = item;
top++;

if (top == items.length) {
    items = Arrays.copyOf(items, 2 * items.length);
}
items[top] = item;
top++;

Notes on the code

The check compares the counter with the array length before every push.
Arrays.copyOf creates a new array of twice the current length and copies the old items into it.
The new item goes into the next free slot, then top increases by one.

The resize step changes the storage but not the stack. The four existing items keep their order from bottom to top, and top still counts them. Only the container grows. This is why the abstract stack operations can stay the same while the array underneath is replaced. A caller pushing a fifth item sees exactly the same behavior as before, even though the array has been swapped for one with room to spare.

The Linked List Top at the Head

The linked list implementation reaches the same abstract behavior by a different route. Here the top of the stack is the node at the head of the list. A private static nested class named Node holds an int item and a reference next to the following node. The class stores a single pointer, top, which points to the head node. If top is null, the stack is empty.

Which node is the top of the stack, and how do the next references connect the nodes so that push and pop only touch the head?

The diagram makes the linked list version easy to read: the top pointer names the head, and every node names the one beneath it. Compare this with the array version. In the array, the top of the stack is found by arithmetic on the counter. In the linked list, it is found by following the head pointer. Both designs present the same stack behavior to the caller.

Tracing Push and Pop on a Linked List

Push creates a new node, stores the new item in it, and points its next reference at the old top. Then top is moved to the new node. Pop saves the item from the head node, moves top to the second node, and returns the saved item. The source explains why this design fits: adding and removing nodes at the front of a linked list is much easier than inserting and deleting nodes in the middle. A stack only ever works at one end, so the front is the only place it needs.

Worked example

Tracing a linked-list stack through the same operations

Start with an empty linked-list stack where top is null. Perform push(3), push(7), push(9), pop(), and isEmpty() in that order. Track which node is the head and what each operation returns.

1
Initial state
top is null, so isEmpty() returns true.
2
push(3)
A new node holding 3 is created with next set to null, the old top. top now points to this node.
3
push(7)
A new node holding 7 is created with next pointing at the node 3. top moves to the node 7.
4
push(9)
A new node holding 9 is created with next pointing at the node 7. top moves to the node 9, which is now the head.
5
pop()
pop saves 9 from the head node, moves top to the second node 7, and returns 9. The node 9 is no longer reachable from top.
6
isEmpty()
top points to the node 7, which is not null, so isEmpty() returns false.

Result

pop returns 9, the same value the array version returns. The head moves from 9 to 7, and the stack still holds 3 and 7 in the same order.

The two versions therefore agree on every return value. The only difference visible inside the code is how each one finds the top: by arithmetic on top in the array, and by following the head pointer in the linked list.

Comparing the Two Top Positions

Question	Array-based stack	Linked-list-based stack
Where is the top?	At position top-1, computed from the counter	At the head node, named by the top pointer
How is the top found?	By arithmetic on the counter	By following the head pointer
Where do push and pop work?	At the counter position, which moves as items are added and removed	At the front of the list
What signals empty?	top equals 0	top is null
What grows when full?	The array is replaced by one of twice the length	Nothing is resized; a new node is created per push

Both implementations expose push, pop, and isEmpty with the same behavior.

Mistakes With Stack Tops

Common mistake
Treating array index 0 as the top of the stack
What it looks like
After push(3), push(7), push(9), reading items[0] and calling it the top gives 3, not 9.
Why it fails
Position 0 is the bottom. The top is at position top-1, which moves as the stack changes size.
Do this instead
Read the top at position top-1, which is index 2 when top is 3.
Common mistake
Reading position top instead of top-1 in pop
What it looks like
With top equal to 3, reading items[3] returns an unused slot instead of 9.
Why it fails
top is the count and also the next free slot, so it is one past the last item in use.
Do this instead
pop reads items[top-1], then decrements top.
Common mistake
Expecting pop to erase the removed item
What it looks like
After pop returns 9 from a three-item stack, items[2] still holds 9 until a later push overwrites it.
Why it fails
pop only lowers the counter. The counter records which spaces are in use, so the old value is simply no longer part of the stack.
Do this instead
Trust top, not the leftover contents of unused positions.
Common mistake
Calling pop on an empty stack
What it looks like
Calling pop immediately after creating a new stack.
Why it fails
When top is 0 there is nothing to remove, and the array version throws an IllegalStateException.
Do this instead
Check isEmpty() before calling pop when the stack may be empty.
Common mistake
Forgetting that a full array must be resized before the next push

Practice Tracing a Stack

MEDIUM

Start with an empty array stack of length 4 where top is 0. Perform push(5), push(8), pop(), push(2), push(6), push(1), and then state the value of top, which position holds the top item, and what the next push would do. Then repeat the same sequence on a linked-list stack and list the value of the head node.

Hints

Track top after each operation, not the array contents alone.
After the pop, top is 1, so the next push writes to position 1, overwriting 8 in the array.
The array has length 4. Count how many items are in use before deciding whether the next push triggers resizing.
In the linked list, the head is always the most recent push that has not been popped.

Your attempt (not saved)

Key Takeaways

A stack is Last-In-First-Out, and the array and linked list versions expose the same push, pop, and isEmpty operations.
In the array version, items occupy positions 0 through top-1, so the top is at top-1 and not at index 0.
In the linked list version, the top is the head node, and push and pop work at the front of the list.
A dynamic array checks whether top equals its length before a push, and doubles its size with Arrays.copyOf when full, leaving the stack's contents and order unchanged.