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
Divide and conquer
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
Array Characteristics and Storage
Accessing a Value in an Array
Recap: Array Basics
Array Search, Insert and Delete
Operations on Arrays
Recap: Array Operations
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?
Singly and Doubly Linked Lists
Adding Nodes to a Linked List
Recap: Linked List Basics
Inserting a Node
Removing a Node
Linked Lists Operations
Recap: Linked List Operations
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
Splitting Into Sublists
Recursively Merging Sublists
Merge Sort Implementations
Recap: Merge Sort
Ensuring the Correctness of Merge Sort
Evaluating the Runtime of Merge Sort
Alternate Versions of Merge Sort
Recap: Runtime Analysis of Merge Sort
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.