Data Structures

Why data structures matter

In Introduction to OODSA, you modeled problems as objects. In Algorithmic Thinking, you turned those models into step-by-step methods with invariants and traces.

Now we ask a design question every programmer eventually faces:

Where should the data live so the algorithm stays simple, correct, and efficient?

A data structure is not just a container. It is a set of tradeoffs: what is fast, what is slow, what is easy to express, and what mistakes it helps prevent.

In C#, you will often choose among arrays, lists, stacks, queues, dictionaries, and sets. This lesson gives you the mental model for choosing wisely before we move into sorting and searching next.

The central idea

Different data structures arrange values in different shapes.

That shape determines the operations that feel natural:

Structure Natural question Typical strength Array / List "What is at position i?" Ordered access Stack "What was added most recently?" Undo / backtracking style behavior Queue "What arrived first?" Fair processing order Dictionary "What value belongs to this key?" Fast lookup by name/id Set "Have I seen this before?" Uniqueness

A good data structure makes your algorithm almost read like the problem statement.

If your code constantly fights the container, that is often a design smell.

You are building a feature that tracks whether a username has already been seen during import.

Which data structure best matches the core question: "Have I seen this before?"

Ordered collections

Arrays and lists store items in a sequence. That makes them great when order matters or when you need to access by index.

In C#:

• int[] has a fixed size once created.
• List<T> can grow and shrink.
• Both support index-based access like items[0].

Use a list when your algorithm says: "Keep these values in order, and I may add more as I go."

Notice how this example traces the collection as it changes, just like you practiced in Algorithmic Thinking.

```csharp
using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        List<string> tasks = new List<string>();

        tasks.Add("model problem");
        tasks.Add("write method");
        tasks.Add("test invariant");

        Console.WriteLine("First task: " + tasks[0]);
        Console.WriteLine("All tasks:");

        for (int i = 0; i < tasks.Count; i++)
        {
            Console.WriteLine(i + ": " + tasks[i]);
        }
    }
}
```

True or false:

A C# array is usually the best choice when you do not know how many items you will need and expect the collection to grow often.

Order rules as behavior

Some structures are powerful because they restrict how data comes out.

Stack: last in, first out

A stack is like a pile of plates. The most recently added item is removed first.

Useful when your algorithm needs the latest pending thing first.

Queue: first in, first out

A queue is like a checkout line. The earliest added item is removed first.

Useful when your algorithm needs fair arrival order.

These structures are not mainly about storage space. They encode a rule, which makes the algorithm harder to misuse.

```csharp
using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        Stack<string> undo = new Stack<string>();
        undo.Push("typed A");
        undo.Push("typed B");
        undo.Push("typed C");

        Console.WriteLine("Undo stack removes:");
        Console.WriteLine(undo.Pop());
        Console.WriteLine(undo.Pop());

        Queue<string> printJobs = new Queue<string>();
        printJobs.Enqueue("report.pdf");
        printJobs.Enqueue("invoice.pdf");
        printJobs.Enqueue("notes.pdf");

        Console.WriteLine("\nPrint queue removes:");
        Console.WriteLine(printJobs.Dequeue());
        Console.WriteLine(printJobs.Dequeue());
    }
}
```

Fill in the blank:

A queue removes items in ______ order.

Lookup structures

Sometimes position is not the point. You do not care that an item is at index 12; you care that it belongs to a name, id, or key.

That is where dictionaries and sets shine.

Dictionary

A Dictionary<TKey, TValue> maps a key to a value.

Example: username → login count.

Set

A HashSet<T> stores unique values and answers membership questions.

Example: has this email already appeared?

These are often the right choice when your algorithm repeatedly asks "where is the thing with this identity?" rather than "what is next in order?"

```csharp
using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        string[] visitors = { "ana", "bob", "ana", "dev", "bob", "ana" };

        Dictionary<string, int> visitCounts = new Dictionary<string, int>();
        HashSet<string> uniqueVisitors = new HashSet<string>();

        foreach (string name in visitors)
        {
            uniqueVisitors.Add(name);

            if (!visitCounts.ContainsKey(name))
            {
                visitCounts[name] = 0;
            }

            visitCounts[name]++;
        }

        Console.WriteLine("Unique visitor count: " + uniqueVisitors.Count);
        Console.WriteLine("Ana visits: " + visitCounts["ana"]);
        Console.WriteLine("Seen Zoe? " + uniqueVisitors.Contains("zoe"));
    }
}
```

You are designing a small cache where each product id should quickly retrieve a product name.

Which structure best fits this need?

How to choose

When deciding on a data structure, ask these questions in order:

1. What is the main operation? Add, remove, lookup, preserve order, enforce uniqueness?
2. What identity matters? Index, arrival time, most recent item, key, or value itself?
3. What rule should be hard to violate? FIFO, LIFO, unique-only, key-value mapping?
4. How will the algorithm read? The best choice often makes the method shorter and clearer.

A practical shortcut:

• Need positions? Use an array or list.
• Need most recent first? Use a stack.
• Need arrival order? Use a queue.
• Need key-based lookup? Use a dictionary.
• Need uniqueness? Use a set.

This completes the bridge from object models to algorithm-ready storage. Next, you will see how these choices affect sorting and searching without changing the core discipline: choose the structure that matches the problem.