Data Structures

As we continue our study of data structures and algorithms, let's first think back to some of the concepts we learned in the previous course.

Before continuing our study of data structures and algorithms, let's first think back to what we have previously learned. In the previous data structures course, we learned about a few different linear data structures, including arrays, linked lists, stacks, and queues.

We think of arrays and linked lists as building block data structures; we often use them to implement other data structures with some kind of abstraction, such as stacks and queues.

How we choose to implement data structures, including deciding between using an array or a linked list, depends on what properties we are looking for and what efficiency is required. Check out the video below to remind yourself about these data structures:

To summarize:

  • Big-O notation provides us with a language to analyze the efficiency of algorithms, both in terms of time and space. Big-O classes include O(1) (constant), O(logn), O(n), O(n2), and O(cn) (in order from fastest to slowest).
  • An array is a fixed-size collection of items that provides random access to its elements.
  • A linked list is an extensible collection of items that does not provide random access to its elements.
  • A queue is a data structure with a first-in, first-out (FIFO) abstraction.
  • A stack is a data structure with a last-in, first-out (LIFO) abstraction.

Data structures in Python

As we learn about these data structures, we implement them in Python or use existing Python constructs.

Array

Python doesn't have a built-in array data type. However, it does have a list data type, which we use to simulate an array. Under the hood, Python lists are actually implemented as arrays, so we have to be careful and recognize that occasionally operations on a Python list might be expensive (for example, inserting an item in the middle of a list).

Linked list

When we need to use a linked list, we create a special Node class that contains at least a piece of data and a reference to the next node in the list. We then create instances of the Node list and connect them to form a linked list.

For example, here's a portion of the LLString class that used in a previous semester, which includes Node as a nested, inner class and also has a prepend() method to add a node to the head of the list.

class LLString:
    class Node:
        def __init__(self, val, next):
            self.val = val
            self.next = next

    def __init__(self):
        self.head = None

    def prepend(self, new_val):
        new_node = LLString.Node(new_val, self.head)
        self.head = new_node

Queue

Python provides a deque object from its collections library that we can use as a queue data structure. A deque (pronounced "deck", stands for double-ended queue) provides with O(1) enqueue and dequeue operations by using the append() and popleft() methods, respectively:

Stack

The easiest way to simulate a stack in Python is to use a list. To push items onto the stack, we can use the append() method, and the pop items from the top of the stack we can use the (you guessed it) pop() method. Both of these are O(1) algorithms.