Data Structures and Dynamic Arrays

MIT 6.006 Introduction to Algorithms, lecture 2, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part explains the difference between what a data structure promises to do and how it actually does it, then starts on the simplest version: a fixed-length sequence of items stored in an array.

Key ideas

An interface says what you want to do with your data. A data structure says how it gets done. The same interface can be built in many different ways. 0:57
The lecture focuses on two interfaces, sets and sequences. A sequence keeps items in a specific order, like first, second, and last. A set is about the values themselves, which can be kept sorted and searched. 3:27
A static sequence has a fixed number of items. You can read or change any item by its position, but you cannot add or remove items. 5:41
The natural way to build a static sequence is a static array, which is a block of memory where each item sits in a numbered spot. 7:50
In the word RAM model, memory is a row of numbered words, and you can jump to any word equally quickly. That fast jump is what makes arrays work. 9:29

Words to know

interface: The list of things you are allowed to do with some data, and what each action should do. It is the promise, not the method behind it.
data structure: A way of storing data in memory, along with the steps (algorithms) for doing each action on it quickly.
static array: A fixed-size row of storage spots, each holding one item and numbered from 0, so any item can be reached by its number.
word RAM: A simple model of computer memory where memory is split into equal-sized words, and any word can be read or written directly by its number.

Example

Think of a row of numbered lockers at a gym. The interface is the rule: you can put a bag in locker 5, take a bag out of locker 5, or count how many lockers there are. The data structure is how the lockers are actually built and labeled so that finding locker 5 takes almost no time. Many different locker designs could follow the same rule.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains how an array stores items side by side in memory so any item can be found quickly, and why inserting into the middle of a sequence changes the positions of the items after it.

Key ideas

An array is a block of memory where all the items sit right next to each other. Because of this, you can find any item by starting at the block's start address and adding the item's index. 10:22
Reading or changing an item at a given index takes constant time, meaning the time stays the same no matter how big the array is. This is because finding the spot is just one quick addition. 11:24
Making a new array takes linear time, meaning the time grows in step with its size, because the memory must be set to starting values. Looking up the length is constant time, since the length is stored as a number. 13:11
Inserting an item in the middle of a sequence shifts every later item one spot over, so their indexes all go up by 1. Only the new positions count for later lookups. 18:34
Inserting at the end leaves all the old indexes the same, but inserting at the front shifts every item's index up by 1. 19:37

Words to know

index: The position number of an item in a sequence, starting from 0 for the first item.
consecutive: Following one after another with no gaps, like houses on one street with no empty lots between them.
constant time: A task whose time does not get longer as the amount of data gets bigger.
word size: How many bits a computer handles at once as one unit. The lesson says it has to grow at least as fast as log n so that every item in memory can be given an address.

Example

Think of a row of numbered mailboxes built one after another on the same street. If you know where box 0 is and you want box 7, you just walk 7 boxes past it, so you go straight there without checking each box. If a new box is added at position 2, every box after it has to be renumbered by one.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part explains why some ways of storing a list are fast for adding and removing items and others are slow, and it introduces the linked list as a first answer.

Key ideas

Adding or removing items at the front, or at the end, is a special case that can be made faster than adding or removing items anywhere in the list. Doing every operation in constant time (the same amount of work no matter how long the list is) is not possible, but these special cases can be done that way. 20:43
A linked list stores each value in a node, which is a small box holding the value and a pointer (an address that says where the next box is). The pointers link the boxes in order, and a head pointer marks the first box. 21:32
A static array is slow for changes at the front. If you insert a new first item, every other item has to shift over one spot, which takes time proportional to the list's length. 25:50
A static array also cannot grow by one. You would have to ask for a new, bigger array and copy everything over, which takes linear time. 28:52
A linked list can change order just by changing pointers, without moving any nodes. Adding a new first item is therefore efficient: you make a new node and point it at the old head. 29:33

Words to know

node: A small container that holds one value and a pointer to the next container.
pointer: A stored address that tells the computer where something else lives in memory.
head: The pointer to the first node in a linked list. It is how you get into the list.
static array: A fixed-size block of slots in memory. Its size cannot be changed once it is made.

Example

Picture a scavenger hunt where each clue tells you where to find the next clue. If you want to add a new first clue, you only need to write it so that it points to the old first clue, and then hand it out as the start. You do not have to move or rewrite any of the other clues. A numbered row of lockers works differently: adding a locker at the front means relabeling every locker behind it.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains why linked lists and static arrays each fall short, and how a dynamic array keeps spare room so it can grow without slowing down every insert.

Key ideas

A linked list can add or remove items at the front in constant time, meaning the time stays the same no matter how long the list is. Getting the ith item is slow, because you must follow the next pointers i times. 30:37
Keeping an extra pointer to the last item, called a tail, makes getting the last item fast. This is an example of data structure augmentation: adding extra information and keeping it up to date. 32:57
A dynamic array does not need its size to match the number of items exactly. Its size stays at least n and at most some constant times n, such as 2n, so it has spare room at the end. 36:11
The data structure keeps a length value that tracks how many slots hold real data. To add at the end, you put the new item in the next free slot and increase length by one. 37:19
When the array is completely full, it must be made bigger. Unlike a static array, which resizes on every insert, a dynamic array only resizes sometimes. 39:36

Words to know

pointer: A stored address that tells the computer where another piece of data lives, like a note saying which shelf to check next.
constant time: A task takes about the same amount of time no matter how big the collection is.
dynamic array: A list-like container that can grow or shrink, because it keeps some empty spare room behind the items it holds.
data structure augmentation: Adding an extra stored value to a data structure, such as a tail pointer, so some task becomes faster, and then keeping that value updated every time the structure changes.

Example

Think of a bookshelf with some empty slots at the right end. You add new books in the next empty slot and keep a note of how many books are on it. When the shelf is full, you buy a bigger one, but you do not do this every time you add a single book.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:11

This part explains why a dynamic array that doubles in size when full can still add items to the end quickly on average.

Key ideas

When an array is full, it needs a new, bigger array. Adding only a few slots each time means copying the items over and over, which is wasteful. 41:18
Doubling the size makes resizing happen only at sizes 1, 2, 4, 8, 16, and so on. The total copying work across all those resizes adds up to about n, which is linear. 43:20
Amortized means averaging over a whole sequence of operations. A few expensive resizes are paid for by many cheap inserts, so each insert at the end is constant amortized. 46:45
Dynamic arrays keep get_at and set_at fast, in constant time. Insert at the end is constant amortized, but it is not quite as good as constant in the worst case. 49:05

Words to know

amortized: Averaged out over a whole series of operations, so that one slow step is balanced by many fast ones.
allocate: To set aside space in memory for a new array.
geometric series: A list of numbers where each number is a fixed multiple of the one before, like 1, 2, 4, 8. Its total is dominated by the last, biggest term.
constant factor: A fixed number that multiplies the running time. It changes how fast something is in practice but not its overall pattern of growth.

Example

Think of a bookshelf that fills up. If you buy a shelf just one slot bigger each time, you have to move all your books again and again. If you buy one twice as big each time, you move books only rarely, so the moving cost spreads out over all the books you add.

3 checked practice questions for this part are in the app.

← Lecture 1: Algorithms and Computation · Lecture 3: Sets and Sorting →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York