array-list.ipynb

balanced-bsts-demo.ipynb

binary-search-trees.ipynb

bst-ds-demo.ipynb

hashtable-demo.ipynb

iterators-demo.ipynb

lang-intro-part1.ipynb

lang-intro-part2.ipynb

lang-intro-part3.ipynb

linked-list-demo.ipynb

{
 "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": {},
   "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": {},
   "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": {},
   "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": {},
   "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": {},
   "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": {},
   "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": {},
   "outputs": [],
   "source": [
    "class LinkedList (LinkedList):\n",
    "    def del_head(self):\n",
    "        assert(len(self) > 0)\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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": {},
   "outputs": [],
   "source": [
    "class LinkedList (LinkedList):\n",
    "    def del_tail(self):\n",
    "        assert(len(self) > 0)\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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) & Sentinel head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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 __getitem__(self, idx):\n",
    "        pass\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": {},
   "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. Incorporating a \"cursor\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.head = self.cursor = LinkedList.Node(None)\n",
    "        self.head.prior = self.head.next = self.head\n",
    "        self.count = 0\n",
    "                \n",
    "    def append(self, value):\n",
    "        n = LinkedList.Node(value, prior=self.head.prior, next=self.head)\n",
    "        n.prior.next = n.next.prior = n\n",
    "        self.count += 1\n",
    "        \n",
    "    def cursor_set(self, idx):\n",
    "        pass\n",
    "    \n",
    "    def cursor_insert(self, x):\n",
    "        pass\n",
    "    \n",
    "    def cursor_delete(self):\n",
    "        pass\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": {},
   "outputs": [],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.append(i)\n",
    "lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lst.cursor_set(4)\n",
    "for x in 'abcd':\n",
    "    lst.cursor_insert(x)\n",
    "lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lst.cursor_set(8)\n",
    "for _ in range(4):\n",
    "    lst.cursor_delete()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. 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",
    "- indexing = $O(?)$\n",
    "- insertion at arbitrary position: indexing = $O(?)$ + insertion = $O(?)$\n",
    "- deletion of arbitrary element: indexing = $O(?)$ + deletion = $O(?)$"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}

linked-structures-demo.ipynb

on-recursion-demo.ipynb

priority-queues-demo.ipynb

searching-sorting-timing.ipynb

stacks-and-queues-demo.ipynb