Welcome!

Data Structures and Algorithms in Python

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

Algorithms and data structures

Algorithm: set of instructions that solve a problem
1. Design
2. Code

Data structures: hold and manipulate data when we execute an algorithm
- Advanced data structures: linked lists, stacks, queues...

Linked lists

A visual example of a linked list that contains the steps to prepare bread.

Sequence of data connected through links

Linked lists - structure

The representation of a node in a linked list.

Linked lists - structure

The representation of a node in a linked list with the word "DATA" in the first part.

Linked lists - structure

The representation of a node in a linked list with the words "DATA" in the first part, and "NEXT" with a pointer in the second part.

Linked lists - structure

The representation of two nodes of a linked list connected with a link.

Linked lists - structure

The representation of several nodes of a linked list connected with links.

Linked lists - structure

The representation a linked list where the last node points to null.

Linked lists - structure

The representation of a linked list with the word "HEAD" in the first node.

Linked lists - structure

The representation of a linked list with the word "TAIL" in the last node.

Data doesn't need to be stored in contiguous blocks of memory
Data can be located in any available memory address

Singly linked lists

The representation of a singly linked list.

One link: singly linked list

Doubly linked lists

The representation of a doubly linked list.

Two links in either direction: doubly linked list

Linked lists - real uses

Implement other data structures:
- stacks
- queues
- graphs
Access information by navigating backward and forward
- web browser
- music playlist

Linked lists - Node class

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

Linked lists - LinkedList class

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

Linked lists - methods

insert_at_beginning()
remove_at_beginning()
insert_at_end()
remove_at_end()
insert_at()
remove_at()
search()
...

Linked lists - insert_at_beginning

The representation of a singly linked list.

Linked lists - insert_at_beginning

The representation of a singly linked list and a new node,

 def insert_at_beginning(self, data):
    new_node = Node(data)

    if self.head:

Linked lists - insert_at_beginning

The representation of a singly linked list with the new node connected.

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

Linked lists - insert_at_beginning

The representation of a singly linked list with the new node connected and the word "HEAD" in this node.

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

Linked lists - insert_at_beginning

The representation of new node in an empty linked list.

 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

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

Linked lists - search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

The representation of a singly linked list with the word "current_node" pointing to the first node.

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

The representation of a singly linked list with the word "current_node" pointing to the second node.

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

The representation of a singly linked list with the word "current_node" pointing to the third node.

Linked lists - example

The representation of a new node in an empty linked list.

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Linked lists - example

The representation of a new node added at the end of a linked list.

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

Linked lists - example

The representation of a new node added at the beginning of a linked list.

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

Linked lists - example

The representation of a linked list.

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Let's practice!

Data Structures and Algorithms in Python