Introduction to Data Structures and Algorithms

Primitive and non-primitive; linear and non-linear

Books sort data structures in two steps. First, into two families: primitive (one value each, like an int) and non-primitive (many values). Then the non-primitive family splits into two kinds: linear and non-linear. Here is the whole family tree:

Good to know: Java has exactly eight primitive types (all shown above; char holds one character, like 'A'), and Java itself calls them primitive types, not data structures. Some books list them as "primitive data structures" because they are the simplest building blocks. Either way, they hold one value each.

Here is how the two kinds of non-primitive structures compare:

The six main structures of this course

Here are the six structures you will learn, each with a real-life picture. Tap a name to open its lesson:

Quick check: classify each one

Five traits every algorithm has

An algorithm must have all five of these traits. Miss one, and it is just a vague idea:

1. Input: takes zero or more values to work with.
2. Output: produces at least one result related to the goal.
3. Definiteness: each step is clear and unambiguous, with no guesswork.
4. Finiteness: it stops after a limited number of steps.
5. Effectiveness: each step is simple enough to actually be carried out.

Picture an algorithm as a machine. This one finds the highest score: it looks at each score, keeps the highest one seen so far, and shows it at the end. Each part of the machine shows one trait:

To see the traits at work, here are three sets of "steps" that each break one trait:

Not all algorithms are equal

Many algorithms can solve the same problem, and some are much faster. Try it: both players below hunt for the same secret number.

Why only 7? Each "too low" or "too high" throws away about half of what is left. In the worst case, the numbers still possible go 100 → 50 → 25 → 12 → 6 → 3 → 1, so by the 7th guess only one number is left. Simple search may need all 100.

Good to know: binary search only works because the numbers 1 to 100 are in order. "Too low" can rule out the whole lower half only when the values are sorted. You will write it in Java in the Searching lesson, and the same halving idea powers BST search.

Both algorithms solve the same problem, but one is far faster. That is the whole point of this course: data structures + algorithms = programs that run fast and use memory wisely.

Algorithm vs. program, coding vs. programming

These four words are easy to mix up. Here is what each one means:

Here is the algorithm from the table (ask for two numbers, add them, show the result) next to its Java program:

One algorithm can become many programs. Written in Python or C, the code would look different (a different program), but the three steps would be the same (the same algorithm).

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    System.out.print("Enter first number: ");   // step 1
    int a = in.nextInt();
    System.out.print("Enter second number: ");
    int b = in.nextInt();
    int sum = a + b;                             // step 2
    System.out.println(sum);                     // step 3
  }
}

 1public class Main {
 2  // The algorithm, step by step:
 3  // 1. If the score is below 0 or above 100, the answer is "Invalid".
 4  // 2. Otherwise, if the score is 75 or higher, the answer is "Passed".
 5  // 3. Otherwise, the answer is "Failed".
 6  static String result(int score) {
 7    // YOUR CODE: turn steps 1 to 3 into Java.
 8
 9    return "";
10  }
11
12  public static void main(String[] args) {
13    System.out.println(result(88));    // expected: Passed
14    System.out.println(result(75));    // expected: Passed
15    System.out.println(result(74));    // expected: Failed
16    System.out.println(result(-5));    // expected: Invalid
17    System.out.println(result(101));   // expected: Invalid
18  }
19}

 1static String result(int score) {
 2  if (score < 0 || score > 100) {
 3    return "Invalid";
 4  } else if (score >= 75) {
 5    return "Passed";
 6  } else {
 7    return "Failed";
 8  }
 9}

Data structure, algorithm, or both?

This course is called Data Structures and Algorithms, and its lessons teach both. A data structure is a way to store and organize data (see Part 1 ). An algorithm is a list of steps for doing a task (see above ). Many lessons teach both at once, so they show two labels under the title: a data structure, plus the algorithms that work on it (search it, add to it, remove from it). Arrays is one of them.

Two more words appear in later lessons:

• An abstract data type (ADT) says what a collection can do (its operations), not how it is stored. Sets and maps are ADTs; a hash table is one data structure that can store them (you will meet sets, maps, and hash tables near the end of the course).
• A technique is a way of building many algorithms, like recursion (a method that calls itself) or hashing (also near the end of the course).

Every lesson shows these labels under its title. Here is the whole course at a glance: