Basic Algorithms and Data Structures

So far we have used data structures (lists, sets, maps) and written ad-hoc loops. This page introduces the classic algorithms and structures that show up in real software again and again. We will not get formal — no Big-O notation lectures — but we will develop intuition for which idea to reach for and why it works.

Linear search

The simplest possible search: look at each element until you find what you want, or run out.

Linear search:

• Works on any collection — sorted, unsorted, anything iterable.
• In the worst case, looks at every element. Doubling the collection roughly doubles the time.
• Is exactly what List.contains(...) and List.indexOf(...) do internally for a plain ArrayList.

For small lists, this is fine. For 10 million elements, repeatedly, it is too slow. Then you need…

Binary search

If the collection is sorted, you can do vastly better. Look at the middle element. If it matches, done. If your target is smaller, search the left half. Otherwise the right half. Each step eliminates half of what is left.

A list of 1 million elements is fully searched in 20 comparisons (2^20 ≈ 1M). A list of 1 billion: about 30 comparisons.

The cost of binary search: the input must be sorted. So sorting is itself worth investing in.

A simple sort: selection sort

Sorting is one of the most-studied subjects in CS. The fancy ones (quick sort, merge sort) are clever; the slow ones are easy to understand. Here is selection sort: on each pass, find the smallest remaining element and put it in the next position.

Selection sort takes time proportional to the square of the list length. For 10,000 elements, fine. For 10,000,000 elements, way too slow — for that you'd use the JDK's built-in Arrays.sort, which is O(n log n).

The general rule: you almost never write a sort in production Java. You call Collections.sort(list) or Arrays.sort(arr). But writing one once in your life makes the cost of sorting intuitive forever.

Two abstract data types: stack and queue

A data structure is how something is stored. An abstract data type (ADT) is what operations it supports. Two ADTs you will meet everywhere:

Stack — Last In, First Out (LIFO)

You push items on top; you pop them off the top.

Stacks model call frames (we saw it on the stack-and-heap page!), undo history, brace matching in parsers, depth-first search.

Queue — First In, First Out (FIFO)

You enqueue items at the back; you dequeue from the front. Like a line at a coffee shop.

Queues model task scheduling, message buffers, breadth-first search.

Java has classes for both — Deque (often used as a stack via ArrayDeque) and Queue (often LinkedList or ArrayDeque):

Knowing what to reach for

A working programmer's mental table of first-resort tools:

You will, of course, run into problems that don't fit this table. But this table covers an astonishing fraction of day-to-day code.

A challenge

!olleh

You now have a vocabulary for the dozen most common patterns. The last conceptual page widens the lens one more time: how is a whole program organized?