1 00:00:00,000 --> 00:00:09,382 [MUSIC] 2 00:00:09,382 --> 00:00:10,815 Hi, my name is Pasan. 3 00:00:10,815 --> 00:00:12,214 I'm an instructor at Treehouse. 4 00:00:12,214 --> 00:00:15,495 And welcome to the Introduction to Data Structures course. 5 00:00:15,495 --> 00:00:18,846 In this course, we're going to answer one fundamental question, 6 00:00:18,846 --> 00:00:23,280 why do we need more data structures than a programming language provides? 7 00:00:23,280 --> 00:00:27,030 Before we answer that question, some house keeping, if you will. 8 00:00:27,030 --> 00:00:27,730 In this course, 9 00:00:27,730 --> 00:00:32,430 we're going to rely on concepts we learned in the introduction to algorithms course. 10 00:00:32,430 --> 00:00:37,310 Namely, big o notation, space and time complexity, and recursion. 11 00:00:37,310 --> 00:00:39,370 If you're unfamiliar with those concepts or 12 00:00:39,370 --> 00:00:43,590 just need a refresher, check out the prerequisite courses listed. 13 00:00:43,590 --> 00:00:48,270 In addition, this course does assume that you have some programming experience. 14 00:00:48,270 --> 00:00:51,160 We're going to use data structures that come built into nearly 15 00:00:51,160 --> 00:00:54,520 all programming languages as our point of reference. 16 00:00:54,520 --> 00:00:58,133 While we will explain the basics of how these structures work, 17 00:00:58,133 --> 00:01:01,076 we won't be going over how to use them in practice. 18 00:01:01,076 --> 00:01:05,136 If you are looking to learn how to program before digging into this content, 19 00:01:05,136 --> 00:01:08,195 check the notes section of this video for helpful links. 20 00:01:08,195 --> 00:01:12,480 If you are good to go, then awesome, let's start with an overview of this course. 21 00:01:12,480 --> 00:01:16,613 The first thing we are going to do is to explore a data structure we are somewhat 22 00:01:16,613 --> 00:01:18,469 already familiar with, arrays. 23 00:01:18,469 --> 00:01:22,583 If you've written a code before, there's a high chance you have used an array. 24 00:01:22,583 --> 00:01:27,123 In this course, we're going to spend some time understanding how arrays work, 25 00:01:27,123 --> 00:01:29,659 what are the common operations on an array and 26 00:01:29,659 --> 00:01:32,947 what are the runtimes associated with those operations? 27 00:01:32,947 --> 00:01:34,072 Once we've done that, 28 00:01:34,072 --> 00:01:37,900 we're going to build a data type of our own called a linked list. 29 00:01:37,900 --> 00:01:41,870 In doing so, we're going to learn that there's more than one way to store data. 30 00:01:41,870 --> 00:01:44,960 In fact, there's way more than just one way. 31 00:01:44,960 --> 00:01:49,180 We're also going to explore what motivates us to build specific kinds of structures 32 00:01:49,180 --> 00:01:52,510 and look at the pros and cons of these structures. 33 00:01:52,510 --> 00:01:55,410 We'll do that by exploring four common operations. 34 00:01:55,410 --> 00:01:59,740 Accessing a value, searching for a value, inserting a value, and deleting a value. 35 00:02:00,960 --> 00:02:03,870 After that, we're actually going to circle back to algorithms and 36 00:02:03,870 --> 00:02:06,900 implement a new one, a sorting algorithm. 37 00:02:06,900 --> 00:02:12,270 In the Introductions to Algorithms course, we implemented a binary search algorithm. 38 00:02:12,270 --> 00:02:16,626 A precondition to binary search was that the list needed to be sorted. 39 00:02:16,626 --> 00:02:19,466 We're going to try our hand at sorting a list and 40 00:02:19,466 --> 00:02:22,878 open the door to an entirely new category of algorithms. 41 00:02:22,878 --> 00:02:26,635 We're going to implement our sorting algorithm onto different data 42 00:02:26,635 --> 00:02:30,651 structures and explore how the implementation of one algorithm can defer 43 00:02:30,651 --> 00:02:32,867 based on the data structure being used. 44 00:02:32,867 --> 00:02:36,601 We'll also look at how the choice of data structure potentially influences 45 00:02:36,601 --> 00:02:39,030 the runtime of the algorithm. 46 00:02:39,030 --> 00:02:41,760 In learning about sorting, we're also going to encounter 47 00:02:41,760 --> 00:02:46,760 another general concept of algorithmic thinking called divide and conquer. 48 00:02:46,760 --> 00:02:48,260 Along with recursion, divide and 49 00:02:48,260 --> 00:02:52,750 conquer will be a fundamental tool that we will use to solve complex problems. 50 00:02:52,750 --> 00:02:55,800 All in due time, in the next video, let's talk about arrays.