Note 8: Basic Data Structures

Now that you are comfortable creating Python objects, we will implement basic data structures using Python.

Python Built-In Functionality

Python lists already implement much of what we are going to do in this note. Python’s deque (double-ended queue) from collections implements other things we are going to do in this note.

Nonetheless, implementing these data structures ourselves is how we learn how they work. For the time being, we won’t use deque, and we’ll not use any Python list methods,only indexing, slicing, and concatenation.

Why? While this course is taught in Python, we don’t want to lose sight of some ‘lower level’ programming fundamentals that Python lets us ignore. 😎

Stack

A stack is an ordered collection of elements in which elements are always added to the top of the stack, and elements are always removed from the top of the stack. This is similar to a stack of blocks: you can add to the top, and you can take off from the top. You cannot add to the bottom or middle, and you cannot remove from the bottom or the middle.

For this reason, stacks are referred to as “last in, first out” (LIFO).

  • Conventionally, adding something to a stack is referred to as “pushing” to the stack.
  • Similarly, removing something from a stack is known as “popping” from the stack.

Python’s built-in list functionality makes implementing stacks trivial. We will start by creating a Stack class.

class Stack:
    def __init__(self) -> None:
        self.contents:list = []

The list.append method is effectively a push, so there’s not much work left to do:

class Stack:
    def __init__(self) -> None:
        self.contents:list = []

    def push(self, x) -> None:
        self.contents = self.contents + [x]

    def pop(self):
        to_return = self.contents[-1]
        self.contents = self.contents[:-1]
        return to_return

Extend the Stack class with a new __repr__ in the practice problems.

Queue

A stack is an ordered collection of elements in which elements are always added to the back of the queue, and always removed from the front of the queue:

For this reason, queues are referred to as “first in, first out” (FIFO).

  • Conventionally, adding something to a queue is referred to as “enqueuing.”
  • Similarly, removing something from a queue is known as “dequeuing.”

Implementation is straightforward, and similar to the Stack class:

class Queue:
    def __init__(self) -> None:
        self.contents:list = []

    def enqueue(self, x) -> None:
        self.contents = self.contents + [x]

    def dequeue(self):
        to_return = self.contents[0]
        self.contents = self.contents[1:]
        return to_return

Priority Queue

A priority queue is, like a stack and a queue, an ordered collection, but it differs from both stack and queue in that the removal order of the priority queue is not a function of the order in which elements are added to the queue.

To review:

  • Stacks remove (pop) the most recent element added (last in, first out)
  • Queues remove (dequeue) elements in order of addition (first in, first out)

Elements in a priority queue have a value and a priority.

  • Elements are added to the queue in order of the priority.
    • This is commonly called “insertion,” because rather than being added at the top (stack) or the end (queue), the new element is inserted according to priority order
  • Elements are removed from the queue, highest priority first

  • The new element (priority 4) is added after the priority-3 element and before the priority-5 element
  • The highest-priority element (priority 4) is removed
  • This diagram shows a “lowest first” priority
    • Priority queues can also be implemented with “highest-first” priority

Implementation of a simple list-based priority queue in Python (without list methods) is somewhat more involved. (Note that there are substantially more efficient ways to implement a priority queue, and we will learn about these later on.)

class PriorityQueue:
    def __init__(self) -> None:
        self.contents:list = []

    def insert(self, val, pri) -> None:
        x = (val, pri)
        
        # find the correct insertion position
        insert_position = len(self.contents)
        for i in range(len(self.contents)):
            if self.contents[i][1] > x[1]:
                insert_position = i
                break
       
        # insert in the correct position
        self.contents = self.contents + [None]
        for i in range(len(self.contents)-1, insert_position ,-1):
            self.contents[i] = self.contents[i - 1]
        self.contents[insert_position] = x

    def extract(self):
        to_return = self.contents[0]
        self.contents = self.contents[1:]
        return to_return[0]
  • This implementation uses an ordered list of (value, priority) tuples
  • We will see other implementations in the future
  • This implementation finds the correct insertion position for each insertion, then:
    • Adds an “empty” element
    • Shifts every existing element by one towards the end of the queue
    • Inserts the new element in the correct position

Extend this class to have basic Stack and Queue functionality in the practice problems.

Linked List

The linked list has fundamental differences from the previous data structures we have implemented.

  • A linked list consists of nodes
  • Each node contains a value, and a reference to the next node
  • The last node’s reference is to None
  • A “head” reference indicates which node is first

Inserting an element into a linked list is somewhat easier than inserting an element into an array-like ordered collection, such as a Python list.

  • The correct insertion “position” is found:
    • Which node comes before the new node
    • Which node comes after the new node
  • The new node is created, with its reference the “after” node
  • The reference from the “before” node is updated to point to the new node

Note how only the parts of the linked list highlighted in red were changed.

To implement the linked list, we’ll start with a Node class:

class Node:
    def __init__(self, value) -> None:
        self.value = value
        self.next = None

    def update(self, new_next) -> None:
        self.next = new_next

This class is created with a value, and no reference to a “next” node, and has an update method to change the next node.

We could, in a way, create a linked list with just Node objects:

  • We assign the first node to list_head (Line 9)
  • We create another node and initially assign to b (Line 10)
    • We then update the first node to point to this new node (Line 11)
  • We can create a new node directly, without assignment (line 12)
  • Removing the ‘explicit’ reference to the second node does not remove it (Line 13)
  • Removing all links to a node does remove it (Line 14)

In practice, it is more useful to create a class for the linked list (that uses the Node class).

class Node:
    def __init__(self, value) -> None:
        self.value = value
        self.next = None

    def update(self, new_next) -> None:
        self.next = new_next

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

    def append(self, value) -> None:
        if self.head == None:
            self.head = Node(value)
            return
        current = self.head
        while current.next != None:
            current = current.next
        current.next = Node(value)

This linked list has an append method, that adds a new node at the end of the list.

We will add more functionality to our linked list in the practice problems.

Practice

Practice Problem 8.1

Practice Problem 8.1

Change the __repr__ method of the basic Stack class to allow inspection of the stack. The result should print as follows:

K = Stack()
K.push(4)
K.push(3)
print(K)
Stack: 3, 4

Practice Problem 8.2

Practice Problem 8.2
  • Add a push method to the PriorityQueue class that takes one argument, and then adds a new element to the priority queue:
    • The value of the element added will be the argument to push
    • The priority of the element added will be such that it is added to the front of the queue
  • Add an enqueue method to the PriorityQueue class that takes one argument, and then adds a new element to the priority queue:
    • The value of the element added will be the argument to enqueue
    • The priority of the element added will be such that it is added to the back of the queue

Practice Problem 8.3

Practice Problem 8.3
  • Add a tail reference to the LinkedList class
    • Just as self.head points to the first node in the linked list, self.tail should point to the last node
  • Add a prepend method to the LinkedList class
    • prepend should add a node to the list at the head position (and this new node’s next should reference the prior head)

Practice Problem 8.4

Practice Problem 8.4
  • Add a remove_first method to the LinkedList class:
    • The method should return the value of the first node in the list
    • The method should remove the first node from the list
    • The second node in the list will be the new first node
  • Add a remove_last method to the LinkedList class:
    • The method should return the value of the last node in the list
    • The method should remove the last node from the list

Practice Problem 8.5

Practice Problem 8.5
  • Add an insert_before method to the LinkedList class:
    • The method should take two arguments, a “node” value, and a “before” value
    • The method should traverse the linked list, starting at the head node
    • As soon as a node with the “before” value is found, insert a new node before this node
      • The new node’s value should be the “node” value (argument)

–>