Chapter 1: Introduction

1.1Digital data

This course is about how to organize data in memory, so it makes sense to start with the data itself. A computer's memory holds no letters, photographs, or songs. It holds billions of tiny cells, each set to 0 or 1, and everything else is built on top of them. How does a song end up as a pattern of bits?

1.1.1What is digital data?

When you record a voice memo, your voice reaches the phone as a pressure wave in the air. The wave is continuous: it has a value at every instant, and the value changes smoothly from one instant to the next. Quantities like this are called analog. The microphone converts the wave into a voltage, which is still analog. The processor, however, can only work with numbers — strings of 0s and 1s.

An analog-to-digital converter (ADC) bridges the gap. It samples the voltage at regular intervals and records each sample as a number. Playback reverses the process: a digital-to-analog converter (DAC) turns the numbers back into a voltage, and the speaker turns the voltage back into sound. Everything in between — saving, copying, sending, changing the volume, filtering out noise — is arithmetic on numbers (Figure 1.1).

The important word here is represented. A pattern of bits means nothing by itself: the same eight bits might be a letter in one file, a number in another, and the red level of a pixel in a third. What gives bits meaning is an encoding, a rule for interpreting them. A file extension such as .txt, .png, or .mp3 is a hint about which encoding to use.

1.1.2Bits, bytes, and binary numbers

The smallest unit of memory is the bit (binary digit), which is either 0 or 1. In hardware, the two values might be a low or high voltage, or a tiny patch of disk magnetized one way or the other. Two states are much easier to tell apart reliably than ten, which is the main reason computers work in binary.

One bit carries little information, so bits are grouped; eight bits make a byte. Every extra bit doubles the number of patterns, since each existing pattern can be followed by a 0 or a 1. One bit gives 2 patterns, two bits give 4 (00, 01, 10, 11), and n bits give 2ⁿ: 256 for a byte, 65,536 for 16 bits, and 4,294,967,296 for 32.

To read a bit pattern as a number we use the binary number system. In decimal, digits are weighted by powers of ten — 365 = 3·100 + 6·10 + 5·1. Binary works the same way with powers of two, so the eight positions of a byte are worth 128, 64, 32, 16, 8, 4, 2, and 1.

Larger units come up all the time. A kilobyte (KB) is about a thousand bytes, a megabyte (MB) about a million, and a gigabyte (GB) about a billion. “About,” because some software counts in powers of 1,024 (2¹⁰, a round number in binary) rather than 1,000.

1.1.3Why digital?

Three properties explain why digital data took over.

• It is numeric. Everything — photos, novels, songs — becomes binary numbers such as 1011 0010, so the same hardware can store and carry all of it. A hard disk neither knows nor cares what its bits mean.
• It is easy to store and share. Data moves freely between disks, the cloud, and networks, and copying is lossless. A cassette degrades a little with every copy; the millionth copy of a digital file is identical, bit for bit, to the first.
• It is fast to process. An ordinary processor today performs on the order of 10⁹ — a billion — basic operations per second.

The third point is also the reason this course exists. A billion operations a second sounds like enough for anything, but a poorly organized program can do work that grows far faster than its input. Suppose a program compares each of a million records with every other record. That is 10⁶ · 10⁶ = 10¹² comparisons, or about 1,000 seconds — more than sixteen minutes. Keep the same records in a suitable structure and the job can finish in a tiny fraction of a second. The machine sees only bits; data structures are how we arrange those bits so that the work stays small.

1.1.4Representing text, numbers, images, and sound

Each kind of information has its own encoding. Table 1.1 summarizes the four basic cases, and the paragraphs that follow look at each in turn.

Text. To store text, each character is assigned a number by a character encoding. One of the oldest and most widespread is ASCII (American Standard Code for Information Interchange), which numbers 128 characters from 0 to 127: uppercase letters start at 65 ('A'), lowercase at 97 ('a'), and digits at 48 ('0'). Seven bits are enough, though in practice each character takes a byte. 'A' is stored as 65, that is, 01000001.

ASCII covers only English letters; Turkish ş, ğ, and ı are missing, as are the scripts of most of the world. Unicode fixes this by giving every character in every writing system a code point — ş, for instance, is 351. How a code point is laid out in bytes is a separate rule. UTF-8, the most common choice on the web, stores ASCII characters in one byte and others in two or more, so a word can take more bytes than it has letters. The Turkish word veri (“data”) is 4 letters and 4 bytes; şeker (“sugar”) is 5 letters but 6 bytes, because ş takes two. Java's char, by contrast, is a 16-bit UTF-16 code unit, so ş fits in a single char.

Numbers. Integers are written directly in binary. For negative numbers, computers use a scheme called two's complement. We don't need its details here, only the result: an n-bit signed integer ranges from −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1, so a byte holds −128 to 127. Numbers with a fractional part are stored in floating-point form, defined by the IEEE 754 standard. Like scientific notation, a floating-point number has a sign, a significand, and an exponent; 3.14 is stored as roughly 1.57 · 2¹. Since the significand has a fixed number of digits, most decimal fractions can only be stored approximately.

Images. A digital image is a grid of tiny squares called pixels. Each pixel's color is given by three numbers saying how much red (R), green (G), and blue (B) light to mix, usually one byte each, from 0 to 255. Pure red is (255, 0, 0), white is (255, 255, 255), and black is (0, 0, 0). The image itself is a long sequence of these triples, row after row.

Sound. Sound becomes numbers when the ADC samples it. Each measurement is a sample, and the number of samples per second is the sampling rate. An audio CD takes 44,100 samples per second, each a 16-bit integer, with separate samples for the left and right channels.

1.1.5Kinds of digital data

Digital data is also classified by how it is organized. Table 1.2 shows a common classification.

In structured data, the fields of every record are fixed in advance. Each row of a student table has an ID, a name, a department, and a GPA; this list of fields is the table's schema. A CSV (comma-separated values) file is structured too: each line is a record and each comma-separated column a field. Because every value has a known place, structured data is easy to search and sort.

Semi-structured data has no schema, or only a loose one; instead, tags describe the data as it goes. Here is a student in JSON (JavaScript Object Notation):

{ "id": 101, "name": "Alice", "courses": ["Data Structures", "Physics"] }

Each value is labeled ("id", "name"). Another student's record might have no "courses" field, or an extra "phone" field. XML (eXtensible Markup Language) does the same with opening and closing tags, as in <name>Alice</name>. Semi-structured data nests naturally — a student holds a list of courses, each course a list of grades — and nesting of this kind is a tree.

Text, images, and sound are organized by content rather than by a schema. The body of an email or the pixels of a photo don't divide into fields the way a table does, which is why such data is often called unstructured.

The lesson for data structures is that the outside shape of the data shapes the structure we choose inside the program. CSV rows fit naturally in an array or list; the nesting of JSON and XML calls for a tree; and finding a person from an email address calls for a key–value map.

1.2Data structures and algorithms

A program consists of data and the steps applied to it, and the two are not independent. How the data is stored decides which steps are easy and which are laborious; the steps needed decide how the data should be stored.

1.2.1Algorithms and data structures

A recipe is the everyday example: listed ingredients, ordered steps that each say exactly what to do, and an end. A computer algorithm needs the same, with steps precise enough for a machine — no “add a pinch of salt” — and a finite number of them.

The data structure is the groundwork and the algorithm runs on top; choose both well and the software is efficient and the problem solved systematically. Niklaus Wirth, the Swiss computer scientist, put the relationship in the title of his 1976 book: Algorithms + Data Structures = Programs.

Suppose we look up a name in a thousand-entry phone book. Unordered, the names must be checked one by one, and a name that is last or missing costs a thousand comparisons. Alphabetized, we can check the middle name and discard the right half if ours comes before it, the left half if after. Each comparison halves the candidates — 1000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1 — so 10 comparisons at most settle it. Kept in a different order, the same data allowed an algorithm a hundred times faster. The price: every new name must go in its proper place.

1.2.2What organization costs and what it buys

Data structures exist for fast, effective access. The slides picture two kitchen drawers with the same utensils, one jumbled, one divided into compartments. Finding a spoon in the first may mean handling every item; in the second, your hand goes straight to the spoons.

The subtler lesson: organization is not free. The tidy drawer makes you find the right compartment; the jumbled one takes things anywhere. Organization makes insertion a little harder and search much easier, so the choice depends on which happens more often. If one item goes in each year and something is looked for daily, organizing pays. If things go in daily and are never looked for — a wastebasket — it is wasted effort.

This trade-off is the heart of choosing a data structure. Every structure makes some operations cheap and others expensive, and that choice sets a program's speed and memory use.

1.2.3Building blocks: objects, arrays, links

However complex they look, nearly all data structures are built from three parts.

Objects. An object gathers related attributes into one unit with named fields. A student's name and ID could live in two variables, but then the programmer must remember which name goes with which number. In Java, a class bundling the two looks like this:

class Student {
  String name; // the student's name
  int id;      // student ID number
  Student(String name, int id) { this.name = name; this.id = id; }
}

A Student object keeps its name and id together in memory, and they travel together. Objects are also the basis of nodes: a node is a small object holding a value plus fields pointing to its neighbors.

Arrays. An array stores elements of one type in consecutive memory slots, and that contiguity is its great strength. Knowing where the array starts and how many bytes each element takes, we find element i with one multiplication and one addition: start address + i × element size. For 4-byte ints starting at address 1000, element 5 is at 1000 + 5 × 4 = 1020. The cost does not depend on length: ten elements or ten million, it is the same.

Links. A link points from one entity to another; Java calls it a reference. Links set up optional, directed relationships: a student points to an advisor, a city to its neighbors, a song to the next song in a playlist. A linked structure's elements can be scattered through memory, kept in order by arrows rather than by contiguity. In the slides' figure the last arrow ends in a question mark: a chain must end somewhere, and Java writes that final link to nothing as null.

Arrays versus links is one of the course's main themes. An array gives instant access by index, but its size is fixed and inserting in the middle shifts elements. A linked structure grows freely and inserts by redirecting a few arrows, but reaching element i means following the arrows from the front.

1.3Data types

A language learns from the programmer how to interpret bits: declaring a variable's type says “read these bits as an integer” or “as a character.” Types also guard a program against errors.

1.3.1Primitive types

Java has eight basic types built into the language, the primitive types, for integers, floating-point numbers, logical values, and characters. Table 1.3 lists their sizes and ranges.

The ranges follow from the rule in 1.1.4: an n-bit signed integer runs from −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. For byte, n = 8 and 2⁷ = 128, so −128 … 127. For short, 2¹⁵ = 32,768; for int, 2³¹ = 2,147,483,648, hence “about ±2.1 billion”; for long, 2⁶³ ≈ 9.22·10¹⁸. The positive side is one short because zero uses up a pattern in the non-negative half.

Primitive types share four properties. They are simple, not built from other types. They have a fixed size: an int takes 32 bits whether it holds 3 or 2 billion. The processor handles them directly; adding two ints is one instruction. And a primitive variable holds its value inside itself, which will matter in 1.4.

A fixed size means a limit. Past it, Java reports no error; the value wraps around to the other end of the range. This is overflow.

int big = Integer.MAX_VALUE;             // 2147483647
System.out.println(big + 1);             // -2147483648
long wide = (long) big + 1;
System.out.println(wide);                // 2147483648
System.out.println(0.1 + 0.2);           // 0.30000000000000004

Floating-point types are limited differently: they reach very large and very small numbers, but only approximately. A float keeps about 7 significant digits, a double about 15. In binary, 0.1 is an infinite fraction (as 1/3 is 0.333… in decimal), so memory holds an approximation. Hence the last line: 0.1 + 0.2 prints 0.30000000000000004.

1.3.2A type is values plus operations

A type is more than “the values it can take.” int and String differ not only in holding numbers versus text but in the operations that apply to them.

Integers support addition, subtraction, multiplication, and division. Strings (String) support comparison, concatenation, and substrings: "data" + "base" gives "database", and "database".substring(0, 4) gives "data". The same + adds numbers and joins strings — clear evidence that behavior belongs to the type.

Division shows it best. In Java, an int divided by an int is an int; the fraction is not rounded but dropped.

System.out.println(7 / 2);     // 3
System.out.println(7 % 2);     // 1
System.out.println(-7 / 2);    // -3
System.out.println(-7 % 2);    // -1
System.out.println(7.0 / 2);   // 3.5
System.out.println(7 / 2.0);   // 3.5
int n1 = 7, n2 = 8;
double avg1 = (n1 + n2) / 2;     // 7.0
double avg2 = (n1 + n2) / 2.0;   // 7.5

7 / 2 drops the fraction of 3.5 and gives 3. 7 % 2 is the remainder, 1, so that 7 = 2 · 3 + 1. -7 / 2 is −3, not −4, because Java truncates toward zero, and the remainder matches: −7 = 2 · (−3) + (−1). With a double operand, as in 7.0 / 2 or 7 / 2.0, the division is in floating point and gives 3.5.

Mixed types follow fixed rules. A char is really a 16-bit number and becomes an int in arithmetic, so 'A' + 1 is 66. If one side of + is a String, the other is converted to text and appended: "A" + 1 gives "A1". Evaluation runs left to right, so 1 + 2 + "x" gives "3x" but "x" + 1 + 2 gives "x12".

1.3.3Type safety

Not every operation fits every type. Multiplying text by a number means nothing in Java: for "abc" * 2 the compiler reports an error without running the program. This protective role is called type safety. Types keep errors to a minimum; their restrictions tell the programmer what is possible.

When an error is caught matters greatly. In a statically typed language like Java, types are written in the source, and the compiler checks every operation against them before the program runs: compile-time checking. Such an error is found and fixed before anyone else sees the program. Had it surfaced only at run time, the program might have worked for months and then crashed in a user's hands the first time it reached that line.

Type safety is especially valuable in data structures. A structure holds thousands of elements, added and removed all over a program, and one element of the wrong type causes trouble far from where it entered. So Java data structures are written with generics, which tell the compiler their element type (1.5).

1.4The Java memory model

Nearly every data structure rests on a variable “pointing to” data stored elsewhere, and code for linked lists, trees, or graphs is unreadable without knowing where a running Java program keeps its variables and objects.

1.4.1The call stack and the heap

A running Java program uses two main memory regions. The first is the call stack. Each method call opens a stack frame there for its parameters and local variables; when the method returns, the frame and all its locals vanish. Frames pile up, and the last opened is the first closed — hence the name.

The second is heap memory. Every object created with new, every array, and every String lives there. Heap objects belong to no frame and can outlive the method that created them.

Every Java type except the eight primitives is a reference type: arrays, String, our own classes, and every library class. Four lines show both kinds:

int x = 5;               // primitive: a value
int[] a = {7, 2, 9};     // reference → array
String s = "data";       // reference → object
int[] p = null;          // points to nothing

In Figure 1.2, the four boxes in the frame are all small and equal in size: whether the array has 3 elements or 3 million, a holds only an address. The data is on the heap.

An object no reference points to is unreachable and wastes space. Java's garbage collector periodically reclaims such objects, so memory is never freed by hand; in C that falls to the programmer, and forgetting it leaks memory.

Using the object behind a null reference fails at run time. p points to no array, so p[0] finds no element and Java throws a NullPointerException, the most common error in work with linked structures.

1.4.2Code trace: value or reference?

Assignment (=) copies the value on the right into the variable on the left. What that value is depends on the variable, as this program shows:

int x = 5;
int y = x;
y = 7;
int[] a = {1, 2, 3};
int[] b = a;
b[0] = 9;
b = new int[2];
System.out.println(x + " " + a[0]);

Table 1.4 gives the variables and the heap after each line, with objects numbered #1, #2 in order of creation.

Lines 1–3. x is primitive; 5 sits directly in the frame. int y = x; copies it, giving two independent boxes holding 5, so y = 7; leaves x at 5.

Line 4. {1, 2, 3} creates a three-element array on the heap. a holds a reference to it, drawn as an arrow.

Line 5. int[] b = a; also copies, but what it copies is the value in a — an address. The array itself is not copied: the heap still holds one array, and a and b are two arrows to it.

Line 6. b[0] = 9; follows b to the object and changes cell 0. a points to the same object, so a[0] is now 9 too. Reaching one object through several references is called aliasing: a and b are two names for one array.

Line 7. b = new int[2]; creates a new two-element array, which Java fills with 0s, and turns b's arrow toward it. a is unaffected: the address in b changed, not object #1.

Line 8. x + " " + a[0] joins 5, a space, and 9: the output is 5 9.

The whole trace reduces to one rule: = copies the value of a primitive and the address of a reference. Assigning to a reference variable redirects its arrow; assigning through it, as in b[0] = … or obj.field = …, changes the object. Our own classes behave the same way:

Student st1 = new Student("Alice", 101);
Student st2 = st1;         // a second reference, no new object
st2.id = 202;
System.out.println(st1.id);  // 202

st2 = st1 creates no student, only a second arrow, and st2.id = 202 changes the shared object, so st1.id is 202 too.

1.4.3Passing arguments to methods

In a method call, each argument is assigned to its parameter like an ordinary =. Java always passes by value: the parameter gets a copy — of the number for a primitive, of the address for a reference. Two swap methods show the consequence:

static void swap(int a, int b) {
  int tmp = a; a = b; b = tmp;
}
static void swap(int[] arr) {
  int tmp = arr[0]; arr[0] = arr[1]; arr[1] = tmp;
}

int p = 1, q = 2;
swap(p, q);
System.out.println(p + " " + q);              // 1 2
int[] nums = {1, 2};
swap(nums);
System.out.println(Arrays.toString(nums));    // [2, 1]

The rule has a limit. Had the method run arr = new int[2];, only the local arrow would move; nums would keep the old array, and the unreferenced new one would be garbage-collected after the return. A method can change an object's contents but cannot point the caller's variable elsewhere.

1.4.4Strings and comparison

String is a reference type with one big difference from arrays: a String's contents never change after creation. This is immutability. toUpperCase(), substring(), and + leave the object alone and return a new one.

String s1 = "course";
String s2 = s1;
s2 = s2.toUpperCase();
System.out.println(s1 + " " + s2);      // course COURSE
String u1 = new String("data");
String u2 = new String("data");
System.out.println(u1 == u2);           // false
System.out.println(u1.equals(u2));      // true

After two lines, s1 and s2 point to one "course" object. s2.toUpperCase() creates a new "COURSE" object, and the assignment turns s2's arrow toward it. The old object is unchanged, so s1 still prints course. An array's shared object could be changed (b[0] = 9); String has no such operation, so variables sharing a String cannot affect each other.

The last lines make a second point. Each new String("data") creates a separate heap object, so u1 == u2, which asks whether both arrows point to one object, gives false; u1.equals(u2) compares contents and gives true.

1.5Generics

A stack, list, or queue works the same whatever it holds; push and pop do not care whether the elements are integers or students. A stack class per element type wastes effort and copies every bug. Generics avoid this without giving up type safety.

1.5.1The trouble with a non-generic box

Take the simplest “data structure,” a box holding one item. To accept anything, it can use Object, the common ancestor of all Java classes:

public class ObjectBox {
  private Object item;
  public void put(Object x) { item = x; }
  public Object get() { return item; }
}

ObjectBox b = new ObjectBox();
b.put(42);                    // compiles: 42 is an Object too
String z = (String) b.get();  // compiles, but throws ClassCastException at run time

Accepting everything is exactly the problem. put(42) compiles. get() returns Object, so storing the result in a String needs a cast, (String), which the compiler cannot verify and therefore accepts. Only at run time does the 42 turn out not to be a String: ClassCastException. By the standard of 1.3.3 this is the worst case, an error caught at run time rather than compile time.

1.5.2Box<T>: one class for every type

The generic box:

public class Box<T> {
  private T item;
  public void put(T x) { item = x; }
  public T get() { return item; }
}

Box<String> b = new Box<>();
b.put("data");
String s = b.get();     // no cast needed
Box<Integer> m = new Box<>();
m.put(42);              // int → Integer
// m.put("x");          // COMPILE-TIME ERROR

<T> after the class name declares the type parameter, and inside the class T acts as a real type: item is a T, put takes one, get returns one.

For Box<String> b, the compiler substitutes String for T: b.put accepts only a String and b.get() returns one, so String s = b.get(); needs no cast. The empty brackets in new Box<>() are the diamond operator; the compiler infers the type argument from the left-hand declaration.

Box<Integer> m comes from the same class, for integers. Uncomment m.put("x") and compilation fails, since put on a Box<Integer> accepts only Integer. The error of 1.5.1 is now caught at compile time.

As Figure 1.4 sums up, code written once serves as a separate type-safe class per type argument, with compile-time type checks, no casts, and no duplication.

1.5.3Wrapper classes and autoboxing

A type parameter must be a reference type; Box<int> is illegal. Inside a generic class, T values are always handled as references, and a primitive is not one — it holds its value directly.

The fix is Java's wrapper classes, one per primitive type. A wrapper is a small heap object carrying one primitive value: Integer for int, Double for double, Character for char, Boolean for boolean, and so on. A box of integers is therefore Box<Integer>.

Java wraps automatically. An int given where an Integer is expected is placed in an Integer object — autoboxing, which the comment “int → Integer” on m.put(42) refers to. Conversely, an Integer used in arithmetic or assigned to an int has its value extracted — unboxing.

Autoboxing shortens code but sets two traps. The first is null: an empty Box<Integer> returns null from get(), and assigning that to an int makes Java try to unbox it and throw a NullPointerException. The second is comparison:

Integer i1 = 127, i2 = 127;
Integer i3 = 128, i4 = 128;
System.out.println(i1 == i2);         // true
System.out.println(i3 == i4);         // false
System.out.println(i3.equals(i4));    // true

Integer is a reference type, so == compares addresses. Java keeps ready-made objects for −128 to 127 and reuses them when boxing: both 127s point to one object and == gives true, while each 128 gets its own object and == gives false. equals compares contents and is right both times.

1.5.4Java collections

Every data structure in Java's standard library is generic; together they are the collections. Two of the most used are ArrayList<E>, an ordered list of Es that grows as needed, and Map<K,V>, which maps K keys to V values and so takes two type parameters. This code uses three collections:

ArrayList<String> list = new ArrayList<>();
list.add("Ann"); list.add("Ben"); list.add("Ann");
HashSet<String> set = new HashSet<>(list);
HashMap<Integer, String> students = new HashMap<>();
students.put(101, "Alice");
students.put(102, "Bob");
students.put(101, "Carol");
System.out.println(list.size() + " " + set.size());     // 3 2
System.out.println(students.size() + " " + students.get(101));  // 2 Carol
System.out.println(students.get(103));                  // null

A list may hold duplicates, so three adds give size 3. A HashSet holds each element once; built from the list, it drops the second “Ann” and has size 2. HashMap keys are unique: a second put with the same key overwrites the old value instead of adding a pair, so 101 now maps to “Carol” and the map has 2 pairs. For a missing key (103), get returns null.

Type parameters protect this code too: given students.put("101", "Alice"), the compiler would see a String key where an Integer belongs and refuse. The structures we write in this course are generic classes in the same way.

1.6Non-primitive data structures

A primitive holds one number, character, or logical value, but real programs handle hundreds of students, thousands of cities, millions of words, and need structures that keep many values together in a definite arrangement.

1.6.1Composite structures

Structures built from primitive types and other structures are non-primitive data structures. By the relationship among their elements they fall roughly into these groups:

• Linear: arrays and lists. The elements form a sequence; each has one before it and one after it.
• Linked: linked lists. References connecting the elements build the sequence.
• Hierarchical: trees. Each element can have one above it and several below.
• Network: graphs. Each element can be related to any number of others.
• Indexed: hash tables. An element's position is computed from its key.
• Beyond these, sets, maps, and many more.

They share three traits. They are composite, holding many values, even of different types. Most are dynamic, growing and shrinking during a run; arrays are the exception, since a Java array's length is fixed at creation. And each is specialized: one returns the latest element fast, another finds a key fast, another suits finding paths.

1.6.2Four values, eight structures

The clearest way to compare structures is to put the same data in each. Figure 1.5 arranges 7, 2, 9, 5 in eight ways, each with its own strengths and weaknesses.

(a) Array. The values occupy consecutive cells, indices 0 to 3. a[2] yields 9 in one step: by the address calculation of 1.2.3, indexed access is O(1). But the size is fixed; a fifth value has no room.

(b) Linked list. Each value has its own node pointing to the next: 7 → 2 → 9 → 5 → null. One reference to the head suffices. Adding a node redirects a few arrows, and the size is flexible. The price: reaching element i means following i arrows from the head, O(n).

(c) Stack. The values are piled with 7 at the bottom and 5, the latest, on top. Insertion (push) and removal (pop) happen only at the top: LIFO (last in, first out). The next pop returns 5.

(d) Queue. The values line up by arrival, 7 in front and 5 at the rear. Elements join at the rear and leave from the front: FIFO (first in, first out). The next removal returns 7. Stack and queue release the same values in opposite orders.

(e) Tree. The values form a hierarchy: 7 is the root, 2 and 9 its children, 5 a child of 2. The childless 9 and 5 are leaves. Exactly one path leads from the root to each node.

(f) Graph. The values are nodes and the lines edges; each node connects to two or three others. Unlike a tree, a graph need not be hierarchical: a node can be reached by several paths, and edges can form cycles. The relationship is many-to-many.

(g) Hash table. The values go into a 5-cell array at positions given by a hash function h(k), here h(k) = k mod 5, the remainder on division by 5: 5 mod 5 = 0, 7 mod 5 = 2, 9 mod 5 = 4. But 2 mod 5 is also 2, and cell 2 already holds 7. Two values in one cell is a collision, and hash tables have extra rules to resolve it. With few collisions, a search just computes the cell and looks there, so it takes O(1) on average.

(h) Set. A set holds distinct elements in no particular order. Adding 7 again changes nothing: {7, 2, 9, 5} ∪ {7} is the same set. Its close relative, the map, attaches a value to each distinct key (key → value).

1.7Abstract data types and data structures

“Stack” can mean a behavior — add and remove at the top, last in, first out — or that behavior built in memory from a particular array, index variable, and code. Keeping the two levels apart is the key to understanding and designing data structures.

1.7.1What versus how

Lists, stacks, queues, sets, maps, and graphs are ADTs, descriptions of behavior. Linked lists, arrays, and adjacency matrices are data structures, ways of building ADTs in memory and concerned with performance.

Think of a car. It offers a steering wheel and two pedals, and anyone who knows that “interface” can drive any car; whether the engine is gasoline or electric, or how the brakes work, does not concern the driver. Wheel and pedals are the ADT, engine and brakes the data structure. Different mechanisms can provide the same interface, and the driver can switch cars without noticing.

Figure 1.6 shows this for lists. The List ADT offers four operations — add, remove, get the ith element, report the size — and both an array and a linked list can provide them. They differ only in cost: an array does get(i) instantly but shifts everything to add at the front; a linked list adds at the front instantly but walks from the start for get(i). Table 1.5 compares the two concepts.

1.7.2From ADT to Java: the interface

Java has a language feature for each side of the distinction. An interface records an ADT's contract: which methods exist and what each takes and returns, with no bodies. The stack ADT's interface:

public interface Stack<E> {
  int size();         // number of elements
  boolean isEmpty();  // is the stack empty?
  void push(E e);     // add on top
  E top();            // return the top element
  E pop();            // remove the top element
}

size() returns the element count, isEmpty() whether there are none, and push(e) puts e on top. top() returns the top element without removing it; pop() removes and returns it. The interface is generic: E is the element type, so one interface serves all types.

With no fields and no bodies, the interface does not say whether elements live in an array or in linked nodes. A class says that: one declaring implements Stack<E> must give all five methods bodies. The interface is the contract, what to do; the class is the data structure, how. An ADT can have several implementations.

Code that uses the stack is client code, and Figure 1.7 shows that it depends only on the interface. The client creates a stack like this:

Stack<Integer> s = new ArrayStack<>(10);

The variable's type is the interface (Stack<Integer>); the object comes from a specific class (ArrayStack). Later code can use only interface operations such as s.push(…) and s.pop(), so switching to a linked-node stack changes only this line, new ArrayStack<>(10) becoming new LinkedStack<>().

1.7.3An implementation: ArrayStack

An array-based stack fills the array from the start: the first push goes into cell 0, the second into cell 1. The top is the last filled cell, so one variable holding its index suffices; we call it t (for top).

public class ArrayStack<E> implements Stack<E> {
  private E[] data;         // the elements
  private int t = -1;       // index of the top element
  public ArrayStack(int capacity) {
    data = (E[]) new Object[capacity];
  }
  public int size() { return t + 1; }
  public boolean isEmpty() { return t == -1; }
  public E top() {
    if (isEmpty()) return null;
    return data[t];
  }
  // push and pop
}

Piece by piece:

• implements Stack<E>: the class accepts the stack contract; its type parameter E becomes the interface's E.
• private E[] data: the elements. private blocks outside access, forcing the client through the interface and so protecting top-only access.
• private int t = -1: the top element's index. An empty stack has no top, signaled by −1, which is not a valid index.
• The constructor creates an array of the requested capacity. new E[capacity] is illegal, because the type parameter is unknown at run time and Java cannot create an array of an unknown type; instead an Object array is cast with (E[]) and assigned to data. The compiler warns of an “unchecked cast,” but it is safe: the array never leaves the class and receives only Es.
• size(): the elements fill cells 0 through t, so there are t + 1; for an empty stack, −1 + 1 = 0.
• isEmpty(): the stack is empty when t == -1.
• top(): returns null for an empty stack, otherwise the top element, data[t], without removing it; t is unchanged.

In Figure 1.8, 5 and then 8 have been pushed: t = 1 marks the 8, and cells 2 and 3 wait empty.

1.7.4push and pop

The two missing methods change the stack. The slides show them with a short client:

public void push(E e) {
  if (size() == data.length)
    throw new IllegalStateException("full");
  data[++t] = e;
}
public E pop() {
  if (isEmpty()) return null;
  E e = data[t];
  data[t--] = null;     // clear for GC
  return e;
}
s.push(5); s.push(8);
System.out.println(s.pop());
s.push(3);

push(e). If the element count equals the array length, there is no room and the method throws an IllegalStateException; pushing onto a full fixed-capacity stack is overflow. Otherwise data[++t] = e increments t, then writes at the new index. data[t++] = e would overwrite the old top.

pop(). On an empty stack the method returns null; otherwise it saves the top element in e. data[t--] = null writes null into the cell at the old t, then decrements t. Clearing the cell helps the garbage collector: a cell still pointing to the old element would keep it alive after the client was done with it. Finally the saved element is returned.

1.7.5Code trace: ArrayStack

The client runs on an empty ArrayStack of capacity 4: push(5), push(8), print pop(), push(3). Table 1.6 gives the call stack, t, and the array per step. Line numbers refer to the slides' code block: push is lines 1–5, pop 6–11, the client 12–14.

Three things stand out. Each call opens a frame (“main | push(5)”) that closes on return — the memory model of 1.4.1 at work. pop returns 8, the latest element, while 5, the first, stays put (LIFO). And push(3) reuses the just-cleared cell 1: nothing ever shifts; only t moves.

The last step reflects a design choice: this class reports popping an empty stack (underflow) by returning null rather than as an error, where some libraries throw an exception. Both are common, but the client of a null-returning stack must check results for null. And if null was itself pushed, a null from pop cannot tell “empty” from “the top was null.”

1.7.6What the operations cost

Operations are compared by the work they do, usually in Big O notation. Two meanings suffice for now. O(1): the number of steps is constant, independent of the element count. O(n): the steps grow in proportion to the element count n, so doubling the elements roughly doubles the work.

Every operation in Table 1.7 is O(1), as the code shows. size does one addition, isEmpty one comparison, top a comparison and an array access; push a comparison, an increment, and a write; pop a comparison, a read, a write, and a decrement. No method loops, and array access is one step (1.2.3). With 3 elements or 3 million, the step count is the same.

Memory, though, is proportional to capacity: a stack of capacity N reserves N cells however few it holds. That is the array's price. The capacity is fixed and push throws once it is reached; too large wastes memory, too small fills early. The remedies are to move to a larger array when full or to replace the array with linked nodes. Either way the stack ADT stays the same and only the class changes — the practical payoff of 1.7.1.

1.8Organizing data and choosing a structure

Before choosing a structure, look at how the data items relate. Are they independent, or do they form a sequence, a hierarchy, or a tangled network? The answer narrows the candidates considerably.

1.8.1Four ways to organize data

Figure 1.10 shows the four basic arrangements; Table 1.8 gives the relationship each sets up and an everyday example.

In an unordered arrangement the elements are unrelated: a classroom's students form a group, but “the student after Alice” means nothing. The questions concern membership — is Bob in this class, how many students are there? Sets and maps fit.

In a linear arrangement each element has at most one predecessor and one successor: one-to-one. In a cafeteria line everyone has one person ahead and one behind, except the first and last. Arrays, lists, linked lists, stacks, and queues are linear; they differ in which ends allow insertion and removal.

In a tree each element has at most one parent above it but may have several children: one-to-many. Family trees, organization charts, and computer folders follow this pattern; each folder has one parent folder but may hold many subfolders.

In a graph each element can relate to any number of others: many-to-many. On a road map, roads lead from each city to many others. Social-network friendships and computer networks are graphs too. The graph is the most general arrangement, with linear arrangements and trees as restricted cases.

1.8.2Choosing a data structure

The right structure follows from how the data will be used. These questions decide it:

• Can the structure be filled completely at the start? If all the data is known in advance (the twelve month names, say), it is built once and then only read; data arriving over time needs room to grow.
• Can elements be deleted? If not, the structure can be much simpler. Frequent deletion calls for a cheap way to close the gap a deleted element leaves.
• Does insertion order matter? Processing in arrival order suggests a queue; latest-first, a stack. If order is irrelevant, consider a set or a map.
• Can the elements be sorted? If they can be ordered by size or alphabetically, fast methods such as the halving search of 1.2.1 apply.
• Are elements processed in a fixed order, or is random access needed? Frequent access by position (“give me element 5”) calls for an array; for front-to-back passes a linked list will do.

In short: static structures for unchanging data, dynamic ones for frequent insertion and deletion. A static structure, such as a fixed-size array, gives the fastest access; a dynamic one, such as a linked list, adapts to change but accesses more slowly.

Figure 1.11 turns the questions into a flow. It is a starting point, not a rule: real problems often answer “yes” to several questions and then use several structures together.

1.9The fundamental data structures at a glance

Table 1.9 gathers the fundamental structures met so far, with each one's core idea and typical uses.

Each use in the table follows from a basic property of the structure.

The array underlies the others: stacks, queues, hash tables, and priority queues are often arrays inside. Images, game boards, and tables are stored as two-dimensional arrays (matrices).

The linked list suits changing sizes and frequent insertion at the front or middle: a music player adds or removes playlist songs without moving the others.

The stack embodies “undo the latest action first”: an editor pushes each action, and undo pops one and applies its inverse. The call stack of 1.4.1 follows the same rule. In bracket matching, opening brackets are pushed and each closing bracket must match the one on top.

The queue is fair waiting. Print jobs, server requests, and tasks waiting for the operating system are handled in arrival order. Breadth-first search (BFS) also takes its next node from a queue.

The tree is hierarchy: computer folders, a web page's HTML elements (the DOM, Document Object Model, in browsers), and database indexes for fast search.

The priority queue removes by priority, not arrival. An emergency room sees patients by severity, not by when they came. It is usually built on a special tree called a heap.

The map and hash table lead quickly from a key to a value: from a student ID to a record, from a word to its count in a text. A browser's cache maps addresses to page contents.

The set removes duplicates and answers “is this element present?” quickly, with direct support for union and intersection.

The graph models the most general relationships. A maps app stores cities or intersections as nodes and roads as edges and searches for the shortest path between two points. With numbers such as distances on the edges, it is a weighted graph.

1.10Common mistakes

Table 1.10 collects the chapter's mistakes. Most come from forgetting whether a variable holds a value or a reference, or from misplacing the type that decides a result.

1.11Summary

• Digital data is text, numbers, images, and sound as 0s and 1s; an ADC turns signals into numbers and a DAC turns them back. n bits give 2ⁿ values. Text uses character encodings (ASCII, Unicode), floating-point numbers IEEE 754, images pixel RGB values, sound sampling.
• An algorithm is a plan of steps for a task; a data structure organizes and stores data: Algorithms + Data Structures = Programs (Wirth). Each structure makes some operations cheaper, others dearer. The building blocks are objects, arrays, and links.
• A data type is values plus operations. Java's eight primitive types have fixed sizes and wrap around past the limit; int divided by int is an int. Type safety catches type violations at compile time.
• Local variables live in call stack frames, objects in heap memory. A primitive variable holds a value, a reference an address; = copies whichever it holds, so two references can share an object (aliasing). Parameters pass by value. The garbage collector reclaims unreachable objects.
• Generics (Box<T>) give one class for every reference type, with type errors caught at compile time. Type parameters cannot be primitive: Integer replaces int, and autoboxing converts. Java's collections are generic.
• An abstract data type says what is done (behavior); a data structure says how (memory layout). In Java an ADT is an interface, a data structure a class implementing it. With interface-typed variables, changing the implementation is a one-line edit.
• ArrayStack uses an array and a top index t: t = −1 when empty, size() = t + 1. push increments, then writes; pop reads, then clears. All operations are O(1); memory grows with capacity, and a full stack makes push throw.
• Data is unordered, linear, a tree, or a graph. Access pattern, insertion and deletion frequency, need for order, and kind of relationship decide the structure: static for stable data, dynamic for changing data.

1.12Key terms

Each term links to the course glossary, which gives its Turkish equivalent and its use in other chapters.

• digital data
• algorithm
• data structure
• data type
• primitive type
• non-primitive
• reference
• null
• heap memory
• call stack
• stack frame
• shallow copy
• immutable
• generic
• generics
• autoboxing
• unboxing
• collection
• abstract data type (ADT)
• interface
• array
• index
• capacity
• linked list
• node
• stack
• top
• overflow
• underflow
• queue
• first in, first out (FIFO)
• tree
• priority queue
• map
• hash table
• hash function
• collision
• set
• graph
• static array
• Big O

1.13Test Yourself

1. How many bits do 1,000 different values need? How is 200 written in eight bits, and what is (byte) 200 in Java?

   Answer

   Ten: 9 bits give only 2⁹ = 512 values, 10 bits 2¹⁰ = 1,024. Since 200 = 128 + 64 + 8, it is 11001000. A byte is signed and holds at most 127, so the leading 1 makes it negative: 200 − 256 = −56.

2. For int a = 9;, what do a / 4 * 4 and a * 4 / 4 give, and why do they differ?

   Answer

   8 and 9, evaluating left to right. In the first, integer division makes 9 / 4 2, losing the fraction, and 2 · 4 = 8. In the second, 9 · 4 = 36 comes first, and 36 / 4 = 9 exactly.

3. After these lines, which arrays do r and r2 point to?

   int[] r = {3, 4, 5};
   int[] r2 = r;
   r2[2] = r2[0] + r2[1];
   r2 = new int[]{0, 0, 0};
   r2[0] = 1;

   Answer

   r: [3, 4, 7], r2: [1, 0, 0]. Line 2 copies the reference; line 3 writes 3 + 4 = 7 into the shared array, changing r too. Line 4 points r2 to a new array, and line 5 changes only that.

4. After StringBuilder sb = new StringBuilder("ab"); StringBuilder sb2 = sb; sb2.append("c");, what does sb contain? What would change with String instead of StringBuilder and sb2 = sb2 + "c" instead of append?

   Answer

   "abc". A StringBuilder is mutable: sb and sb2 share one object, and append changes it. A String is immutable: sb2 + "c" creates a new object and the assignment only redirects sb2, so sb would stay "ab".

5. After Box<Double> d = new Box<>(); d.put(2.5);, what does double x = d.get() * 2; give? Does d.put(3); compile?

   Answer

   5.0: 2.5 was autoboxed into a Double and unboxed for the multiplication. d.put(3) does not compile: the int 3 can be boxed only into an Integer, which is not a Double. Write d.put(3.0).

6. An empty ArrayStack<Integer> of capacity 3 receives, in order, push(4), push(6), pop(), push(1), top(), pop(), push(2), push(8). What do the value-returning calls return? What are t and data at the end? What does a further push(5) do?

   Answer

   6, 1, 1: the first pop returns 6, top returns 1 without removing it, the second pop returns 1. Pushing 2 and 8 leaves t = 2, data = [4, 2, 8], full. push(5) finds size() = 3 = data.length and throws an IllegalStateException.

7. Of queue, array, map, linked list, set, and adjacency matrix, which are abstract data types and which are data structures?

   Answer

   Queue, map, and set are ADTs, describing possible operations; array, linked list, and adjacency matrix are data structures, fixing how data is held in memory. A queue ADT can be built on an array or a linked list, and a graph ADT stored in an adjacency matrix.

8. Which structure suits each? (a) callers waiting at a call center, (b) a company's organization chart, (c) the number of distinct visitors to a website, (d) prerequisite relationships among courses.

   Answer

   (a) Queue: callers are served in arrival order (FIFO). (b) Tree: one manager per employee, many employees per manager (one-to-many). (c) Set: repeat visitors count once; the set's size is the answer. (d) Graph: a course can have several prerequisites and several successors (many-to-many).

9. The values 10, 24, 3, and 17 go into a 7-cell table with h(k) = k mod 7. Which cells? And in a 5-cell table with k mod 5?

   Answer

   Mod 7, all four land in cell 3: 10 = 7 + 3, 24 = 21 + 3, 3 = 0 + 3, 17 = 14 + 3. Every insertion after the first collides, so lookups lose constant time. Mod 5, the cells are 0, 4, 3, 2: no collisions. How evenly the hash function spreads values decides the table's speed.

10. A client's 500-line program begins with Stack<String> s = new ArrayStack<>(100);. To escape the capacity limit, the client wants to switch to LinkedStack, which uses linked nodes. How many lines change? What if the variable had been declared as ArrayStack<String>?

    Answer

    Only the first: new ArrayStack<>(100) becomes new LinkedStack<>(); the rest uses only the five interface operations. With a class-typed variable the declaration would change too, and lines using ArrayStack-specific methods would need rewriting.

1.14Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Chapters 1 and 2: Java's basic types, references, classes and interfaces, and generics, with code close to the stack example in these notes.
• R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Sections 1.2 and 1.3: data abstraction, the separation of API from implementation, and generic stack and queue classes, through short, clear examples.
• N. Wirth, Algorithms + Data Structures = Programs (1976): the classic source for the idea that algorithms and data structures must be designed together; its first chapter presents the fundamental data types and structures from a historical perspective.

1.15References

1. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
2. Oracle, Java SE 17 API Specification: documentation for java.lang.Integer, java.lang.String, java.util.ArrayList, java.util.HashMap, and java.util.HashSet.
3. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.
4. N. Wirth, Algorithms + Data Structures = Programs, Prentice-Hall, 1976.

Related pages: Chapter 1 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.