In computer science a data structure is a construct that allows us to organize and store data in our programs.
In this course we're going to learn about two introductory data structures - arrays and linked lists! We'll look at common operations and how the runtimes of these operations affect our everyday code.
For the rest of the course we're going to bring our knowledge of algorithms and data structures together to solve the problem of sorting data using the merge sort algorithm
What you'll learn
Arrays
Linked lists
Merge sort
Divide and conquer
Recursion
Syllabus
Exploring Arrays
If you have some programming experience you've undoubtedly run into the array type. Arrays are a simple way of storing data in an ordered, indexed list and in this stage we're going to look at how an array is created along with some of the operations we can carry out on the stored data
Chevron 8 steps
Introduction
2:56
Array Basics
5:40
instruction
Array Characteristics and Storage
Accessing a Value in an Array
6:45
Recap: Array Basics
5 questions
Array Search, Insert and Delete
9:50
instruction
Operations on Arrays
Recap: Array Operations
3 questions
Building a Linked List
While arrays come built into most programming languages, only few provide an implementation for a linked list.
Over the next set of videos let's take a look at another simple data structure called a linked list. We'll look at how a linked list is defined, what advantages it offers over arrays, and in what situations we use them
Chevron 9 steps
What Is a Linked List?
13:18
instruction
Singly and Doubly Linked Lists
Adding Nodes to a Linked List
7:50
Recap: Linked List Basics
5 questions
Implementing Search
4:28
Inserting a Node
6:44
Removing a Node
7:46
instruction
Linked Lists Operations
Recap: Linked List Operations
4 questions
The Merge Sort Algorithm
One of the fundamental problems when working with data is sorting it in a particular order. There are lots of different sorting algorithms each with its own set of advantages and in this stage we're going to look at the merge sort algorithm.
To start, we're going to implement it using an array or a Python list. We'll look at each step in the process and introduce an important problem solving strategy called divide and conquer.
Chevron 9 steps
Merge Sort
8:07
Splitting Into Sublists
3:14
Recursively Merging Sublists
7:07
instruction
Merge Sort Implementations
Recap: Merge Sort
3 questions
Ensuring the Correctness of Merge Sort
6:41
Evaluating the Runtime of Merge Sort
7:22
instruction
Alternate Versions of Merge Sort
Recap: Runtime Analysis of Merge Sort
4 questions
Merge Sort and Linked Lists
To conclude this course let's implement the merge sort algorithm again but this time on our linked list.
We'll look at how the implementation of each step differs based on the underlying data structure as well as how this affects the runtime of the individual operations.
