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.
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!
Arrays, also called lists or Vectors in some languages.
Very closely related are Strings, which are just arrays of characters, like letters, numbers, punctuation and other written symbols.
a Matrix.
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.
Let’s take a look at this struct that’s called a “node”.
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.
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 – FIFO.
That’s the first part.
With just a small change, we can use linked lists as stacks, which are LIFO…
Last-In First-Out.
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.
For data that links arbitrarily, that include things like loops, we can use a graph data structure instead.
So that’s a whirlwind overview of pretty much all of the fundamental data structures used in computer science.
