[MUSIC]

Hi, my name is Pasan.

I'm an instructor at Treehouse.

And welcome to the Introduction to Data Structures course.

In this course, we're going to answer one fundamental question,

why do we need more data structures than a programming language provides?

Before we answer that question, some house keeping, if you will.

In this course,

we're going to rely on concepts we learned in the introduction to algorithms course.

Namely, big o notation, space and time complexity, and recursion.

If you're unfamiliar with those concepts or

just need a refresher, check out the prerequisite courses listed.

In addition, this course does assume that you have some programming experience.

We're going to use data structures that come built into nearly

all programming languages as our point of reference.

While we will explain the basics of how these structures work,

we won't be going over how to use them in practice.

If you are looking to learn how to program before digging into this content,

check the notes section of this video for helpful links.

If you are good to go, then awesome, let's start with an overview of this course.

The first thing we are going to do is to explore a data structure we are somewhat

already familiar with, arrays.

If you've written a code before, there's a high chance you have used an array.

In this course, we're going to spend some time understanding how arrays work,

what are the common operations on an array and

what are the runtimes associated with those operations?

Once we've done that,

we're going to build a data type of our own called a linked list.

In doing so, we're going to learn that there's more than one way to store data.

In fact, there's way more than just one way.

We're also going to explore what motivates us to build specific kinds of structures

and look at the pros and cons of these structures.

We'll do that by exploring four common operations.

Accessing a value, searching for a value, inserting a value, and deleting a value.

After that, we're actually going to circle back to algorithms and

implement a new one, a sorting algorithm.

In the Introductions to Algorithms course, we implemented a binary search algorithm.

A precondition to binary search was that the list needed to be sorted.

We're going to try our hand at sorting a list and

open the door to an entirely new category of algorithms.

We're going to implement our sorting algorithm onto different data

structures and explore how the implementation of one algorithm can defer

based on the data structure being used.

We'll also look at how the choice of data structure potentially influences

the runtime of the algorithm.

In learning about sorting, we're also going to encounter

another general concept of algorithmic thinking called divide and conquer.

Along with recursion, divide and

conquer will be a fundamental tool that we will use to solve complex problems.

All in due time, in the next video, let's talk about arrays.