Introduction to Data Structures Course (How To)

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

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.

Chevron 7 steps

• The Merge Function

  4:51

• The Divide Step

  7:25

• The Conquer Step

  12:14

• Evaluating the Runtime

  8:35

• instruction

  Implementing Merge Sort on Linked Lists

• Recap

  2:13

• Recap: Merge Sort and Linked Lists

  1 question