3.Data_Structure_explnation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e2a989a4-6679-4c0d-abba-857a6b33365e",
   "metadata": {},
   "source": [
    "Data structure :\n",
    "1. definition \n",
    "2. why we study it\n",
    "3. how to think in data structure\n",
    "\n",
    "                                               let's start\n",
    "\n",
    "    definition :(simply it's a paradigm for storing data with different techniques  where we make operations on these data, we are looking for the best way to get a more efficient algorithm .)\n",
    "1. A data structure is a way of organizing and storing data in a computer so that it can be manipulated efficiently.\n",
    "2. It defines the relationship between data elements and operations that can be performed on them to get a more efficient algorithm).\n",
    "\r\n",
    "\r\n",
    "Data structures can be broadly categorized into two main types:\r\n",
    "\r\n",
    "Primitive Data StructurPrimitive data structures are used to represent individdatasges, such as integers, floating-point numbers, characteand rs, boolaems.\r\n",
    "\r\n",
    "Abstract Data TAbstractsstructuresctures are used to represent many data items like arrays, linked lists, stacks, queues, trees, heaps, graphs, and hash tables.\n",
    "\n",
    "                                            why we should know them?\n",
    "                                      \n",
    "1. Efficiency: Knowing which data structure to use in a given scenario can impact the performance of algorithms and applications. For example, using a hash table for fast lookups or a balanced tree for efficient searching.\r\n",
    "2. \r\n",
    "SolvingSolvinge. Knowing various data structures and their properties allows you to choose the best approach to solve a parproblem  .s.3. \r\n",
    "\r\n",
    "Optimization: Understanding data structures helps in optimizing code and improving overall software performance. By selecting the most suitable data structure and algorithm for a specific task, you can reduce execution time and memory usage, leadinapplicationslicationsa. ion4. spatternsgn Pat ring. Familiarity with data structures enables you to recognize and apply design patterns effectively,a  leading to clmaintainable.anable,.\n",
    "\n",
    " and                                     I hope that will be enough to learn different Datastructe techniques\n",
    "                            ask yourself questions: 1. how does this data structure technique store the data\n",
    "                                                    2. why is it stored in that way\n",
    "                                                    3.  scenarios the scenari\n",
    "                                                    4. onon \n",
    "    \n",
    "ction."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0d40dc1-465c-4b43-aae7-8930f4ba3f4f",
   "metadata": {},
   "source": [
    "                                        first: linked list \n",
    "1. how? \n",
    "  linked list: it stores data via pointers so it needs two parts \n",
    "    1. Data\n",
    "    2. next(pointer) to refer to next node\n",
    "\n",
    "3. why?\n",
    "\n",
    "    Dynamic Memory Allocation: This flexibility enables the list to grow or shrink in size as elements are added or removed, respectively, without requiring contiguous memory blocks.\n",
    "    \n",
    "    \n",
    "Efficient Insertions and Deletions. When inserting or deleting an element in an array, elements may need to be shifted, resulting in a higher time complexity. In a linked list, inserting or deleting an element typically involves only updating pointers, making these operations faster.    \n",
    "\n",
    "Memory efficiency, linked lists only allocate memory for the elements they contain.\n",
    "\n",
    "Flexibility in Storage: Linked lists can store elements of different sizes and types, as each node can hold a pointer to any data type  This flexibility allows for more versatile data storage compared to fixed-size a \n",
    "\n",
    "4. Scenarios:\n",
    " \n",
    "1. Undo Functionality: In applications where an \"undo\" functionality is required, linked lists can be used to implement a history of operations. Each node represents a state, and traversing the list backward allows for undoing previous actions.\n",
    "\n",
    "2. Graphs: Linked lists are used to represent adjacency lists in graph data structures. In this representation, each vertex of the graph is stored as a node, and the edges incident to the vertex are stored as linked lists.\n",
    "\n",
    "3. Music and Video Playlist: Linked lists can represent playlists in music or video players, where each node contains information about a song or video and a reference to the next item in the playlist.\n",
    "\n",
    "4. Memory Management: Linked lists can be used in memory management systems, such as dynamic memory allocation and garbage collection, where memory blocks are allocated and deallocated dynamically.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7ab1f555-82d4-439d-bac2-3344089bb0a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def append(self, data):\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "            return\n",
    "        last_node = self.head\n",
    "        while last_node.next:\n",
    "            last_node = last_node.next\n",
    "        last_node.next = new_node\n",
    "\n",
    "    def print_list(self):\n",
    "        current_node = self.head\n",
    "        while current_node:\n",
    "            print(current_node.data, end=\" -> \")\n",
    "            current_node = current_node.next\n",
    "        print(\"None\")\n",
    "\"\"\" \n",
    "Node class: Represents a single node in the linked list. It has two attributes: data to store the value of the node \n",
    "and next to store the reference to the next node.\n",
    "LinkedList class: Represents the linked list itself. It has a head attribute that points to the first node in the list.\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bd83d49e-da3b-4933-83bd-2ac6d2ad8116",
   "metadata": {},
   "outputs": [],
   "source": [
    "                                              2. stack  \n",
    "                                        How does this data structure technique store the data?\n",
    "\n",
    "Stacks store data in a sequential manner, following the Last In, First Out (LIFO) principle. Elements are added and removed from the top of the stack.\n",
    "Each time an element is added (pushed) onto the stack, it becomes the new top element. Similarly, when an element is removed (popped) from the stack, \n",
    "the element that was added last is the one that gets removed.\n",
    "\n",
    "                                         Why is it stored in that way?\n",
    "Storing data in a stack-like manner facilitates efficient last-in, and first-out operations, which are common in many scenarios. \n",
    "This storage approach is particularly useful in situations where you need to keep track of a sequence of elements and where the most recent elements are the ones of immediate interest.\n",
    "For example, in function call management, the most recently called function needs to finish executing before the previous one can resume, making a stack an ideal data structure.\n",
    "\n",
    "                                         What are the scenarios we use it?\n",
    "Stacks are used in various scenarios, including:\n",
    "\n",
    "Function call management and recursion in programming languages.\n",
    "Expression evaluation and conversion (infix to postfix/prefix).\n",
    "Backtracking algorithms like Depth-First Search (DFS).\n",
    "Undo functionality in applications.\n",
    "Syntax parsing and checking in compilers.\n",
    "Memory management, particularly in managing function call frames and local variables.\n",
    "\n",
    "History management in web browsers, where the back and forward buttons simulate a stack-like behavior.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "82c1e81c-2714-427c-8cd3-25def29411cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self.head is None\n",
    "    \n",
    "    def push(self, data):\n",
    "        new_node = Node(data)\n",
    "        if self.head is None:\n",
    "            self.head = new_node\n",
    "        else:\n",
    "            new_node.next = self.head\n",
    "            self.head = new_node\n",
    "    \n",
    "    def pop(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Stack is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            popped_item = self.head.data\n",
    "            self.head = self.head.next\n",
    "            return popped_item\n",
    "    \n",
    "    def peek(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Stack is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            return self.head.data\n",
    "    \n",
    "    def display(self):\n",
    "        current = self.head\n",
    "        if self.is_empty():\n",
    "            print(\"Stack is empty\")\n",
    "        else:\n",
    "            while current is not None:\n",
    "                print(current.data, end=\" -> \")\n",
    "                current = current.next\n",
    "            print(\"None\")\n",
    "\n",
    "# Example usage:\n",
    "stack = Stack()\n",
    "stack.push(1)\n",
    "stack.push(2)\n",
    "stack.push(3)\n",
    "stack.display()  \n",
    "\n",
    "print(\"Popped:\", stack.pop())  \n",
    "stack.display()  \n",
    "\n",
    "print(\"Peeked:\", stack.peek()) \n",
    "stack.display() \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62edeafc-4f52-4bf7-b6b3-9c815f699feb",
   "metadata": {},
   "source": [
    "                                           3 queue\n",
    "                                           How does this data structure technique store the data?\r\n",
    "\r\n",
    "A queue stores data in a First-In-First-Out (FIFO) manner. This means that the first element added to the queue is the first one to be removed. In terms of implementation, a queue can be implemented using arrays/lists or linked lists. In the case of a linked list implementation, each element of the queue is stored in a node, and these nodes are linked together                                          .\r\n",
    "Why is it stored in that way?\r\n",
    "\r\n",
    "Storing data in a FIFO manner is useful in scenarios where you need to process data in the order it was received. For example, in a printer queue, documents are printed in the order they were sent to the printer. This ensures fairness and efficiency in processing ta                                         sks.\r\n",
    "Scenarios and use cas1. uch as:\r\n",
    "Task scheduling: A queue can be used to schedule tasks in the order they are r2. eceived.\r\n",
    "Printers: A print queue manages the order in which documents are3.  printed.\r\n",
    "Message queues: In distributed systems, message queues ensure that messages are processed in the order they 4. were sent.\r\n",
    "Breadth-first search (BFS) traversal in graphs: A queue is used to traverse nodes level by level in BFS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fccf9347-0c5e-4f0e-8a6e-6a074fb2e2a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.front = None\n",
    "        self.rear = None\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.front is None\n",
    "\n",
    "    def enqueue(self, data):\n",
    "        new_node = Node(data)\n",
    "        if self.rear is None:\n",
    "            self.front = self.rear = new_node\n",
    "        else:\n",
    "            self.rear.next = new_node\n",
    "            self.rear = new_node\n",
    "\n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Queue is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            popped_item = self.front.data\n",
    "            if self.front == self.rear:\n",
    "                self.front = self.rear = None\n",
    "            else:\n",
    "                self.front = self.front.next\n",
    "            return popped_item\n",
    "\n",
    "    def display(self):\n",
    "        current = self.front\n",
    "        if self.is_empty():\n",
    "            print(\"Queue is empty\")\n",
    "        else:\n",
    "            while current is not None:\n",
    "                print(current.data, end=\" -> \")\n",
    "                current = current.next\n",
    "            print(\"None\")\n",
    "\n",
    "# Example usage:\n",
    "queue = Queue()\n",
    "queue.enqueue(1)\n",
    "queue.enqueue(2)\n",
    "queue.enqueue(3)\n",
    "queue.display()  # Output: 1 -> 2 -> 3 -> None\n",
    "\n",
    "print(\"Dequeued:\", queue.dequeue())  # Output: Dequeued: 1\n",
    "queue.display()  # Output: 2 -> 3 -> None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5322927c-8cf2-4707-8f02-fc17a8846988",
   "metadata": {},
   "source": [
    "                                             4. dequeue\n",
    "                                             How does this data structure technique store the data?\r\n",
    "\r\n",
    "A deque, short for double-ended queue, is a data structure that allowthe s insertion and deletion of elements from both the front and the back. It can be thought of as a hybrid of a stack and a queue. Deques can be implemented using arrays/lists or linked lists. In the case of a linked list implementation, each element of the deque is stored in a node, and these nodes are linked together bidirectionall\n",
    "y                                              .\r\n",
    "Why is it stored in that w\n",
    "                                              y?\r\n",
    "\r\n",
    "Storing data in a deque allows for efficient insertion and deletion operations at both ends of the data structure. This flexibility makes deques suitable for scenarios where elements need to be added or removed from both ends frequently. For example, deques are commonly used in scenarios such as implementing queues, stacks, and double-ended priority qu\n",
    "e                                              ues.\r\n",
    "Scenarios and use cases:\r\n",
    "\r\n",
    "Deques are commonly used in scenarios where elements need to be added or removed from both ends, such as:\r\n",
    "Implementing queues and stacks: Deques can be used to implement both queues (enqueue and dequeue operations) and stacks (push and pop operations).\r\n",
    "Sliding window problems: Deques are useful in solving problems where you need to maintain a window of elements and perform operations on it efficiently, such as finding the maximum or minimum in a sliding window of fixed size.\r\n",
    "Palindrome checking: Deques are used to efficiently check if a string is a palindrome by comparing characters from\n",
    " both ends."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "80a67fd4-796f-4e03-a0bd-3b87098bd2ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "class MyDeque:\n",
    "    def __init__(self):\n",
    "        self.deque = deque()\n",
    "\n",
    "    def is_empty(self):\n",
    "        return len(self.deque) == 0\n",
    "\n",
    "    def add_front(self, data):\n",
    "        self.deque.appendleft(data)\n",
    "\n",
    "    def add_rear(self, data):\n",
    "        self.deque.append(data)\n",
    "\n",
    "    def remove_front(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Deque is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            return self.deque.popleft()\n",
    "\n",
    "    def remove_rear(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Deque is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            return self.deque.pop()\n",
    "\n",
    "    def peek_front(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Deque is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            return self.deque[0]\n",
    "\n",
    "    def peek_rear(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Deque is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            return self.deque[-1]\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.deque)\n",
    "\n",
    "    def display(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Deque is empty\")\n",
    "        else:\n",
    "            print(\"Front ->\", end=\" \")\n",
    "            for item in self.deque:\n",
    "                print(item, end=\" \")\n",
    "            print(\"<- Rear\")\n",
    "\n",
    "# Example usage:\n",
    "my_deque = MyDeque()\n",
    "my_deque.add_front(1)\n",
    "my_deque.add_rear(2)\n",
    "my_deque.add_front(3)\n",
    "my_deque.display()  # Output: Front -> 3 1 2 <- Rear\n",
    "\n",
    "print(\"Removed from front:\", my_deque.remove_front())  # Output: Removed from front: 3\n",
    "print(\"Removed from rear:\", my_deque.remove_rear())    # Output: Removed from rear: 2\n",
    "my_deque.display()  # Output: Front -> 1 <- Rear\n",
    "\n",
    "print(\"Peek front:\", my_deque.peek_front())  # Output: Peek front: 1\n",
    "print(\"Peek rear:\", my_deque.peek_rear())    # Output: Peek rear: 1\n",
    "\n",
    "print(\"Deque size:\", my_deque.size())  # Output: Deque size: 1\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class MyDeque:\n",
    "    def __init__(self):\n",
    "        self.deque = deque()\n",
    "\n",
    "    def is_empty(self):\n",
    "        return len(self.deque) == 0\n",
    "\n",
    "    def add_front(self, data):\n",
    "        self.deque.appendleft(data)\n",
    "\n",
    "    def add_rear(self, data):\n",
    "        self.deque.append(data)\n",
    "\n",
    "    def remove_front(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Deque is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            return self.deque.popleft()\n",
    "\n",
    "    def remove_rear(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Deque is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            return self.deque.pop()\n",
    "\n",
    "    def peek_front(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Deque is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            return self.deque[0]\n",
    "\n",
    "    def peek_rear(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Deque is empty\")\n",
    "            return None\n",
    "        else:\n",
    "            return self.deque[-1]\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.deque)\n",
    "\n",
    "    def display(self):\n",
    "        if self.is_empty():\n",
    "            print(\"Deque is empty\")\n",
    "        else:\n",
    "            print(\"Front ->\", end=\" \")\n",
    "            for item in self.deque:\n",
    "                print(item, end=\" \")\n",
    "            print(\"<- Rear\")\n",
    "\n",
    "# Example usage:\n",
    "my_deque = MyDeque()\n",
    "my_deque.add_front(1)\n",
    "my_deque.add_rear(2)\n",
    "my_deque.add_front(3)\n",
    "my_deque.display()  # Output: Front -> 3 1 2 <- Rear\n",
    "\n",
    "print(\"Removed from front:\", my_deque.remove_front())  # Output: Removed from front: 3\n",
    "print(\"Removed from rear:\", my_deque.remove_rear())    # Output: Removed from rear: 2\n",
    "my_deque.display()  # Output: Front -> 1 <- Rear\n",
    "\n",
    "print(\"Peek front:\", my_deque.peek_front())  # Output: Peek front: 1\n",
    "print(\"Peek rear:\", my_deque.peek_rear())    # Output: Peek rear: 1\n",
    "\n",
    "print(\"Deque size:\", my_deque.size())  # Output: Deque size: 1\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}