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

linked-structures-demo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked Structures\n",
    "\n",
    "## Agenda\n",
    "\n",
    "1. Motives\n",
    "2. Objectives\n",
    "3. Mechanisms\n",
    "4. Linked Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Motives"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from timeit import timeit\n",
    "\n",
    "def time_array_front_insert_delete(n):\n",
    "    return timeit('lst.insert(0, None) ; del lst[0]',\n",
    "                  'lst = list(range({}))'.format(n),\n",
    "                  number=1000)\n",
    "\n",
    "ns = np.linspace(100, 10000, 50)\n",
    "plt.plot(ns, [time_array_front_insert_delete(int(n)) for n in ns], 'ro')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# consider:\n",
    "\n",
    "def concatenate(arr1, arr2):\n",
    "    \"\"\"Concatenates the contents of arr1 and arr2 as efficiently (time-wise)\n",
    "    as possible, so that the resulting structure can be used to index all\n",
    "    combined elements (arr1's followed by arr2's).\"\"\"\n",
    "\n",
    "    # option 1: O(?)\n",
    "    for x in arr2:\n",
    "        arr1.append(x)\n",
    "    return arr1\n",
    "\n",
    "    # option 2: O(?)\n",
    "    arr1.extend(arr2)\n",
    "    return arr1\n",
    "\n",
    "    # option 3: O(?)\n",
    "    return arr1 + arr2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Objectives\n",
    "\n",
    "We would like a new data storage mechanism for constructing data structures that:\n",
    "\n",
    "- does not require monolithic, contiguous memory allocation,\n",
    "- allows individual elements to be flexibly and efficiently reorganized,\n",
    "- and preserves the ability to locate (e.g., via position) and iterate over elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Mechanisms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1. Two-Element Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# data items\n",
    "i1 = 'lions'\n",
    "i2 = 'tigers'\n",
    "i3 = 'bears'\n",
    "i4 = 'oh, my'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# creating individual \"links\"\n",
    "l1 = [,]\n",
    "l2 = [,]\n",
    "l3 = [,]\n",
    "l4 = [,]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# link-ing them together\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# iteration\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# prepending\n",
    "\n",
    "i0 = 'walruses'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# insertion\n",
    "\n",
    "i2_5 = 'elephants'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# deletion\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2. \"Link\" objects"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Link:\n",
    "    def __init__(self, val, next=None):\n",
    "        self.val = val\n",
    "        self.next = next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# manually constructing a list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# prepending\n",
    "\n",
    "def prepend(l, val):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = None\n",
    "for x in range(10):\n",
    "    l = prepend(l, x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# iterator\n",
    "\n",
    "def link_iterator(l):\n",
    "    yield"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in link_iterator(l):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# iteration based on a recursive pattern\n",
    "\n",
    "def link_iterator_rec(l):\n",
    "    yield"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in link_iterator_rec(l):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Linked Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedList:\n",
    "    class Link:\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",
    "        \n",
    "    def prepend(self, val):\n",
    "        pass\n",
    "        \n",
    "    def __iter__(self):\n",
    "        pass\n",
    "            \n",
    "    def __repr__(self):\n",
    "        return '[' + ', '.join(str(x) for x in self) + ']'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = LinkedList()\n",
    "for x in range(10):\n",
    "    l.prepend(x)\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryLink:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# manual construction of a \"tree\" representing the expression ((5+3)*(8-4))\n",
    "t = BinaryLink('*')\n",
    "t.left = BinaryLink('+')\n",
    "t.left.left  = BinaryLink('5')\n",
    "t.left.right = BinaryLink('3')\n",
    "t.right = BinaryLink('-')\n",
    "t.right.left  = BinaryLink('8')\n",
    "t.right.right = BinaryLink('4')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_expr_tree(t):\n",
    "    if t:\n",
    "        if not t.val.isdigit():\n",
    "            print('(', end='')\n",
    "        print_expr_tree(t.left)\n",
    "        print(t.val, end='')\n",
    "        print_expr_tree(t.right)\n",
    "        if not t.val.isdigit():\n",
    "            print(')', end='')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_expr_tree(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 4.3 N-ary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NaryLink:\n",
    "    def __init__(self, val, n=2):\n",
    "        self.val = val\n",
    "        self.children = [None] * n\n",
    "        \n",
    "    def __getitem__(self, idx):\n",
    "        return self.children[idx]\n",
    "    \n",
    "    def __setitem__(self, idx, val):\n",
    "        self.children[idx] = val\n",
    "        \n",
    "    def __iter__(self):\n",
    "        for c in self.children:\n",
    "            yield c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "root = NaryLink('Kingdoms', n=5)\n",
    "\n",
    "root[0] = NaryLink('Animalia', n=35)\n",
    "root[1] = NaryLink('Plantae', n=12)\n",
    "root[2] = NaryLink('Fungi', n=7)\n",
    "root[3] = NaryLink('Protista', n=5)\n",
    "root[4] = NaryLink('Monera', n=5)\n",
    "\n",
    "root[2][0] = NaryLink('Chytridiomycota')\n",
    "root[2][1] = NaryLink('Blastocladiomycota')\n",
    "root[2][2] = NaryLink('Glomeromycota')\n",
    "root[2][3] = NaryLink('Ascomycota')\n",
    "root[2][4] = NaryLink('Basidiomycota')\n",
    "root[2][5] = NaryLink('Microsporidia')\n",
    "root[2][6] = NaryLink('Neocallimastigomycota')\n",
    "\n",
    "def tree_iter(root):\n",
    "    if root:\n",
    "        yield root.val\n",
    "        for c in root:\n",
    "            yield from tree_iter(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "for x in tree_iter(root):\n",
    "    print(x)"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}

on-recursion-demo.ipynb

priority-queues-demo.ipynb

searching-sorting-timing.ipynb

stacks-and-queues-demo.ipynb