LinkedList.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return str(\"Node\")\n",
    "\n",
    "    def __str__(self):\n",
    "        return str({\"value\":self.value,\n",
    "                    \"next\": self.next})\n",
    "\n",
    "class LinkedList:\n",
    "\n",
    "    def __init__(self, value):\n",
    "        new_node = Node(value)\n",
    "        self.head = new_node\n",
    "        self.tail = new_node\n",
    "        self.length = 1\n",
    "    \n",
    "    def __str__(self):\n",
    "        linked_list = \"\"\n",
    "        temp = self.head\n",
    "        if temp is None:\n",
    "            return \"None\"\n",
    "        for _ in range(0, self.length+1):\n",
    "            linked_list += str(temp.value)\n",
    "            linked_list += \"->\"\n",
    "            if temp.next is None:\n",
    "                linked_list += \"None\"\n",
    "                return linked_list\n",
    "            temp = temp.next\n",
    "        return linked_list\n",
    "            \n",
    "    \n",
    "    def append(self, value):\n",
    "        new_node = Node(value)\n",
    "        # if the linked list is empty assign head and tail to new node\n",
    "        if self.head is None:\n",
    "            self.head = new_node\n",
    "            self.tail = new_node\n",
    "        # if not, assign, tail.next  as new node(now None) and then shift tail to the new node(already new_node.next is None)\n",
    "        else:\n",
    "            self.tail.next = new_node\n",
    "            self.tail = new_node\n",
    "        # increment the length of LL and return True(will be used in another function)\n",
    "        self.length +=1\n",
    "        return True\n",
    "    \n",
    "    def pop(self):\n",
    "        # if length is 0, return None\n",
    "        if self.length == 0:\n",
    "            return None\n",
    "        # we are using pre and temp, to find the node before tail (if doubly linked list we can do a prev in tail to get that)\n",
    "        # here we need to do it ourselves\n",
    "        pre = self.head\n",
    "        temp = self.head\n",
    "        # our goal is to find new tail(since pop removes the last node, node before last node is our new tail)\n",
    "        while(temp.next): # until temp.next is not none - temp is not the tail\n",
    "            prev = temp # retaining the previous node of tail in prev\n",
    "            temp = temp.next\n",
    "        prev.next = None\n",
    "        self.tail = prev\n",
    "        self.length -= 1\n",
    "        # for cases when we have only one node in LL, the node will not be removed from above steps so\n",
    "        if self.length == 0:\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        return temp # the last element removed should be returned\n",
    "\n",
    "\n",
    "    def prepend(self, value):\n",
    "        new_node = Node(value)\n",
    "        # if LL is empty just assign head and tail to new node\n",
    "        if self.length == 0:\n",
    "            self.head = new_node\n",
    "            self.tail = new_node\n",
    "        # else, self.head is the first node, assign self.head to new_node.next and shift self.head as new node\n",
    "        else:\n",
    "            new_node.next = self.head\n",
    "            self.head = new_node\n",
    "        self.length += 1\n",
    "        return True\n",
    "    \n",
    "    def pop_first(self):\n",
    "        if self.length == 0:\n",
    "            return None\n",
    "        # we need to return the removed element so assign temp with self.head\n",
    "        temp = self.head\n",
    "        # move head to the next node in LL\n",
    "        self.head = self.head.next\n",
    "        # detach temp by assigning temp.next = None\n",
    "        temp.next = None\n",
    "        self.length -= 1\n",
    "        if self.length == 0:\n",
    "            self.tail = None\n",
    "        return temp\n",
    "    \n",
    "    def get(self,index):\n",
    "        # if out of bound\n",
    "        if index < 0 or index >= self.length:\n",
    "            return None\n",
    "        # we need to return node so assign head to temp and loop to get to the index position\n",
    "        temp = self.head\n",
    "        for _ in range(index):\n",
    "            temp = temp.next\n",
    "        return temp\n",
    "\n",
    "    def set(self, index, value):\n",
    "        # use get to get the node at index, if node is not none, set the value\n",
    "        temp = self.get(index)\n",
    "        if temp:\n",
    "            temp.value = value\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def insert(self, index, value):\n",
    "        # index out of bound\n",
    "        if index < 0 or index>self.length:\n",
    "            return False\n",
    "        # when you have to insert as the first node, do prepend\n",
    "        if index == 0:\n",
    "            return self.prepend(value)\n",
    "        # when you have to insert as the last node, do append\n",
    "        if index == self.length:\n",
    "            return self.append(value)\n",
    "        # Any other position, get the node before index position and swap next values\n",
    "        new_node = Node(value)\n",
    "        temp = self.get(index -1)\n",
    "        new_node.next = temp.next\n",
    "        temp.next = new_node\n",
    "        self.length += 1\n",
    "        return True\n",
    "\n",
    "    \n",
    "    def remove(self, index):\n",
    "        if index < 0 or index>=self.length:\n",
    "            return None\n",
    "        if index == 0:\n",
    "            return self.pop_first()\n",
    "        if index == self.length - 1:\n",
    "            return self.pop()\n",
    "        prev = self.get(index - 1)\n",
    "        temp = prev.next\n",
    "        prev.next = temp.next\n",
    "        temp.next = None\n",
    "        self.length -= 1\n",
    "        return temp\n",
    "    \n",
    "    def reverse(self):\n",
    "        temp = self.head\n",
    "        self.head = self.tail\n",
    "        self.tail = temp\n",
    "        after = temp.next\n",
    "        before = None\n",
    "        for _ in range(self.length):\n",
    "            after = temp.next\n",
    "            temp.next = before\n",
    "            before = temp\n",
    "            temp = after\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "appending 2\n",
      "4->2->None\n",
      "popping 2 {'value': 2, 'next': None}\n",
      "4->None\n",
      "prepending 2 True\n",
      "2->4->None\n",
      "pop_first 2 {'value': 2, 'next': None}\n",
      "4->None\n",
      "pop_first 4 {'value': 4, 'next': None}\n",
      "None\n",
      "appending 2 True\n",
      "appending 4 True\n",
      "2->4->None\n",
      "Get index 2 None\n",
      "Get index 0 {'value': 2, 'next': Node}\n",
      "set index 0 True\n",
      "5->4->None\n",
      "set index 2 False\n",
      "5->4->None\n",
      "3->5->1->4->None\n",
      "5->1->4->None\n",
      "None\n",
      "4->1->5->None\n"
     ]
    }
   ],
   "source": [
    "my_linked_list = LinkedList(4)\n",
    "print(\"appending 2\")\n",
    "my_linked_list.append(2)\n",
    "print(my_linked_list)\n",
    "print(\"popping 2\",my_linked_list.pop())\n",
    "print(my_linked_list)\n",
    "print(\"prepending 2\", my_linked_list.prepend(2))\n",
    "print(my_linked_list)\n",
    "print(\"pop_first 2\", my_linked_list.pop_first())\n",
    "print(my_linked_list)\n",
    "print(\"pop_first 4\", my_linked_list.pop_first())\n",
    "print(my_linked_list)\n",
    "print(\"appending 2\", my_linked_list.append(2))\n",
    "print(\"appending 4\", my_linked_list.append(4))\n",
    "print(my_linked_list)\n",
    "print(\"Get index 2\",my_linked_list.get(2))\n",
    "print(\"Get index 0\",my_linked_list.get(0))\n",
    "\n",
    "print(\"set index 0\",my_linked_list.set(0,5))\n",
    "print(my_linked_list)\n",
    "print(\"set index 2\",my_linked_list.set(2,5))\n",
    "print(my_linked_list)\n",
    "my_linked_list.insert(0, 3)\n",
    "my_linked_list.insert(2,1)\n",
    "print(my_linked_list)\n",
    "my_linked_list.remove(0)\n",
    "print(my_linked_list)\n",
    "print(my_linked_list.reverse())\n",
    "print(my_linked_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}