LinkedList.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked List\n",
    "\n",
    "## Overview\n",
    "A **Linked List** is a linear data structure where elements, known as **nodes**, are stored in separate memory locations and connected using **pointers**. Each node consists of:\n",
    "\n",
    "- **Data**: The actual value stored.\n",
    "- **Pointer (next)**: A reference to the next node in the sequence.\n",
    "\n",
    "Unlike arrays, linked lists do not require a contiguous memory block. Instead, elements are scattered in memory and linked using pointers.\n",
    "\n",
    "---\n",
    "\n",
    "## Why Do We Need Linked Lists?\n",
    "\n",
    "1. **Dynamic Size**: \n",
    "   - Unlike arrays, linked lists can grow or shrink dynamically without the need for memory reallocation.\n",
    "\n",
    "2. **Efficient Insertions/Deletions**: \n",
    "   - Adding or removing elements in a linked list (especially at the start or middle) is more efficient than in arrays since it doesn't require shifting elements.\n",
    "\n",
    "3. **No Wasted Memory**: \n",
    "   - Arrays allocate a fixed memory block, which may lead to unused space. Linked lists allocate memory only when needed.\n",
    "\n",
    "---\n",
    "\n",
    "## Types of Linked Lists\n",
    "\n",
    "1. **Singly Linked List**:\n",
    "   - Each node points to the next node only.\n",
    "\n",
    "2. **Doubly Linked List**:\n",
    "   - Each node has pointers to both the previous and next nodes.\n",
    "\n",
    "3. **Circular Linked List**:\n",
    "   - The last node connects back to the first node, forming a loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "Apple--->Bannana--->\n"
     ]
    }
   ],
   "source": [
    "\"\"\"A class representing a node in a linked list.\"\"\"\n",
    "class Node:\n",
    "    def __init__(self,data=None,next=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "\n",
    "class LinkedList:\n",
    "    \"\"\"This class representing singly Linked list .\"\"\"\n",
    "    def __init__(self):\n",
    "        self.head = None #intialize Head of the linked list\n",
    "\n",
    "    # ----------------insert__at__begin\n",
    "    def insert_at_begining(self,data):\n",
    "        node = Node(data,self.head)\n",
    "        self.head = node\n",
    "\n",
    "    # ----------insert__End__\n",
    "    def insert_at_end(self,data):\n",
    "\n",
    "        if self.head is None:\n",
    "            self.head = Node(data,None)\n",
    "            return \n",
    "        \n",
    "        itr = self.head\n",
    "\n",
    "        while itr.next:\n",
    "            itr = itr.next\n",
    "\n",
    "        itr.next = Node(data,None)\n",
    "    \n",
    "    # ------------insert_values\n",
    "    def insert_values(self,value):\n",
    "        self.head = None\n",
    "\n",
    "        for i in value:\n",
    "            self.insert_at_end(i)\n",
    "    \n",
    "    #--------------- get length function\n",
    "    def get_length(self):\n",
    "        count = 0\n",
    "        itr = self.head\n",
    "\n",
    "        while itr:\n",
    "            count += 1\n",
    "            itr = itr.next\n",
    "\n",
    "        return count   \n",
    "    # -----------------------remove_at \n",
    "    def remove_at(self,index):\n",
    "        if index  < 0 or index > self.get_length() -1:\n",
    "            raise Exception(\"index is going out of range\") \n",
    "        if index == 0: \n",
    "            self.head = self.head.next\n",
    "\n",
    "            return \n",
    "        count = 0\n",
    "        itr = self.head\n",
    "        while itr:\n",
    "            if count == index -1:\n",
    "                itr.next = itr.next.next\n",
    "                break\n",
    "\n",
    "            itr = itr.next\n",
    "            count += 1\n",
    "    def insert_at(self,index,data):\n",
    "        pass\n",
    "\n",
    "    # ----------------------print_function \n",
    "    def print(self):\n",
    "        if self.head is None:\n",
    "            print(\"My Linked list is Empty !!\")\n",
    "            return \n",
    "        \n",
    "        itr = self.head \n",
    "        llstr = ''\n",
    "        \n",
    "        while itr :\n",
    "            llstr += str(itr.data) + '--->'\n",
    "            itr = itr.next\n",
    "\n",
    "        print(llstr) \n",
    "\n",
    "\n",
    "ll =LinkedList()\n",
    "\n",
    "# ll.insert_at_begining(123)\n",
    "# ll.insert_at_begining(23)\n",
    "# ll.insert_at_end(45)\n",
    "\n",
    "ll.insert_values([\"Apple\",\"Bannana\",\"WaterMelon\"])\n",
    "len_ = ll.get_length()\n",
    "ll.remove_at(2)\n",
    "\n",
    "print(len_)\n",
    "\n",
    "ll.print()\n",
    "        "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "dsa",
   "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
}