Welcome!

D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N

Miriam Antona
Software Engineer
The importance of algorithms and data structures
Data structures and algorithms enable us to
solve everyday problems

using efficient code

The course could be taught in any programming language

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Algorithms and data structures
Algorithm: set of instructions that solve a Data structures: hold and manipulate data
problem when we execute an algorithm
1. Design Advanced data structures: linked lists,
stacks, queues...

2. Code

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists

Sequence of data connected through links

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - structure

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - structure

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - structure

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - structure

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - structure

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - structure

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - structure

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - structure

Data doesn't need to be stored in contiguous blocks of memory

Data can be located in any available memory address

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Singly linked lists

One link: singly linked list

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Doubly linked lists

Two links in either direction: doubly linked list

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - real uses
Implement other data structures:
stacks

queues

graphs

Access information by navigating backward and forward

web browser

music playlist

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - Node class
class Node:
def __init__(self, data):
self.data = data
self.next = None

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - LinkedList class
class LinkedList:
def __init__(self):
self.head = None
self.tail = None

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - methods
insert_at_beginning()

remove_at_beginning()

insert_at_end()

remove_at_end()

insert_at()

remove_at()

search()

...

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - insert_at_beginning

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - insert_at_beginning

def insert_at_beginning(self, data):

new_node = Node(data)
if self.head:

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - insert_at_beginning

def insert_at_beginning(self, data):

new_node = Node(data)
if self.head:
new_node.next = self.head

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - insert_at_beginning

def insert_at_beginning(self, data):

new_node = Node(data)
if self.head:
new_node.next = self.head
self.head = new_node

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - insert_at_beginning

def insert_at_beginning(self, data):

new_node = Node(data)
if self.head:
new_node.next = self.head
self.head = new_node
else:
self.tail = new_node
self.head = new_node

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - insert_at_end
def insert_at_end(self, data):
new_node = Node(data)
if self.head:
self.tail.next = new_node
self.tail = new_node
else:
self.head = new_node
self.tail = new_node

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - search
def search(self, data):
current_node = self.head
while current_node:
if current_node.data == data:
return True

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - search
def search(self, data):
current_node = self.head
while current_node:
if current_node.data == data:
return True
else:
current_node = current_node.next

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - search
def search(self, data):
current_node = self.head
while current_node:
if current_node.data == data:
return True
else:
current_node = current_node.next
return False

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - example

sushi_preparation = LinkedList()
sushi_preparation.insert_at_end("prepare")

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - example

sushi_preparation = LinkedList()
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll")

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - example

sushi_preparation = LinkedList()
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll")
sushi_preparation.insert_at_beginning("assemble")

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Linked lists - example

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

DATA STRUCTURES AND ALGORITHMS IN PYTHON

 Let's practice!
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N
 Understanding Big O
Notation
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N

Miriam Antona
Software Engineer
Big O Notation
Measures the worst-case complexity of an algorithm
Time complexity: time taken to run completely

Space complexity: extra memory space

Doesn't use seconds/bytes

Different results depending on the hardware

Mathematical expressions: O(1), O(n), O(n2 )...

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Big O Notation

DATA STRUCTURES AND ALGORITHMS IN PYTHON

O(1)
colors = ['green', 'yellow', 'blue', 'pink']

def constant(colors):
print(colors[2])

constant(colors)

blue

DATA STRUCTURES AND ALGORITHMS IN PYTHON

O(1)
colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple', 'red']

def constant(colors):
print(colors[2]) # O(1)

constant(colors)

blue

DATA STRUCTURES AND ALGORITHMS IN PYTHON

O(n)
colors = ['green', 'yellow', 'blue', 'pink']

def linear(colors):
for color in colors:
print(color)

linear(colors)

green
yellow
blue
pink

DATA STRUCTURES AND ALGORITHMS IN PYTHON

O(n)
colors = ['green', 'yellow', 'blue', 'pink'] # n=4

def linear(colors):
for color in colors:
print(color) # O(4)

linear(colors)

n=4 : 4 operations

DATA STRUCTURES AND ALGORITHMS IN PYTHON

O(n)
colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple'] # n=7

def linear(colors):
for color in colors:
print(color) # O(7)

linear(colors)

n=4 : 4 operations

n=7 : 7 operations

n=100 : 100 operations

...

O(n) complexity

DATA STRUCTURES AND ALGORITHMS IN PYTHON

 2
O(n )
colors = ['green', 'yellow', 'blue'] green green
green yellow
def quadratic(colors): green blue
for first in colors: yellow green
for second in colors: yellow yellow
print(first, second) yellow blue
blue green
quadratic(colors) blue yellow
blue blue
n=3 : (3 x 3) 9 operations

n=100 : (100 x 100) 10,000 operations

quadratic pattern

O(n2 ) complexity

DATA STRUCTURES AND ALGORITHMS IN PYTHON

 3
O(n )
colors = ['green', 'yellow', 'blue'] n=3 : (3 x 3 x 3) 27 operations

n=10 : (10 x 10 x 10) 1,000 operations

def cubic(colors):
for color1 in colors:
cubic pattern
for color2 in colors: O(n3 ) complexity
for color3 in colors:
print(color1, color2, color3)

cubic(colors)

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Calculating Big O Notation
colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple']
other_colors = ['orange', 'brown']

def complex_algorithm(colors):
color_count = 0

for color in colors:

print(color)
color_count += 1

for other_color in other_colors:

print(other_color)
color_count += 1

print(color_count)

complex_algorithm(colors)

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Calculating Big O Notation
colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple'] # O(1)
other_colors = ['orange', 'brown'] # O(1)

def complex_algorithm(colors):
color_count = 0 # O(1)

for color in colors:

print(color) # O(n)
color_count += 1 # O(n)

for other_color in other_colors:

print(other_color) # O(m)
color_count += 1 # O(m)

print(color_count) # O(1)

complex_algorithm(colors) # O(4

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Calculating Big O Notation
colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple'] # O(1)
other_colors = ['orange', 'brown'] # O(1)

def complex_algorithm(colors):
color_count = 0 # O(1)

for color in colors:

print(color) # O(n)
color_count += 1 # O(n)

for other_color in other_colors:

print(other_color) # O(m)
color_count += 1 # O(m)

print(color_count) # O(1)

complex_algorithm(colors) # O(4 + 2n

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Calculating Big O Notation
colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple'] # O(1)
other_colors = ['orange', 'brown'] # O(1)

def complex_algorithm(colors):
color_count = 0 # O(1)

for color in colors:

print(color) # O(n)
color_count += 1 # O(n)

for other_color in other_colors:

print(other_color) # O(m)
color_count += 1 # O(m)

print(color_count) # O(1)

complex_algorithm(colors) # O(4 + 2n + 2m)

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Simplifying Big O Notation
1. Remove constants
O(4 + 2n + 2m) -> O(n + m)
2. Different variables for different inputs
O(n + m)
3. Remove smaller terms
O(n + n2 )

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Simplifying Big O Notation
1. Remove constants
O(4 + 2n + 2m) -> O(n + m)
2. Different variables for different inputs
O(n + m)
3. Remove smaller terms
O(n + n2 ) -> O(n2 )

DATA STRUCTURES AND ALGORITHMS IN PYTHON

 Let's practice!
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N
 Working with stacks
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N

Miriam Antona
Software Engineer
Stacks
LIFO: Last-In First-Out
Last inserted item will be the first item to
be removed

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks
LIFO: Last-In First-Out
Last inserted item will be always the first
item to be removed

Can only add at the top

Pushing onto the stack

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks
LIFO: Last-In First-Out
Last inserted item will be always the first
item to be removed

Can only add at the top

Pushing onto the stack
Can only take from the top
Popping from the stack

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks
LIFO: Last-In First-Out
Last inserted item will be always the first
item to be removed

Can only add at the top

Pushing onto the stack
Can only remove from the top
Popping from the stack
Can only read the last element
Peeking from the stack

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Undo functionality

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Undo functionality
push each keystroke

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Undo functionality
push each keystroke

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Undo functionality
push each keystroke

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Undo functionality
push each keystroke

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Undo functionality
push each keystroke

pop last inserted keystroke

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Symbol checker: ( [ { } ] )
push opening symbols

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Symbol checker: ( [ { } ] )
push opening symbols

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Symbol checker: ( [ { } ] )
push opening symbols

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Symbol checker: ( [ { } ] )
push opening symbols

check closing symbol

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Symbol checker: ( [ { } ] )
push opening symbols

check closing symbol

pop matching opening symbol

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - real uses
Function calls
push block of memory

pop after the execution ends

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - implementation using singly linked lists
class Node:
def __init__(self,data):
self.data = data
self.next = None

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - implementation using singly linked lists
class Node:
def __init__(self,data):
self.data = data
self.next = None

class Stack:
def __init__(self):
self.top = None

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - implementation using singly linked lists
class Node:
def __init__(self,data):
self.data = data
self.next = None

class Stack:
def __init__(self):
self.top = None

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - push
def push(self, data):

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - push
def push(self, data):
new_node = Node(data)
if self.top:

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - push
def push(self, data):
new_node = Node(data)
if self.top:
new_node.next = self.top

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - push
def push(self, data):
new_node = Node(data)
if self.top:
new_node.next = self.top
self.top = new_node

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - pop
def pop(self):
if self.top is None:
return None
else:

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - pop
def pop(self):
if self.top is None:
return None
else:
popped_node = self.top

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - pop
def pop(self):
if self.top is None:
return None
else:
popped_node = self.top
self.top = self.top.next

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - pop
def pop(self):
if self.top is None:
return None
else:
popped_node = self.top
self.top = self.top.next
popped_node.next = None

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - pop
def pop(self):
if self.top is None:
return None
else:
popped_node = self.top
self.top = self.top.next
popped_node.next = None
return popped_node.data

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Stacks - peek
def peek(self):
if self.top:
return self.top.data
else:
return None

DATA STRUCTURES AND ALGORITHMS IN PYTHON

LifoQueue in Python
LifoQueue: print(my_book_stack.get())
Python's queue module print(my_book_stack.get())
print(my_book_stack.get())
behaves like a stack

import queue 1984

Persepolis
my_book_stack = queue.LifoQueue(maxsize=0) The misunderstanding
my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis") print("Empty stack: ", my_book_stack.empty())
my_book_stack.put("1984")

Empty stack: True

print("The size is: ", my_book_stack.qsize())

The size is: 3

DATA STRUCTURES AND ALGORITHMS IN PYTHON

 Let's practice!
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N