{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked Lists\n",
    "\n",
    "## Agenda\n",
    "\n",
    "1. The `LinkedList` and `Node` classes  \n",
    "2. Implementing `append`\n",
    "3. Implementing deletion\n",
    "4. Bidirectional links\n",
    "5. Run-time analysis\n",
    "6. Closing remarks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. The `LinkedList` and `Node` classes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class LinkedList:\n",
    "    class Node:\n",
    "        def __init__(self, val, next=None):\n",
    "            self.val = val\n",
    "            self.next = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.count = 0\n",
    "    \n",
    "    def prepend(self, value):\n",
    "        pass\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.count\n",
    "        \n",
    "    def __iter__(self):\n",
    "        n = self.head\n",
    "        while n:\n",
    "            yield n.val\n",
    "            n = n.next\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return '[' + ', '.join(x for x in self) + ']'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.prepend(i)\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Implementing `append`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Option 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class LinkedList (LinkedList): # note: using inheritance to extend prior definition\n",
    "    def append(self, value):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.append(i)\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Option 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class LinkedList (LinkedList):\n",
    "    def __init__(self):\n",
    "        self.head = self.tail = None\n",
    "        self.count = 0\n",
    "        \n",
    "    def prepend(self, value):\n",
    "        pass\n",
    "        \n",
    "    def append(self, value):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.append(i)\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Implementing deletion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deleting the head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class LinkedList (LinkedList):\n",
    "    def del_head(self):\n",
    "        assert(len(self) > 0)\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.append(i)\n",
    "lst.del_head()\n",
    "lst.del_head()\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deleting the tail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class LinkedList (LinkedList):\n",
    "    def del_tail(self):\n",
    "        assert(len(self) > 0)\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.append(i)\n",
    "lst.del_tail()\n",
    "lst.del_tail()\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Bidirectional links (Doubly-linked list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class LinkedList:\n",
    "    class Node:\n",
    "        def __init__(self, val, prior=None, next=None):\n",
    "            self.val = val\n",
    "            self.prior = prior\n",
    "            self.next  = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "        \n",
    "    def prepend(self, value):\n",
    "        self.count += 1\n",
    "        \n",
    "    def append(self, value):\n",
    "        self.count += 1\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self.count\n",
    "        \n",
    "    def __iter__(self):\n",
    "        n = self.head.next\n",
    "        while n is not self.head:\n",
    "            yield n.val\n",
    "            n = n.next\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return '[' + ', '.join(str(x) for x in self) + ']'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.prepend(i)\n",
    "for i in range(10):\n",
    "    lst.append(i)\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Run-time analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run-time complexities for circular, doubly-linked list of $N$ elements:\n",
    "\n",
    "- indexing (position-based access) = $O(?)$\n",
    "- search (unsorted) = $O(?)$\n",
    "- search (sorted) = $O(?)$ --- binary search isn't possible!\n",
    "- prepend = $O(?)$\n",
    "- append = $O(?)$\n",
    "- insertion at arbitrary position: traversal = $O(?)$ + insertion = $O(?)$\n",
    "- deletion of arbitrary element: traversal = $O(?)$ + deletion = $O(?)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. Closing remarks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}