06-data-structures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stack\n",
    "\n",
    "#### **Define Stack**\n",
    "\n",
    "The $\\text{Stack.init(int capacity, type)}$ operation reserves in the computer's memory the number of bits defined by $\\text{capacity}$ and $\\text{type}$. Additionally, it creates two pointers: $\\text{bottom} = 0$ and $\\text{top} = 0$. The $\\text{bottom}$ pointer does not change and points to the bottom of the stack, whereas $\\text{top}$ moves to the right when an element is added to the stack and to the left when an element is removed.\n",
    "\n",
    "![Stack](images/stack-init.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(n)$  \n",
    "Space complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "#### **Get Access to the Top of the Stack**  \n",
    "\n",
    "The $\\text{Stack.top}$ operation returns the element at the top of the stack. Importantly, the other elements beneath the top element are not accessible to the system, which characterizes the stack structure.  \n",
    "\n",
    "![Stack](images/stack-top.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(1)$  \n",
    "Space complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Check the Size of the Stack**  \n",
    "\n",
    "The $\\text{Stack.size}$ operation returns the stack's size, which is $\\text{top} - \\text{bottom}$.  \n",
    "\n",
    "![Stack](images/stack-size.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(1)$  \n",
    "Space complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Check the Capacity of the Stack**  \n",
    "\n",
    "The $\\text{Stack.capacity}$ operation returns the possible maximum size of the stack. For clarification, $\\text{capacity}$ determines the amount of memory reserved for this stack, which is the $\\text{capacity}$ value specified when defining the stack with $\\text{Stack.init(int capacity, type)}$.  \n",
    "\n",
    "![Stack](images/stack-capacity.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(1)$  \n",
    "Space complexity: $\\mathcal{O}(1)$ \n",
    "\n",
    "#### **Check whether the Stack Is Empty**\n",
    "\n",
    "The $\\text{Stack.isEmpty}$ operations returns $\\text{True}$ when $\\text{bottom} = \\text{top}$. Otherwise returns $\\text{False}$\n",
    "\n",
    "![Stack](images/stack-isempty.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(1)$  \n",
    "Space complexity: $\\mathcal{O}(1)$ \n",
    "\n",
    "#### **Check whether the Stack Is Full**\n",
    "\n",
    "The $\\text{Stack.isFull}$ operations returns $\\text{True}$ when $\\text{top} = \\text{capacity}$. Otherwise returns $\\text{False}$\n",
    "\n",
    "![Stack](images/stack-isfull.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(1)$  \n",
    "Space complexity: $\\mathcal{O}(1)$ \n",
    "\n",
    "#### **Add Element to the Stack**  \n",
    "\n",
    "The $\\text{Stack.add(object)}$ operation adds $\\text{object}$ to the top of the stack. As a result, it becomes the value returned by $\\text{Stack.top}$, and access to lower objects is blocked. However, if the stack is full, the operation is not performed. \n",
    "\n",
    "![Stack](images/stack-add.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(1)$  \n",
    "Space complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Add Many Elements to the Stack**  \n",
    "\n",
    "The $\\text{Stack.addMany}(\\text{object}_1, \\text{object}_2, ..., \\text{object}_n)$, $\\text{Stack.addMany}(\\big<\\text{object}_1, \\text{object}_2, ..., \\text{object}_n\\big>)$ operation adds the provided objects to the top of the stack in left-to-right order. The last object, $\\text{objectn}$, becomes the value returned by $\\text{Stack.top}$, and access to lower objects is blocked. However, if adding all elements would overflow the stack, the operation is not performed, and no elements are added.  \n",
    "\n",
    "![Stack](images/stack-addmany.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(n)$  \n",
    "Space complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Remove Element from the Stack**  \n",
    "\n",
    "The $\\text{Stack.remove}$ operation removes the top element from the stack, making the element below it the new value returned by $\\text{Stack.top}$. If the stack is empty, the operation does nothing or possibly returns an empty stack notification.  \n",
    "\n",
    "![Stack](images/stack-remove.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(1)$  \n",
    "Space complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Remove $n$ Elements from the Stack**  \n",
    "\n",
    "The $\\text{Stack.removeMany(int i)}$ operation removes $\\text{i}$ objects from the top of the stack, making the $\\text{i} + 1$ element the new $\\text{Stack.top}$, and access to lower objects is blocked. If $\\text{i}$ is greater than $\\text{size}$, the operation does nothing.  \n",
    "\n",
    "![Stack](images/stack-removemany.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(n)$  \n",
    "Space complexity: $\\mathcal{O}(1)$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Queue\n",
    "\n",
    "#### **Define Queue**  \n",
    "\n",
    "The $\\text{Queue.init(int capacity, type)}$ operation reserves memory for the queue with a defined $\\text{size}$ and $\\text{type}$. It also creates two pointers: $\\text{front} = 0$ and $\\text{rear} = 0$. The $\\text{front}$ pointer represents the beginning of the queue, while $\\text{rear}$ moves to the right when an element is enqueued. If the queue is full, no more elements can be added.  \n",
    "\n",
    "![Queue](images/queue-init.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "#### **Get Access to the Head of the Queue**  \n",
    "\n",
    "The $\\text{Queue.front}$ operation returns the first element in the queue without removing it. Other elements behind it remain inaccessible until dequeued.  \n",
    "\n",
    "![Queue](images/queue-front.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Check the Size of the Queue**  \n",
    "\n",
    "The $\\text{Queue.size}$ operation returns the number of elements currently stored in the queue, computed as $(\\text{rear} - \\text{front}) \\mod{\\text{capacity}}$.  \n",
    "\n",
    "![Queue](images/queue-size.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Check the Capacity of the Queue**  \n",
    "\n",
    "The $\\text{Queue.capacity}$ operation returns the total memory allocated for the queue, which corresponds to the $\\text{capacity}$ specified when initializing it with $\\text{Queue.init(int capacity, type)}$.  \n",
    "\n",
    "![Queue](images/queue-capacity.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Check whether the Queue Is Empty**\n",
    "\n",
    "The $\\text{Queue.isEmpty}$ operations returns $\\text{True}$ when $\\text{front} = \\text{rear}$ and $\\text{Queue.front}$ does not exist. Otherwise returns $\\text{False}$\n",
    "\n",
    "![Queue](images/queue-isempty.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(1)$  \n",
    "Space complexity: $\\mathcal{O}(1)$ \n",
    "\n",
    "#### **Check whether the Queue Is Full**\n",
    "\n",
    "The $\\text{Queue.isFull}$ operations returns $\\text{True}$ when $\\text{front} = \\text{rear}$ and $\\text{Queue.front}$ exists. Otherwise returns $\\text{False}$ \n",
    "\n",
    "![Queue](images/queue-isfull.png)\n",
    "\n",
    "Time complexity: $\\mathcal{O}(1)$  \n",
    "Space complexity: $\\mathcal{O}(1)$ \n",
    "\n",
    "#### **Enqueues Element to the Queue**  \n",
    "\n",
    "The $\\text{Queue.enqueue(object)}$ operation adds $\\text{object}$ to the end of the queue, updating $\\text{rear}$. If the queue is full, the operation is not performed.  \n",
    "\n",
    "![Queue](images/queue-enqueuemany.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Enqueues Many Elements to the Queue**  \n",
    "\n",
    "The $\\text{Queue.enqueueMany}(\\text{object}_1, \\text{object}_2, ..., \\text{object}_n)$, $\\text{Queue.enqueueMany}(\\big<\\text{object}_1, \\text{object}_2, ..., \\text{object}_n\\big>)$ operation enqueues multiple objects in left-to-right order. If adding all elements would exceed the queue's capacity, none are added.  \n",
    "\n",
    "![Queue](images/queue-enqueuemany.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Dequeues Element from the Queue**  \n",
    "\n",
    "The $\\text{Queue.dequeue}$ operation removes the front element from the queue, moving $\\text{front}$ forward. If the queue is empty, the operation does nothing or returns an empty queue notification.  \n",
    "\n",
    "![Queue](images/queue-dequeue.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Dequeues $i$ Elements from the Queue**  \n",
    "\n",
    "The $\\text{Queue.dequeueMany(int i)}$ operation removes $\\text{i}$ elements from the front of the queue. If $\\text{i}$ is greater than the current queue size, the operation does nothing.  \n",
    "\n",
    "![Queue](images/queue-dequeuemany.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Array\n",
    "\n",
    "#### **Define Array**  \n",
    "\n",
    "The $\\text{Array.init(int capacity, type)}$ operation reserves memory for an array with a defined $\\text{capacity}$ and $\\text{type}$. The array is initialized with a fixed size, meaning its length cannot dynamically expand beyond the allocated capacity.\n",
    "\n",
    "![Array](images/array-init.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "#### **Check the Size of the Array**  \n",
    "\n",
    "The $\\text{Array.size}$ operation returns $\\text{capacity}$.\n",
    "\n",
    "![Array](images/array-size.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "#### **Get Access to the $i^{\\text{th}}$ Element of the Array**  \n",
    "\n",
    "The $\\text{Array}[i]$ operation retrieves the element at index $\\text{i}$. Since arrays provide direct access to their elements via indexing, retrieving an element is performed in constant time.  \n",
    "\n",
    "![Array](images/array-access.png)\n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dynamic Array\n",
    "\n",
    "**Define Dynamic Array**  \n",
    "\n",
    "The $\\text{DynamicArray.init(int capacity, type)}$ operation reserves memory for a dynamic array with an initial $\\text{capacity}$ and $\\text{type}$. Unlike a static array, a dynamic array can grow or shrink in size when elements are added or removed.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Check the Size of the Dynamic Array**  \n",
    "\n",
    "The $\\text{DynamicArray.size}$ operation returns the number of elements currently stored in the dynamic array.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Check the Capacity of the Dynamic Array**  \n",
    "\n",
    "The $\\text{DynamicArray.capacity}$ operation returns the total memory allocated for the array, which determines how many elements can be stored before resizing is necessary.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Get Access to the $i^{\\text{th}}$ Element of the Dynamic Array**  \n",
    "\n",
    "The $\\text{DynamicArray}[i]$ operation retrieves the element at index $\\text{i}$. Since arrays provide direct access via indexing, this operation is performed in constant time.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Grow Capacity of the Dynamic Array**  \n",
    "\n",
    "The $\\text{DynamicArray.grow}$ operation expands the allocated memory for the array when more space is neededby increasing $\\text{capacity}$ using formula $\\text{capacity} \\gets 2 \\times \\text{capacity}$.  \n",
    "\n",
    "- **Case 1:** There is enough space to shift the pointer, so no memory reallocation is needed.  \n",
    "  - Time Complexity: $\\mathcal{O}(1)$  \n",
    "  - Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "- **Case 2:** There is not enough space to shift the pointer, requiring allocation of a new, larger memory block (typically doubling the capacity) and copying existing elements.  \n",
    "  - Time Complexity: $\\mathcal{O}(n)$  \n",
    "  - Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Shrink Capacity of the Dynamic Array**  \n",
    "\n",
    "The $\\text{DynamicArray.shrink}$ operation reduces the allocated memory when the number of elements stored is significantly smaller than the capacity. This optimizes memory usage but may require copying elements to a smaller memory block.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Add Element to the End of the Dynamic Array**  \n",
    "\n",
    "The $\\text{DynamicArray.add(object)}$ operation appends $\\text{object}$ to the end of the array by increasing $\\text{capacity}$ using formula $\\text{capacity} \\gets 2 \\times \\text{capacity}$.  \n",
    "\n",
    "- **Case 1:** There is enough space, so the object is added without resizing.  \n",
    "  - Time Complexity: $\\mathcal{O}(1)$  \n",
    "  - Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "- **Case 2:** There is not enough space, requiring the array to grow in capacity before adding the element.  \n",
    "    - **Case 1:** There is enough space to shift the pointer, so no memory reallocation is needed.  \n",
    "        - Time Complexity: $\\mathcal{O}(1)$  \n",
    "        - Space Complexity: $\\mathcal{O}(1)$  \n",
    "    - **Case 2:** There is not enough space to shift the pointer, requiring allocation of a new, larger memory block (typically doubling the capacity) and copying existing elements.  \n",
    "        - Time Complexity: $\\mathcal{O}(n)$  \n",
    "        - Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Insert Element at $i^{\\text{th}}$ Position to the Dynamic Array**  \n",
    "\n",
    "The $\\text{DynamicArray.addAt(object, i)}$ operation inserts $\\text{object}$ at index $\\text{i}$, shifting subsequent elements to the right.  \n",
    "\n",
    "- **Case 1:** There is enough space, so elements are shifted, and the object is inserted.  \n",
    "  - Time Complexity: $\\mathcal{O}(n)$  \n",
    "  - Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "- **Case 2:** There is not enough space, requiring the array to grow in capacity before shifting elements and inserting the object.  \n",
    "    - **Case 1:** There is enough space to shift the pointer, so no memory reallocation is needed.  \n",
    "        - Time Complexity: $\\mathcal{O}(n)$  \n",
    "        - Space Complexity: $\\mathcal{O}(1)$  \n",
    "    - **Case 2:** There is not enough space to shift the pointer, requiring allocation of a new, larger memory block (typically doubling the capacity) and copying existing elements.  \n",
    "        - Time Complexity: $\\mathcal{O}(n)$  \n",
    "        - Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Delete the Last Element From the Dynamic Array**  \n",
    "\n",
    "The $\\text{DynamicArray.remove}$ operation removes the last element from the array. If the array is significantly underutilized, shrinking may be triggered.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Delete Element at $i^{\\text{th}}$ Position From the Dynamic Array**  \n",
    "\n",
    "The $\\text{DynamicArray.removeAt(i)}$ operation removes the element at index $\\text{i}$, shifting subsequent elements to the left. If the array is significantly underutilized, shrinking may be triggered.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linked List\n",
    "\n",
    "**Define Linked List**  \n",
    "\n",
    "The $\\text{LinkedList.init()}$ operation initializes an empty linked list. A linked list is a data structure composed of nodes, where each node contains data and a reference (or link) to the next node in the sequence.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$ (initialization)  \n",
    "Space Complexity: $\\mathcal{O}(1)$ (for the list object itself)  \n",
    "\n",
    "**Check the Size of the Linked List**  \n",
    "\n",
    "The $\\text{LinkedList.size}$ operation counts the number of nodes in the linked list by traversing it from the head to the tail.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Get Access to the Head of the Linked List**  \n",
    "\n",
    "The $\\text{LinkedList.head}$ operation returns the first node of the linked list. Since the head is always accessible directly, this operation has constant time complexity.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Get Access to the Tail of the Linked List**  \n",
    "\n",
    "The $\\text{LinkedList.tail}$ operation returns the last node of the linked list. If the tail is stored directly, this operation is done in constant time. Otherwise, it may require traversal from the head to the tail.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$ (if tail is maintained as a reference) or $\\mathcal{O}(n)$ (if not)  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Get Access to the $i^{\\text{th}}$ Element of the Linked List**  \n",
    "\n",
    "The $\\text{LinkedList.get}(i)$ operation retrieves the element at index $i$ by traversing the list from the head to the $i^{\\text{th}}$ node.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Add Element to the Beginning of the Linked List**  \n",
    "\n",
    "The $\\text{LinkedList.add(object)}$ operation inserts a new node containing $\\text{object}$ at the head of the list. This operation involves creating a new node and adjusting pointers.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Add Element at $i^{\\text{th}}$ Position to the Linked List**  \n",
    "\n",
    "The $\\text{LinkedList.addAt(object, i)}$ operation inserts a new node containing $\\text{object}$ at index $i$, shifting subsequent elements. The list is traversed from the head until the $i^{\\text{th}}$ position is reached.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Delete the First Element From the Linked List**  \n",
    "\n",
    "The $\\text{LinkedList.remove}$ operation removes the first node of the list and updates the head pointer to the next node.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Delete Element at $i^{\\text{th}}$ Position From the Linked List**  \n",
    "\n",
    "The $\\text{LinkedList.removeAt(i)}$ operation removes the node at index $i$, shifting subsequent nodes to maintain the list's structure. This operation requires traversing the list to the $i^{\\text{th}}$ node.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Reference List\n",
    "\n",
    "**Define Reference List**  \n",
    "\n",
    "The $\\text{ReferenceList.init(int capacity)}$ operation reserves memory for a reference list with an initial $\\text{capacity}$. Unlike a dynamic array, a reference list consists of references (or pointers) to objects rather than storing the objects themselves. This allows efficient storage of large or complex objects of any type and mixed types.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Check the Size of the Reference List**  \n",
    "\n",
    "The $\\text{ReferenceList.size}$ operation returns the number of references currently stored in the list.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Check the Capacity of the Reference List**  \n",
    "\n",
    "The $\\text{ReferenceList.capacity}$ operation returns the total memory allocated for the reference list, determining how many references can be stored before resizing is necessary.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Get Access to the $i^{\\text{th}}$ Element of the Reference List**  \n",
    "\n",
    "The $\\text{ReferenceList}[i]$ operation retrieves the reference stored at index $\\text{i}$. Since references are accessed via indexing, this operation is performed in constant time.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Grow Size of the Reference List**  \n",
    "\n",
    "The $\\text{ReferenceList.grow}$ operation increases the allocated memory for the list when more space is needed by doubling $\\text{capacity}$.  \n",
    "\n",
    "- **Case 1:** There is enough space to shift the pointer, so no memory reallocation is needed.  \n",
    "  - Time Complexity: $\\mathcal{O}(n)$  \n",
    "  - Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "- **Case 2:** There is not enough space to shift the pointer, requiring allocation of a new, larger memory block and copying existing references.  \n",
    "  - Time Complexity: $\\mathcal{O}(n)$  \n",
    "  - Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Shrink Size of the Reference List**  \n",
    "\n",
    "The $\\text{ReferenceList.shrink}$ operation reduces allocated memory when the number of stored references is significantly smaller than the capacity. This optimizes memory usage but may require copying references to a smaller memory block.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Add Element to the End of the Reference List**  \n",
    "\n",
    "The $\\text{ReferenceList.add(reference)}$ operation appends $\\text{reference}$ to the end of the list.  \n",
    "\n",
    "- **Case 1:** There is enough space, so the reference is added without resizing.  \n",
    "  - Time Complexity: $\\mathcal{O}(1)$  \n",
    "  - Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "- **Case 2:** There is not enough space, requiring the list to grow in capacity before adding the reference.  \n",
    "    - **Case 1:** There is enough space to shift the pointer, so no memory reallocation is needed.  \n",
    "        - Time Complexity: $\\mathcal{O}(1)$  \n",
    "        - Space Complexity: $\\mathcal{O}(1)$  \n",
    "    - **Case 2:** There is not enough space to shift the pointer, requiring allocation of a new, larger memory block and copying existing references.  \n",
    "        - Time Complexity: $\\mathcal{O}(n)$  \n",
    "        - Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Add Element at $i^{\\text{th}}$ Position to the Reference List**  \n",
    "\n",
    "The $\\text{ReferenceList.addAt(reference, i)}$ operation inserts $\\text{reference}$ at index $\\text{i}$, shifting subsequent references to the right.  \n",
    "\n",
    "- **Case 1:** There is enough space, so references are shifted, and the new reference is inserted.  \n",
    "  - Time Complexity: $\\mathcal{O}(n)$  \n",
    "  - Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "- **Case 2:** There is not enough space, requiring the list to grow in capacity before shifting references and inserting the new reference.  \n",
    "    - **Case 1:** There is enough space to shift the pointer, so no memory reallocation is needed.  \n",
    "        - Time Complexity: $\\mathcal{O}(n)$  \n",
    "        - Space Complexity: $\\mathcal{O}(1)$  \n",
    "    - **Case 2:** There is not enough space to shift the pointer, requiring allocation of a new, larger memory block and copying existing references.  \n",
    "        - Time Complexity: $\\mathcal{O}(n)$  \n",
    "        - Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Delete the Last Element From the Reference List**  \n",
    "\n",
    "The $\\text{ReferenceList.remove}$ operation removes the last reference from the list. If the list is significantly underutilized, shrinking may be triggered.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Delete Element at $i^{\\text{th}}$ Position From the Reference List**  \n",
    "\n",
    "The $\\text{ReferenceList.removeAt(i)}$ operation removes the reference at index $\\text{i}$, shifting subsequent references to the left. If the list is significantly underutilized, shrinking may be triggered.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Map\n",
    "\n",
    "**Define Map**  \n",
    "\n",
    "The $\\text{Map}$ data structure (also known as a dictionary or associative array) stores key-value pairs, allowing efficient lookup, insertion, and deletion based on keys. Each key in the map is unique and maps to a specific value. If a hash collision occurs (i.e., two different keys hash to the same index), the map automatically resizes and reallocates all elements to a larger table instead of using linked lists or open addressing.  \n",
    "\n",
    "Time Complexity:  \n",
    "- Average Case: $\\mathcal{O}(1)$  \n",
    "- Worst Case (when resizing occurs): $\\mathcal{O}(n)$  \n",
    "\n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Check the Size of the Map**  \n",
    "\n",
    "The $\\text{Map.size}$ operation returns the number of key-value pairs currently stored in the map.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Get Access to Any Element of the Map**  \n",
    "\n",
    "The $\\text{Map.get(key)}$ operation retrieves the value associated with a given $\\text{key}$. If the key does not exist, it may return a default value or raise an error.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$ (unless resizing occurs)  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "**Return All Keys of the Map**  \n",
    "\n",
    "The $\\text{Map.keys}$ operation returns a list of all keys stored in the map.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Return All Values of the Map**  \n",
    "\n",
    "The $\\text{Map.values}$ operation returns a list of all values stored in the map.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Return All Pairs (Key: Value) of the Map**  \n",
    "\n",
    "The $\\text{Map.items}$ operation returns a list of all key-value pairs stored in the map.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Grow Size of the Map**  \n",
    "\n",
    "The $\\text{Map.grow}$ operation increases the underlying capacity of the map when a hash collision occurs or when the load factor exceeds a certain threshold. Instead of resolving collisions with chaining or probing, all elements are reallocated into a newly sized map, typically doubling the capacity.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Shrink Size of the Map**  \n",
    "\n",
    "The $\\text{Map.shrink}$ operation reduces the allocated memory of the map when the number of stored elements significantly decreases, optimizing space usage. This process involves rehashing all elements into a smaller table.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(n)$  \n",
    "Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Add Element to the Map**  \n",
    "\n",
    "The $\\text{Map.add(key, value)}$ operation inserts a new key-value pair into the map. If the key already exists, its associated value is updated. If inserting the element results in a hash collision, the map grows and rehashes all elements.  \n",
    "\n",
    "- **Case 1:** No collision occurs, and the element is added directly.  \n",
    "  - Time Complexity: $\\mathcal{O}(1)$  \n",
    "  - Space Complexity: $\\mathcal{O}(1)$  \n",
    "\n",
    "- **Case 2:** A collision occurs, triggering a resize and reallocation.  \n",
    "  - Time Complexity: $\\mathcal{O}(n)$  \n",
    "  - Space Complexity: $\\mathcal{O}(n)$  \n",
    "\n",
    "**Delete Element From the Map**  \n",
    "\n",
    "The $\\text{Map.remove(key)}$ operation removes the key-value pair associated with $\\text{key}$ from the map. If deletion causes the number of stored elements to drop below a threshold, the map may shrink.  \n",
    "\n",
    "Time Complexity: $\\mathcal{O}(1)$ (unless resizing occurs)  \n",
    "Space Complexity: $\\mathcal{O}(1)$  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Directed Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Structures in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tuple"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Range"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# for element in some_sequence:\n",
    "#     print(element)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Built in Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sequences (Lists, Tuples, Ranges, Strings)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dictionaries"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}