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).
- 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()
- 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):