Skip to content
Tutorials Center
My learning

Topics

Lesson 191 of 201 ยท Data Structures and Algorithms

Data Structures in Java

Implement a dynamic array, stack, queue, singly linked list and binary search tree in Java with generics, then learn when to use the built-in collections.

A data structure is a way of arranging data in memory so that the operations you care about are fast. An array makes "give me element 7" instant. A linked list makes "insert at the front" instant. A tree keeps things sorted while you add and remove them. Every collection you used in the Collections Framework is one of these ideas, polished and tested.

In this lesson you'll build five classic structures from scratch with generics: a dynamic array, a stack, a queue, a singly linked list and a binary search tree. You won't use them in production code (the JDK versions are better), but writing them once teaches you what ArrayList, ArrayDeque, LinkedList and TreeMap do on every call, why some operations are cheap and others aren't, and how to answer the data-structure questions every technical interview asks.

Each implementation is small, complete and runnable. Read the code, run it, then change it: break an invariant on purpose and watch what goes wrong.

Measuring cost with Big-O

Before building anything, you need a vocabulary for "fast". Big-O notation describes how the work an operation does grows with the number of elements, n:

Notation Name Example Work for n = 1,000,000
O(1) constant read array[i] 1 step
O(log n) logarithmic find a key in a balanced tree about 20 steps
O(n) linear scan a list for a value a million steps
O(n log n) linearithmic a good sort about 20 million steps
O(nยฒ) quadratic compare every pair a trillion steps

Big-O ignores constant factors and small inputs. It answers one question: when the data gets ten times bigger, how much slower does this get? You'll see a table like this for every structure below. The next lesson, Searching and Sorting Algorithms, uses the same vocabulary for algorithms.

There is one more term you need: amortized cost. An operation is "amortized O(1)" when it is usually O(1) but occasionally expensive, and the rare expensive calls are so rare that the average over many calls is still constant. The dynamic array is the classic example.

A dynamic array

A Java array has a fixed length. ArrayList hides that limit: it keeps an internal array that is bigger than it needs to be, and when it fills up, it allocates a larger one and copies everything over. Here is the same idea in about 60 lines.

Java A growable array like ArrayList

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Run it and you'll see the capacity double from 2 to 4 to 8 while six names go in. Things to notice:

  • The array is Object[], not T[]. Because of type erasure, new T[2] doesn't compile. The JDK's ArrayList uses the same trick: store Object, cast on the way out. The cast is safe because only add and set put values in, and they accept only T.
  • size and items.length are different numbers. size counts elements; length is the capacity. Every bug in this class would come from mixing them up, which is why checkIndex compares against size.
  • Removal clears the freed slot. Without items[--size] = null, the array would keep a reference to an object nobody can reach through the list, so the garbage collector could never free it. That's a real memory leak, covered in Memory and Garbage Collection.

Why doubling makes add amortized O(1)

Copying the whole array is O(n), so why is add called O(1)? Count the copies. Filling the array to 1,024 elements, starting from capacity 2, copies 2 + 4 + 8 + ... + 512 elements, which is 1,022 copies in total: less than one copy per element added. Doubling (or ArrayList's growth of about 1.5ร—) means that the expensive calls get rarer exactly as fast as they get more expensive.

Grow by a fixed amount instead (say, 10 slots each time) and every tenth add copies the whole array. Total work becomes O(nยฒ). The growth factor matters.

Operation Cost
get(i), set(i, v) O(1)
add(v) at the end amortized O(1)
removeAt(i) / insert in the middle O(n): elements shift
search by value O(n)

A stack

A stack is last-in, first-out (LIFO): the last item you push is the first one you pop, like a pile of plates. Stacks power undo histories, the "back" button, expression evaluation and, invisibly, every method call you make (the JVM's call stack, which you met in Recursion).

A dynamic array makes a perfect stack: push and pop at the end are both O(1). The demo uses the stack to evaluate expressions in postfix notation (also called Reverse Polish notation), where the operator comes after its operands: 3 4 + means 3 + 4. The rule is simple: push numbers; when you see an operator, pop two numbers, apply it, and push the result.

Java An array-backed stack evaluating postfix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Trace the second line, 5 1 2 + 4 * + 3 -, with the stack shown bottom to top:

Token Action Stack after
5 push 5
1 push 5 1
2 push 5 1 2
+ pop 2 and 1, push 1 + 2 5 3
4 push 5 3 4
* pop 4 and 3, push 3 ร— 4 5 12
+ pop 12 and 5, push 5 + 12 17
3 push 17 3
- pop 3 and 17, push 17 โˆ’ 3 14

The order of the two pops matters: the value on top is the right operand, so 17 3 - is 14, not โˆ’14. The last two input lines are invalid on purpose: 2 3 4 leaves three values, and 1 + tries to pop from a stack with one item. Your stack reports both cleanly instead of returning garbage. Add your own expressions in the Input box.

In real code, use ArrayDeque as a stack (push, pop, peek), as shown in Queues, Deques and PriorityQueue. The legacy Stack class is synchronized and extends Vector, so it lets you insert into the middle of a "stack" (Legacy Collections).

A queue with a circular buffer

A queue is first-in, first-out (FIFO): items leave in the order they arrived, like people in a line. Print jobs, web requests waiting for a worker and the breadth-first search in Graphs, Recursion and Backtracking all use queues.

A naive array queue removes from index 0 and shifts everything left: O(n) per removal. The fix is a circular buffer (ring buffer). Keep two positions, head (the next item to remove) and tail (where the next item goes), and let both wrap around to index 0 when they fall off the end. Nothing ever shifts.

Java A ring-buffer queue that wraps around

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The output shows the wrap-around clearly:

TEXT
slots [A, B, C, null] head=0 size=3
dequeue A, dequeue B
slots [null, null, C, null] head=2 size=1
slots [E, null, C, D] head=2 size=3
slots [C, D, E, F, G, null, null, null] head=0 size=5
FIFO order: C D E F G

After two removals, head is 2. Adding D uses slot 3, and adding E computes (2 + 2) % 4 = 0, so it lands in slot 0 even though it is logically last. When the ring is full, grow copies the elements in queue order into a bigger array, which is why the slots read C, D, E, F, G afterwards. Copying the raw array with Arrays.copyOf would be a bug here: the order inside the ring isn't the order of the queue.

This is exactly how ArrayDeque works (with power-of-two capacities, so it can wrap with a bit mask instead of %). Both enqueue and dequeue are amortized O(1).

A singly linked list

A linked list doesn't use one big array. Each element lives in its own small node object that holds the value and a reference to the next node. The list itself only remembers the first node (head), and often the last one (tail) too.

TEXT
head                               tail
 โ”‚                                  โ”‚
 โ–ผ                                  โ–ผ
[ 10 | โ—]โ”€โ”€โ–บ[ 20 | โ—]โ”€โ”€โ–บ[ 30 | โ—]โ”€โ”€โ–บ[ 40 | null]

Because nodes are linked by references, inserting at the front means creating one node and moving head: O(1), no shifting. The price is that there are no indexes; reaching element i means following i links from the head.

Java A generic singly linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The tricky parts are the edge cases, and the code handles each one explicitly:

  • Empty list. addFirst and addLast must set both head and tail; removeFirst must clear tail when the last node goes.
  • Removing the head. There's no previous node, so head itself moves.
  • Removing the tail. tail moves back to previous. Forgetting this leaves tail pointing at a node that is no longer in the list, and the next addLast silently attaches to a ghost. Comment out tail = previous;, remove 40, then add a value and see what happens.

reverse is the most famous linked-list exercise. Trace it on 10 โ†’ 20 โ†’ 40:

Step previous current Links so far
start null 10 10 โ†’ 20 โ†’ 40
1 10 20 null โ† 10
2 20 40 null โ† 10 โ† 20
3 40 null null โ† 10 โ† 20 โ† 40

When current becomes null, previous is the old last node, which becomes the new head. Three variables, one pass, O(n) time, O(1) extra memory.

Implementing Iterable<T> (see Iterators and ListIterator) is what lets the class work in a for-each loop. The Node class is a private static nested class: it's an implementation detail nobody outside should see, and it doesn't need a reference to the list (Nested Classes).

Operation Singly linked list Dynamic array
add/remove at the front O(1) O(n)
add at the end (with a tail pointer) O(1) amortized O(1)
remove at the end O(n): needs the node before the tail O(1)
get element i O(n) O(1)
memory per element value + node object (~24 bytes overhead) value only

Removing the last node is O(n) in a singly linked list, because you must walk from the head to find the second-to-last node. java.util.LinkedList is doubly linked (each node also points back to prev), which makes both ends O(1). As LinkedList shows, it's still usually slower than ArrayList in practice: nodes are scattered across memory, and the CPU cache loves arrays.

A binary search tree

A binary tree is made of nodes that each have up to two children, left and right. A binary search tree (BST) adds one rule, the BST property:

For every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger.

That rule turns every lookup into a game of "higher or lower". Start at the root; if the key you want is smaller, go left, otherwise go right. Each step discards a whole subtree. Here's the tree you get by inserting 50, 30, 70, 20, 40, 60, 80, 35:

TEXT
              50
           /      \
         30        70
        /  \      /  \
      20    40  60    80
           /
         35

To find 35: 35 < 50, go left; 35 > 30, go right; 35 < 40, go left; found. Four comparisons instead of scanning eight values.

The implementation is naturally recursive: a tree is a node plus two smaller trees. The key type uses the bound T extends Comparable<T> (Bounded Types and Wildcards) so the tree can call compareTo.

Java A binary search tree with insert, search and delete

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

In-order traversal sorts for free

inOrder visits the left subtree, then the node, then the right subtree. Because of the BST property, that order is always ascending, so the tree prints [20, 30, 35, 40, 50, 60, 70, 80] without any sorting step. There are other traversal orders too: pre-order (node, left, right) is handy for copying a tree, and post-order (left, right, node) for deleting one or evaluating an expression tree.

Deleting a node: three cases

Deletion is where most BST implementations go wrong. There are three cases:

  1. A leaf (no children), like 20: just remove it by returning null to its parent.
  2. One child, like 40 (whose only child is 35): replace the node with its child. The child's whole subtree moves up, and the BST property still holds.
  3. Two children, like the root 50: you can't simply remove it. Find its in-order successor, the smallest key in the right subtree (here 60: go right once, then left as far as possible). Copy 60 into the root, then delete the original 60 from the right subtree, which is now case 1 or 2, since the smallest node never has a left child.

After deleting 20, 40 and 50, the tree is:

TEXT
           60
          /  \
        30    70
          \     \
          35     80

The recursive helpers all follow the same pattern: node.left = delete(node.left, key) and return node. Each call returns the (possibly new) root of its subtree, and the parent stores it. That avoids tracking parent pointers.

The height problem

Every operation walks one path from the root, so it costs O(h), where h is the tree's height. In a balanced tree, h is about logโ‚‚ n: a million keys need only about 20 levels. But a plain BST doesn't balance itself. Insert sorted data, and each new key goes to the right of the last one; the tree degrades into a linked list. That's why the demo prints height 1000 for 1,000 sorted inserts, and every lookup becomes O(n).

Self-balancing trees fix this by rotating nodes after inserts and deletes to keep the height near log n. java.util.TreeMap and TreeSet are red-black trees, which guarantee O(log n) for put, get and remove no matter what order keys arrive in (TreeMap and TreeSet). Writing a red-black tree is a good exercise for a rainy weekend; using TreeMap is the right choice on every other day.

Operation BST, balanced BST, worst case TreeMap
insert, search, delete O(log n) O(n) O(log n) guaranteed
min, max O(log n) O(n) O(log n)
in-order (sorted) traversal O(n) O(n) O(n)

Other structures worth knowing

You've now built the five core structures. A few more show up constantly, and the JDK already has good implementations:

  • Hash table: an array of buckets indexed by hashCode(), giving average O(1) lookups with no ordering. That's HashMap and HashSet, explained in How HashMap Works Inside.
  • Binary heap: a complete binary tree stored in an array where every parent is smaller than its children. The smallest element is always at index 0; insert and remove-min are O(log n). That's PriorityQueue (Queues, Deques and PriorityQueue), and the next lesson uses the same idea for heap sort.
  • Graph: nodes connected by edges, usually stored as a map from each node to a list of neighbors. Java has no built-in graph class; Graphs, Recursion and Backtracking builds one from a Map and Lists.
  • Trie, segment tree, union-find, skip list: specialized structures for prefix search, range queries, connectivity and concurrent sorted maps. ConcurrentSkipListMap is the JDK's skip list.

When to use the built-in collections instead

Write your own structure to learn, for an interview, or when you truly need something the JDK lacks. In application code, use the built-ins. They are faster than anything you'd write in an afternoon, handle edge cases you haven't thought of, implement the standard interfaces so they work with streams and every library, and are fail-fast when misused.

You built Use in real code Notes
DynamicArray ArrayList the default List
ArrayStack ArrayDeque (push/pop/peek) not the legacy Stack
RingQueue ArrayDeque (offer/poll) ArrayBlockingQueue between threads
SinglyLinkedList ArrayList, or ArrayDeque for both ends LinkedList only for rare cases
BinarySearchTree TreeMap / TreeSet balanced, with floor/ceiling/range views

Choosing the Right Collection has the full decision guide and big-O table for the JDK classes.

When an interviewer asks you to implement one of these, talk through the edge cases before you write code: the empty structure, a single element, removing the first and the last element, and duplicates. Most bugs in data-structure code live in exactly those places.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A dynamic array starts with capacity 2 and doubles when full. How many times does it grow while you add 9 elements?

    It grows 2 to 4 (adding the 3rd), 4 to 8 (adding the 5th), and 8 to 16 (adding the 9th). That's 3 growths, and the total number of copied elements (2 + 4 + 8) stays below the number of adds.
  2. 2. What does the postfix expression 8 2 - 3 * evaluate to?

    Push 8 and 2; the minus pops 2 (right) and 8 (left) and pushes 6. Push 3; the star pops 3 and 6 and pushes 18.
  3. 3. A ring queue has capacity 4, head = 3 and size = 2. In which slot does the next enqueued element go?

    The tail index is (head + size) % capacity = (3 + 2) % 4 = 1. The two current elements are in slots 3 and 0.
  4. 4. In a singly linked list with head and tail pointers, which operation is O(n)?

    To remove the tail you need the node before it, and a singly linked list can only reach it by walking from the head. A doubly linked list makes this O(1).
  5. 5. You insert 1, 2, 3, 4, 5 in that order into a plain (unbalanced) binary search tree. What is its height?

    Each key is larger than the previous one, so it goes into the right subtree every time, producing a chain of 5 levels. A self-balancing tree like TreeMap's red-black tree would keep the height near log n.

Summary

  • Big-O describes how cost grows with n; amortized O(1) means occasional expensive steps average out to constant time.
  • A dynamic array stores elements in an Object[] and doubles its capacity when full: O(1) indexing, amortized O(1) append, O(n) middle inserts.
  • A stack (LIFO) is a dynamic array used at one end; a queue (FIFO) is best built as a circular buffer whose head and tail wrap around with %.
  • A singly linked list makes front operations O(1) but indexing O(n); the hard parts are the empty, head and tail edge cases.
  • A binary search tree gives O(log n) operations only while it is balanced; sorted input turns it into a list. In-order traversal yields sorted keys, and deleting a node with two children uses its in-order successor.
  • Build these to understand them; in real code use ArrayList, ArrayDeque, HashMap, PriorityQueue and TreeMap.

Next: Searching and Sorting Algorithms, where you'll implement binary search and six classic sorts and time them against each other.