Skip to content
Course Notes: Data Structures and Algorithms in Python
  • AI Chat
  • Code
  • Report

    • Linked List

    A linked list data structure is where you have data in some sort of linear fashion. They have

    class Node: 
    
    def __init__(self, data): 
        self.data = data 
        self.next = None 
        
class LinkedList: 
    
    def __init__(self, data): 
        self.head = None 
        self.tail = None
        
    def insert_at_beginning(self, data): 
        new_node = Node(data=data) 
        
        if self.head: 
            new_node.next = self.head 
            self.head = new_node
        else: 
            self.tail = new_node 
            self.head = new_node
            
    def insert_at_end(self, data): 
        
        new_node = Node(data) 
        
        if self.head: 
            self.tail.next= next_node 
            self.tail = new_node
        else: 
            self.tail = new_node
            self.head = new_node
            
    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

    Big O notation

    Measures the worst-case complexity of an algorithm.

    • Time complexity
    • Space complexity

    We do not use actual units but based on some mathematical expression based on the number of inputs or something like that. I've seen this before but the ones that we tend to have are O(1), O(N), O(log N), O(N^2). We can see this with our linked List. The insertion time for a linked list is 0(1) while search time is O(N).

    Stacks

    • LIFO -> Last-in First Out
    • You can only add at the top
    • You can only remove from the top
    • You can only read the last element that was put on

    The real world example would be a stack of books or something. You can use singly linked lists to implement stacks if you think about it.

    class Stack: 
    
    def __init__(self): 
        self.top = None 
        
    def push(self, data): 
        new_node = Node(data=data)
        if self.top: 
            new_node.next = self.top 
        
        self.top = new_node
            
    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
        
    def peek(self): 
        
        if self.top: 
            return self.top.data
        else: 
            return None

    You can actually use the queue.LifoQueue from python to do this.

    stack = Stack()
stack.push(4)
stack.push(5)
stack.pop()
stack.top.data
    # Import the module to work with Python's LifoQueue
import queue

# Create an infinite LifoQueue
my_book_stack = queue.LifoQueue(maxsize = 0)

# Add an element to the stack
my_book_stack.put("Don Quixote")

# Remove an element from the stack
my_book_stack.get()

    Queue

    • Follows the FIFO principle
    • First In - First Out principle
    • Can only insert at the end but can only remove at the beginning
    • Enqueue -> insert at the end
    • Dequeue -> remove at the beginning

    You can think of these as doing things in the order they are received.

    class Queue: 
    
    def __init__(self): 
        self.head = None 
        self.tail = None
        
    def enqueue(self, data):