Data Structures: Crash Course Computer Science #14 - YouTube

Hi, I'm Carrie Anne, and welcome to Crash Course Computer Science!

Last episode, we discussed a few example classic algorithms, like sorting a list of numbers

and finding the shortest path in a graph.

What we didn’t talk much about, is how the data the algorithms ran on was stored in computer

memory.

You don’t want your data to be like John Green’s college dorm room, with food, clothing

and papers strewn everywhere.

Instead, we want our data to be structured, so that it’s organized, allowing things

to be easily retrieved and read.

For this, computer scientists use Data Structures!

INTRO

We already introduced one basic data structure last episode, Arrays, also called lists or

Vectors in some languages.

These are a series of values stored in memory.

So instead of just a single value being saved into a variable, like ‘j equals 5’, we

can define a whole series of numbers, and save that into an array variable.

To be able to find a particular value in this array, we have to specify an index.

Almost all programing languages start arrays at index 0, and use a square bracket syntax

to denote array access.

So, for example, if we want to add the values in the first and third spots of our array

‘j’, and save that into a variable ‘a’, we would write a line of code like this.

How an array is stored in memory is pretty straightforward.

For simplicity, let’s say that the compiler chose to store ours at memory location 1,000.

The array contains 7 numbers, and these are stored one after another in memory, as seen here.

So when we write “j index of 0”, the computer goes to memory location 1,000, with an offset

of 0, and we get the value 5.

If we wanted to retrieve “j index of 5”, our program goes to memory location 1000,

plus an offset of 5, which in this case, holds a value of 4.

It’s easy to confuse the fifth number in the array with the number at index 5.

They are not the same.

Remember, the number at index 5 is the 6th number in the array because the first number

is at index 0.

Arrays are extremely versatile data structures, used all the time, and so there are many functions

that can handle them to do useful things.

For example, pretty much every programming language comes with a built-in sort function,

where you just pass in your array, and it comes back sorted.

So there’s no need to write that algorithm from scratch.

Very closely related are Strings, which are just arrays of characters, like letters, numbers,

punctuation and other written symbols.

We talked about how computers store characters way back in Episode 4.

Most often, to save a string into memory, you just put it in quotes, like so.

Although it doesn’t look like an array, it is.

Behind the scenes, the memory looks like this.

Note that the string ends with a zero in memory.

It’s not the character zero, but the binary value 0.

This is called the null character, and denotes the end of the string in memory.

This is important because if I call a function like “print quote”, which writes the string

to the screen, it prints out each character in turn starting at the first memory location,

but it needs to know when to stop!

Otherwise, it would print out every single thing in memory as text.

The zero tells string functions when to stop.

Because computers work with text so often, there are many functions that specifically

handle strings.

For example, many programming languages have a string concatenation function, or “strcat”,

which takes in two strings, and copies the second one to the end of the first.

We can use arrays for making one dimensional lists, but sometimes you want to manipulate

data that is two dimensional, like a grid of numbers in a spreadsheet, or the pixels

on your computer screen.

For this, we need a Matrix.

You can think of a Matrix as an array of arrays!

So a 3 by 3 matrix is really 2 an array of size 3, with each index storing an array of

size 3.

We can initialize a matrix like so.

In memory, this is packed together in order like this.

To access a value, you need to specify two indexes, like “J index of 2, then index

of 1” - this tells the computer you’re looking for the item in subarray 2 at position 1.

And this would give us the value 12.

The cool thing about matrices is we’re not limited to 3 by 3 -- we can make them any

size we want -- and we can also make them any number of dimensions we want.

For example, we can create a five dimensional matrix and access it like this.

That’s right, you now know how to access a five dimensional matrix -- tell your friends!

So far, we’ve been storing individual numbers or letters into our arrays or matrices.

But often it’s useful to store a block of related variables together.

Like, you might want to store a bank account number along with its balance.

Groups of variables like these can be bundled together into a Struct.

Now we can create variables that aren’t just single numbers, but are compound data

structures, able to store several pieces of data at once.

We can even make arrays of structs that we define, which are automatically bundled together

in memory.

If we access, for example, J index of 0, we get back the whole struct stored there, and

we can pull the specific account number and balance data we want.

This array of structs, like any other array, gets created at a fixed size that can’t

be enlarged to add more items.

Also, arrays must be stored in order in memory, making it hard to add a new item to the middle.

But, the struct data structure can be used for building more complicated data structures

that avoid these restrictions.

Let’s take a look at this struct that’s called a “node”.

It stores a variable, like a number, and also a pointer.

A pointer is a special variable that points, hence the name, to a location in memory.

Using this struct, we can create a linked list, which is a flexible data structure that

can store many nodes.

It does this by having each node point to the next node in the list.

Let’s imagine we have three node structs saved in memory, at locations 1000, 1002 and 1008.

They might be spaced apart, because they were created at different times, and other data

can sit between them.

So, you see that the first node contains the value 7, and the location 1008 in its “next”

pointer.

This means that the next node in the linked list is located at memory location 1008.

Looking down the linked list, to the next node, we see it stores the value 112 and points

to another node at location 1002.

If we follow that, we find a node that contains the value 14 and points back to the first

node at location 1000.

So this linked list happened to be circular, but it could also have been terminated by

using a next pointer value of 0 -- the null value -- which would indicate we’ve reached

the end of the list.

When programmers use linked lists, they rarely look at the memory values stored in the next

pointers.

Instead, they can use an abstraction of a linked list, that looks like this, which is

much easier to conceptualize.

Unlike an array, whose size has to be pre-defined, linked lists can be dynamically extended or

shortened.

For example, we can allocate a new node in memory, and insert it into this list, just

by changing the next pointers.

Linked Lists can also easily be re-ordered, trimmed, split, reversed, and so on.

Which is pretty nifty!

And pretty useful for algorithms like sorting, which we talked about last week.

Owing to this flexibility, many more-complex data structures are built on top of linked lists

The most famous and universal are queues and stacks.

A queue – like the line at your post office – goes in order of arrival.

The person who has been waiting the longest, gets served first.

No matter how frustrating it is that all you want to do is buy stamps and the person in

front of you seems to be mailing 23 packages.

But, regardless, this behavior is called First-In First-Out, or FIFO.

That’s the first part.

Not the 23 packages thing.

Imagine we have a pointer, named “post office queue”, that points to the first node in

our linked list.

Once we’re done serving Hank, we can read Hank’s next pointer, and update our “post

office queue” pointer to the next person in the line.

We’ve successfully dequeued Hank -- he’s gone, done, finished.

If we want to enqueue someone, that is, add them to the line, we have to traverse down

the linked list until we hit the end, and then change that next pointer to point to

the new person.

With just a small change, we can use linked lists as stacks, which are LIFO…

Last-In First-Out.

You can think of this like a stack of pancakes... as you make them, you add them to the top

of stack.

And when you want to eat one, you take them from the top of the stack.

Delicious!

Instead of enqueueing and dequeuing, data is pushed onto the stack and popped from the stacks.

Yep, those are the official terms!

If we update our node struct to contain not just one, but two pointers, we can build trees,

another data structure that’s used in many algorithms.

Again, programmers rarely look at the values of these pointers, and instead conceptualize

trees like this: The top most node is called the root.

And any nodes that hang from other nodes are called children nodes.

As you might expect, nodes above children are called parent nodes.

Does this example imply that Thomas Jefferson is the parent of Aaron Burr?

I’ll leave that to your fanfiction to decide.

And finally, any nodes that have no children -- where the tree ends -- are called Leaf Nodes.

In our example, nodes can have up to two children, and for that reason, this particular data

structure is called a binary tree.

But you could just as easily have trees with three, four or any number of children by modifying

the data structure accordingly.

You can even have tree nodes that use linked lists to store all the nodes they point to.

An important property of trees – both in real life and in data structures – is that

there’s a one-way path from roots to leaves.

It’d be weird if roots connected to leaves, that connected to roots.

For data that links arbitrarily, that include things like loops, we can use a graph data

structure instead.

Remember our graph from last episode of cities connected by roads?

This can be stored as nodes with many pointers, very much like a tree, but there is no notion

of roots and leaves, and children and parents…

Anything can point to anything!

So that’s a whirlwind overview of pretty much all of the fundamental data structures

used in computer science.

On top of these basic building blocks, programmers have built all sorts of clever variants, with

slightly different properties -- data structures like red-black trees and heaps, which we don’t

have time to cover.

These different data structures have properties that are useful for particular computations.

The right choice of data structure can make your job a lot easier, so it pays off to think

about how you want to structure your data before you jump in.

Fortunately, most programming languages come with libraries packed full of ready-made data structures.

For example, C++ has its Standard Template Library, and Java has the Java Class Library.

These mean programmers don’t have to waste time implementing things from scratch, and

can instead wield the power of data structures to do more interesting things, once again

allowing us to operate at a new level of abstraction!

I’ll see you next week.