Imagine that I give you 10,000 pieces of paper containing people's names. Then I ask you to find one particular person.

Your first instinct might be to spread all of the papers across a table and start looking through them.

But what if I let you organize the papers first?

You could sort them alphabetically.

Now finding "Maya Rodriguez" is much easier.

Or perhaps you know that you will frequently need to add and remove names from the collection. Maybe a different organization would work better.

The important idea is this: how we organize information affects what operations we can perform efficiently.

This is the fundamental idea behind data structures.

A data structure is a way of organizing and storing data so that we can use it efficiently.

Think about the difference between these two things:

Data:

Data structure:
A particular organization of those values that makes certain operations easier.

There is no single "best" data structure.

A structure that is excellent for adding items might be terrible for searching. A structure that makes searching extremely fast might require additional memory or extra work when data changes.

Choosing a data structure is therefore an engineering decision.

Whenever we encounter a new data structure, ask four questions:

1. How do we access an item?
2. How do we search for an item?
3. How do we add an item?
4. How do we remove an item?

Then ask:

How much time does each operation require?

We will use Big-O notation from our previous class to answer that question.

Let's start with something you have probably used before: an array.

An array stores a collection of values in a sequence of positions. You can imagine an array as a row of numbered boxes:

The number underneath each position is called its index. Notice that the first position is usually index 0 rather than index 1. This means the value 93 is at index 2.

Suppose an array contains one million values. If I ask for the first value, the computer can find it. If I ask for the 500,000th value, the computer can also find it directly. It does not need to inspect the first 499,999 values.

Conceptually, an array can calculate where an element lives using its index. If each element requires the same amount of memory, the address can be calculated from the starting address and the index. This means accessing an array element is approximately .
This is one of the most useful properties of arrays.

Here is what an array-like structure looks like in Python:

arrays.py · python COPY

numbers = [42, 17, 93, 8, 51]

print(numbers[0])
print(numbers[2])
print(numbers[4])

numbers[2] = 100

print(numbers)

Python calls this structure a list. Python lists behave much like dynamic arrays, although the implementation contains additional details that we don't need to worry about yet.

Imagine this array:

Now we want to insert 25 between 20 and 30.

We can't simply place 25 at index 2 because 30 is already there.

We have to move 30, 40, and 50 one position to the right:

If the array contains elements and we insert near the beginning, we may need to move many elements.

That means inserting into the middle of an array can require:

A traditional array has a fixed amount of space.

Imagine that we allocate space for exactly five elements:

What happens when we want to add a sixth?

The computer may need to:

1. Allocate a larger block of memory.
2. Copy the existing elements into it.
3. Add the new element.
4. Release the old memory.

This sounds expensive—and occasionally it is.

But dynamic arrays use a clever trick: they usually allocate extra capacity before they need it.

Most individual additions are therefore cheap, even though occasionally the entire array has to be copied.

Suppose a dynamic array has capacity 4. The first four insertions are cheap. The fifth insertion requires a resize and copying several elements.

Then the next several insertions are cheap again.

So although one particular insertion may require work, the average cost of many insertions can be approximately constant. This idea is called amortized analysis.

For dynamic arrays, appending to the end is generally considered:

This is an important example of why algorithm analysis isn't always as simple as counting one operation.

What if we don't require our data to sit next to each other in memory?

Instead, each element can contain two pieces of information:

1. The value itself.
2. A reference to the next element.

This creates a linked list.

Conceptually:

Each element is called a node.

The final node points to nothing, usually represented by .

Imagine:

We want to insert X between B and C.

Instead of moving C and everything after it, we can change the references:

Only a small number of references need to change.

If we already know where the insertion belongs, the operation can be approximately:

But there is a catch.

How do we find the location in the first place?

With an array, we can jump directly to index 500:

With a linked list, we have to start at the beginning and follow the links:

That takes approximately:

So the tradeoff is roughly:

Array: fast random access, potentially expensive insertion.
Linked list: slow random access, potentially cheap insertion/removal.

Neither is universally better.

Now let's forget about arrays and linked lists for a moment and think about a stack of objects.

If you put a book on top of a stack, where can you remove it?

From the top.

If you add another book, where does it go?

On top.

This gives us the defining rule of a stack:

Last In, First Out (LIFO).

The most recently added item is the first item removed.

A stack typically provides two fundamental operations:

• Push: Add an item to the top.
• Pop: Remove the item from the top.

We may also have:

• Peek: Look at the top item without removing it.
• IsEmpty: Determine whether the stack contains anything.

Here is a simple Python implementation:

stack.py · python COPY

stack = []

stack.append("A")
stack.append("B")
stack.append("C")

print(stack[-1])

item = stack.pop()

print(item)
print(stack)

Python's append and pop operations let us easily use a list as a stack.

Stacks are surprisingly useful.

Undo operations: Every time you perform an action, the program can push it onto a stack. Undo removes the most recent action.

Web browser history: Your navigation history can be thought of as a sequence that supports moving backward through recent pages.

Function calls: Programming languages use a call stack to keep track of functions that have been called.

Expression evaluation: Compilers and calculators use stacks when processing mathematical expressions.

The important lesson is that the data structure isn't interesting because of what it looks like. It is interesting because its rules match a problem we need to solve.

Now imagine a line at a theme park.

Who gets served first?

The person who arrived first.

This is a queue.

Queues follow:

First In, First Out (FIFO).

The first item added is the first item removed.

Queues appear whenever things need to wait their turn.

Examples include:

• Print jobs waiting for a printer
• Messages waiting to be processed
• Customers waiting for service
• Tasks waiting for a processor
• Packets waiting to travel through a network
• People waiting for an event

Queues are especially important because they allow a system to handle work that arrives faster than it can immediately process it.

Stacks and queues can contain exactly the same data.

The difference is which item we remove.

Stack:

Remove .

Queue:

Remove .

This tiny difference produces completely different behavior.

Let's imagine three different applications.

Application 1: Student roster
We frequently need to access students by their position in a list.

An array-like structure is attractive because indexed access is .

Application 2: Undo button
We always want to undo the most recent action.

A stack is a natural match because it provides LIFO behavior.

Application 3: Print server
Documents should generally be printed in the order they arrived.

A queue is a natural match because it provides FIFO behavior.

The key question is not:

"Which data structure is best?"

The better question is:

"Which operations does my problem need to perform efficiently?"

We started today's class with a simple question:

How should we organize information?

Now we have several answers.

Structure	Strength	Tradeoff
Array	Fast indexed access	Insertion can require shifting
Linked list	Easy insertion/removal at a known node	Slow random access
Stack	Fast LIFO operations	Only the top is directly accessible
Queue	Fast FIFO operations	Access is restricted to the ends

And this is only the beginning.

In future classes we will encounter hash tables, trees, heaps, graphs, and other structures.

Each one exists because it makes certain operations easier or more efficient.

You are designing a robot that works in a warehouse. The robot receives tasks such as:

• Move box A to shelf 12.
• Pick up package B.
• Deliver package C.
• Return to the charging station.

Suppose tasks normally need to be completed in the order they arrive.

What data structure should the robot use to store its pending tasks?

Now change the problem: Some tasks are emergencies and must be handled before ordinary tasks. Does your original data structure still make sense? If not, what property would a better data structure need?

We will return to this idea when we study priority queues and heaps.