Introduction to Data Structures

Why this lesson matters

You already know how to program in Java. This course is about sharpening the next skill: recognizing the right data organization for the problem in front of you.

A data structure is not just a container. It is a set of tradeoffs:

• How fast can we read something?
• How fast can we insert or delete?
• Do we preserve order?
• Can we find items by key?
• How much memory do we spend?

This first lesson sets the mental model. Later, we will zoom into patterns like Recursion, Sliding Windows, Trees, and Dynamic Programming, but today we focus on the foundation: what data structures are and how to reason about them.

What is a data structure?

A data structure is a way to store and organize data so that specific operations become easier, faster, or more reliable.

Think of raw data as books arriving at a library. You could pile them on the floor, but then finding one book is painful. If you arrange them by category, author, or ID, certain tasks become much easier.

Common examples:

• Array: contiguous indexed storage
• List: ordered sequence of elements
• Stack: last-in, first-out access
• Queue: first-in, first-out access
• Set: unique values
• Map: key-value lookup
• Tree: hierarchical relationships
• Graph: network relationships

The key idea: structure is chosen based on the operations you care about most.

You are given a collection of user IDs and need to determine whether ID 8472 is present.

Which core operation are you performing?

Same data, different cost

Two programs can produce the same answer but require very different work.

For example, arrays give fast access when you already know the index. But if you only know the value, you may need to scan from left to right.

This is the beginning of data-structure thinking:

• Index known? Direct access can be fast.
• Value unknown? You may need search.
• Order important? Some structures preserve it; others do not.
• Frequent insert/delete? Contiguous storage may become expensive.

Here is a small Java example that counts work instead of relying on timing, which can be noisy.

```java
public class Main {
    static int comparisons = 0;

    static int linearSearch(int[] values, int target) {
        comparisons = 0;
        for (int i = 0; i < values.length; i++) {
            comparisons++;
            if (values[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ids = {101, 202, 303, 404, 505};

        System.out.println("Direct access: " + ids[3]);

        int index = linearSearch(ids, 404);
        System.out.println("Linear search index: " + index + ", comparisons: " + comparisons);

        linearSearch(ids, 999);
        System.out.println("Searching missing value comparisons: " + comparisons);
    }
}
```

True or false: A data structure choice can change runtime even when the program's visible output stays exactly the same.

The behavior matters first

In Java, you often program to an interface:

• List<E> describes ordered list behavior.
• Set<E> describes unique-element behavior.
• Map<K,V> describes key-value lookup behavior.
• Queue<E> describes first-in, first-out behavior.

The implementation decides the internal tradeoffs. For example, Queue<String> tells you the behavior you need, while ArrayDeque<String> is one efficient implementation.

This separation is powerful: first decide the operation pattern, then choose the implementation.

```java
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    static void processNext(Queue<String> tasks) {
        String task = tasks.remove();
        System.out.println("Processing: " + task);
    }

    public static void main(String[] args) {
        Queue<String> tasks = new ArrayDeque<>();
        tasks.add("Build login");
        tasks.add("Ship order");
        tasks.add("Send email");

        processNext(tasks);
        processNext(tasks);

        System.out.println("Remaining: " + tasks);
    }
}
```

Translate problem verbs

When solving DSA problems, pay attention to the verbs in the prompt. They often reveal the structure.

Prompt clue What it suggests “Find by position” Indexed sequence, often array/list “Check if seen before” Set or map “Count frequency” Map from value to count “Process in arrival order” Queue “Undo most recent action” Stack “Represent hierarchy” Tree

This is not memorization. It is pattern recognition.

A strong approach:

1. Identify the dominant operation.
2. Ask what must be preserved: order, uniqueness, hierarchy, key lookup.
3. Pick the simplest structure that supports those needs efficiently.
4. Only then worry about implementation details.

Fill in the blank:

Hiding the internal representation of a structure behind operations like add, remove, contains, or get is called ____.

Java gives you a toolbox

Java's standard library already provides many general-purpose data structures. Your job in interviews and real systems is often to choose the right one.

Here is a common pattern: count occurrences while preserving first-seen order. A LinkedHashMap gives us key-value counting plus predictable iteration order.

```java
import java.util.LinkedHashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        String[] names = {"Maya", "Leo", "Maya", "Nina", "Leo", "Maya"};

        Map<String, Integer> counts = new LinkedHashMap<>();

        for (String name : names) {
            counts.put(name, counts.getOrDefault(name, 0) + 1);
        }

        System.out.println("Name counts: " + counts);
        System.out.println("Maya appeared: " + counts.get("Maya") + " times");
    }
}
```

You receive a stream of event names and need to count how many times each event name occurs.

Which structure is the best starting point?

What you should take forward

Data structures are about organizing data around operations.

Before choosing one, ask:

• Do I need fast lookup?
• Do I need order?
• Do I need uniqueness?
• Do I need key-value association?
• Do I need hierarchy?
• What operation happens most often?

As we continue through this section, keep this lens active. The upcoming lessons will build on this foundation by showing how structure and patterns work together to solve problems cleanly.