{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, init_data):\n",
    "        self.data = init_data\n",
    "        self.next = None\n",
    "        \n",
    "    def get_data(self):\n",
    "        return self.data\n",
    "    \n",
    "    def get_next(self):\n",
    "        return self.next\n",
    "    \n",
    "    def set_data(self, new_data):\n",
    "        self.data = new_data\n",
    "        \n",
    "    def set_next(self, new_next):\n",
    "        self.next = new_next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Unordered List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UnorderedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        \n",
    "    def add(self, item):\n",
    "        # A prepend to list operation\n",
    "        temp = Node(item)\n",
    "        temp.set_next(self.head)\n",
    "        self.head = temp\n",
    "        \n",
    "    def length(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "        \n",
    "        while current != None:\n",
    "            count += 1\n",
    "            current = current.get_next()\n",
    "            \n",
    "        return count\n",
    "    \n",
    "    def search(self, item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        \n",
    "        while current != None and not found:\n",
    "            if current.get_data() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                current = current.get_next()\n",
    "            \n",
    "        return found\n",
    "    \n",
    "    def remove(self, item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        found = False\n",
    "        \n",
    "        while current != None and not found:\n",
    "            if current.get_data() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.get_next()\n",
    "                \n",
    "        if previous == None:\n",
    "            self.head = current.get_next()\n",
    "        elif current != None:\n",
    "            previous.set_next(current.get_next())\n",
    "        else:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import sample"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[29, 71, 12, 9, 98, 18, 56, 70, 74, 83, 76, 28, 41, 75, 45, 78, 72, 42, 31, 44, 19, 43, 57, 53, 81, 94, 69, 95, 15, 92, 4, 61, 37, 20, 38, 10, 30, 14, 93, 64, 84, 55, 99, 89, 21, 79, 0, 65, 87, 86]\n"
     ]
    }
   ],
   "source": [
    "nums = sample(range(100), k=50)\n",
    "print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "ulist = UnorderedList()\n",
    "ulist.add(1)\n",
    "ulist.add(2)\n",
    "ulist.remove(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in nums:\n",
    "    ulist.add(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "86 87 65 0 79 21 89 99 55 84 64 93 14 30 10 38 20 37 61 4 92 15 95 69 94 81 53 57 43 19 44 31 42 72 78 45 75 41 28 76 83 74 70 56 18 98 9 12 71 29 2 1 "
     ]
    }
   ],
   "source": [
    "current = ulist.head\n",
    "while current != None:\n",
    "    print(current.data, end=\" \")\n",
    "    current = current.get_next()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ordered List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class OrderedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        \n",
    "    def search(self, item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        stop = False\n",
    "        \n",
    "        while current != None and not found and not stop:\n",
    "            if current.get_data() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.get_data() > item:\n",
    "                    stop = True\n",
    "                else:\n",
    "                    current = current.get_next()\n",
    "                    \n",
    "        return found\n",
    "    \n",
    "    \n",
    "    def add(self, item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        \n",
    "        while current != None and not stop:\n",
    "            if current.get_data() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.get_next()\n",
    "                \n",
    "        temp = Node(item)\n",
    "        if previous == None:\n",
    "            temp.set_next(self.head)\n",
    "            self.head = temp\n",
    "        else:\n",
    "            temp.set_next(current)\n",
    "            previous.set_next(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = sample(range(100), k=50)\n",
    "print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "olist = OrderedList()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in nums:\n",
    "    olist.add(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "current = olist.head\n",
    "while current != None:\n",
    "    print(current.data, end=\" \")\n",
    "    current = current.get_next()"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
