this is the nav!
Workspace
Stephon Henry-Rerrie/

# Course Notes: Data Structures and Algorithms in Python

0
Beta

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

```.mfe-app-workspace-qcdhrn{font-size:13px;line-height:1.5384615384615385;font-family:JetBrainsMonoNL,Menlo,Monaco,'Courier New',monospace;}```class Node:

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

def __init__(self, data):
self.tail = None

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

else:
self.tail = new_node

def insert_at_end(self, data):

new_node = Node(data)

self.tail.next= next_node
self.tail = new_node
else:
self.tail = new_node

def search(self, data):

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