Skip to content

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