Data Structures

Name: Data Structures
Author: StemPy Lab

Lists and dictionaries are not the only ways to organise data. Some jobs fit a pile of things, some a waiting line, some a chain of nodes, some a family tree, and some a map of connections. In this course you use a stack and a queue, build a linked list from nodes, write a binary search tree and walk through it in order, and store a graph as a dictionary of neighbours. You use breadth-first search to find the fewest steps between two places, and depth-first search to find everything that can be reached. A route finder on a small map is the project at the end. The practice runs your code on real cases and tells you which results are wrong.

5 lessons, about 2 h 35 min5 simulations11 problems10 practice questionsPython in every lesson

Created by StemPy Lab

Course outline (5 lessons)

Lesson 1about 35 min
Stacks and queues
A stack is a pile where the last item put on is the first taken off, and a Python list does the job with append to push and pop to take the top, and an empty stack is a list that is False. Stacks fit jobs that need to go back, such as undo, reversing, and checking that brackets are balanced. A queue is a waiting line where the first to arrive is served first, and collections.deque makes one that is fast at both ends, with append to join and popleft to serve. A list is slow as a queue, because pop of 0 moves every other item. Choose the structure by how items come out: last in first out, or first in first out.
1 simulation2 practice questions3 Python programs3 problems1 Python lab1 question set
Read the lesson
Lesson 2about 30 min
Linked lists
A linked list is a chain of nodes. Each node holds a value and a link to the next node, and the last node links to None. The list is held by its head. Adding at the front is fast, because only the head changes, but finding a value or the end means walking from the head, one node at a time, with a loop that continues while the current node is not None. A node can be removed by making the node before it skip over it, and the list can be reversed by turning each link around. Compared with a Python list, a linked list is quick to insert and remove at the front and in the middle once you are there, and slow to reach the item at a position. A Python list is the better choice for most jobs, and a linked list teaches how nodes and links work.
1 simulation2 practice questions2 Python programs3 problems1 Python lab
Read the lesson
Lesson 3about 30 min
Trees: the binary search tree
A tree is made of nodes in which each node can have children. In a binary tree each node has at most two, a left and a right. A binary search tree keeps the values in a rule: everything on the left of a node is smaller and everything on the right is bigger. To insert or to search, compare with the node and go left or right, so a search in a balanced tree of a million values needs about 20 steps, like binary search. A walk through the left side, then the node, then the right side, called an in-order walk, gives the values sorted. The height is the number of levels. If values are inserted in sorted order, the tree becomes a chain with height n and loses its speed.
1 simulation2 practice questions2 Python programs2 problems1 Python lab
Read the lesson
Lesson 4about 35 min
Graphs: connections and searching
A graph is a set of points, called nodes, and the lines between them, called edges, and it can describe a map of towns and roads, a network of friends, or the links of a website. In Python a graph is a dictionary that maps each node to the list of its neighbours. Breadth-first search uses a queue, visits the places in rings, nearest first, and so finds the path with the fewest steps. A dictionary of the place from which each place was reached marks what has been seen and lets the path be rebuilt backwards. Depth-first search goes as far as it can and then comes back, and finds everything that can be reached from a start and the separate groups of a graph. A node that is not seen again must be recorded, or a loop in the graph would make the search go round for ever.
1 simulation2 practice questions3 Python programs3 problems1 Python lab
Read the lesson
Lesson 5about 25 min
Project: finding the way
In this project we build a route finder on a small map of towns. The roads are a dictionary of neighbours, and breadth-first search with a queue finds the shortest route as a list of towns, or None when there is no way. From it we get the number of stops, and a second search gives every town that can be reached. An unknown town is refused with a ValueError. We plan the expected routes by hand, build the functions, test the same town, a town that cannot be reached and an unknown town, and extend the finder with road lengths and a path that avoids a closed town.
1 simulation2 practice questions1 Python program1 Python lab
Read the lesson

Test Your Learning

Data Structures: Predict the Output

10 questions · 15 min

Not started

Your teacher

StemPy Lab

← All Courses

← PreviousTesting and Debugging →

More onPython Going Further › Data Structures

Discussion (0)

Loading…

Data Structures

Course outline (5 lessons)

Stacks and queues

Linked lists

Trees: the binary search tree

Graphs: connections and searching

Project: finding the way

Test Your Learning

Your teacher

Discussion (0)