Lab06-distribute_DataStructuresLab.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q1. Dynamic Arrays\n",
    "\n",
    "In the dynamic arrays example in the lecture, we did not implement the `set` and `delete` interfaces. Implement them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting dynamic_array.h\n"
     ]
    }
   ],
   "source": [
    "%%file dynamic_array.h\n",
    "\n",
    "\n",
    "typedef struct DArray {\n",
    "    int upto;\n",
    "    int size;\n",
    "    int *array;\n",
    "} DArray;\n",
    "\n",
    "int DArray_init(DArray* arr);\n",
    "int append(DArray* arr, int i);\n",
    "int get(DArray* arr, int index);\n",
    "int get_index(DArray* arr, int value);\n",
    "int set(DArray* arr, int index, int value);\n",
    "int delete(DArray* arr, int value);\n",
    "void DArray_free(DArray* arr);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting dynamic_array2.c\n"
     ]
    }
   ],
   "source": [
    "%%file dynamic_array2.c\n",
    "\n",
    "#include <stdlib.h>\n",
    "#include <string.h>\n",
    "#include \"dynamic_array.h\"\n",
    "\n",
    "int CAPACITY_INIT = 1;\n",
    "int GROWTH_FACTOR = 2;\n",
    "\n",
    "int DArray_init(DArray* arr){\n",
    "    arr->array = (int *) malloc(CAPACITY_INIT*sizeof(int));\n",
    "    if (arr->array == NULL) {\n",
    "        return -1;\n",
    "    }\n",
    "    arr->upto = 0;\n",
    "    arr->size = CAPACITY_INIT;\n",
    "    return 1;\n",
    "}\n",
    "\n",
    "int append(DArray* arr, int i){\n",
    "    int *iptr;\n",
    "    if (arr->upto >= arr->size) {\n",
    "        /* tmp pointer needed below as if allocation failed, original array would be lost */\n",
    "        iptr = (int *) realloc(arr->array, arr->size*GROWTH_FACTOR*sizeof(int));\n",
    "        if (iptr == NULL) {\n",
    "            return -1;\n",
    "        }\n",
    "        arr->array = iptr;\n",
    "        arr->size *= GROWTH_FACTOR;\n",
    "    }\n",
    "    arr->array[arr->upto] = i;\n",
    "    return arr->upto++;       \n",
    "}\n",
    "\n",
    "int get(DArray* arr, int index) {\n",
    "    if (index >= arr->upto || index < 0) {\n",
    "        return -1;\n",
    "    }\n",
    "    return arr->array[index];\n",
    "}\n",
    "\n",
    "int get_index(DArray* arr, int value) {\n",
    "    int i;\n",
    "    for (i=0; i< arr->upto; i++){\n",
    "        if (arr->array[i]==value) {\n",
    "            return i;\n",
    "        }\n",
    "    }\n",
    "    return -1;\n",
    "}\n",
    "\n",
    "void DArray_free(DArray *arr) {\n",
    "  free(arr->array);\n",
    "}\n",
    "\n",
    "/*your code here*/\n",
    "int set(DArray* arr, int index, int value) {\n",
    "    if (index >= arr->upto || index < 0) {\n",
    "        return -1;\n",
    "    }\n",
    "    arr->array[index] = value;\n",
    "    return index;\n",
    "}\n",
    "\n",
    "int delete(DArray* arr, int value) {\n",
    "    int index = get_index(arr, value);\n",
    "    if (index >= arr->upto || index < 0) {\n",
    "        return -1;\n",
    "    }\n",
    "    \n",
    "    int i;\n",
    "    for (i=index; i< arr->upto-1; i++){\n",
    "        arr->array[i] = arr->array[i+1];\n",
    "    }\n",
    "    \n",
    "    return arr->upto--;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can test our code with the following new \"driver\" file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting dademo2.c\n"
     ]
    }
   ],
   "source": [
    "%%file dademo2.c\n",
    "\n",
    "#include <stdio.h>\n",
    "#include \"dynamic_array.h\"\n",
    "\n",
    "int main() {\n",
    "    DArray dynarray;\n",
    "    DArray_init(&dynarray);\n",
    "    printf(\"%d %d\\n\", dynarray.upto, dynarray.size);\n",
    "    int i;\n",
    "    for (i = 0; i < 200; i++) {\n",
    "        append(&dynarray, i);\n",
    "        printf(\"upto %d size %d val %d\\n\", dynarray.upto, dynarray.size, get(&dynarray, i));\n",
    "    }\n",
    "    for (i = 185; i < 190; i++) {\n",
    "        set(&dynarray, i, i+1);\n",
    "        printf(\"i %d val %d\\n\", i, get(&dynarray, i));\n",
    "    }\n",
    "    for (i = 180; i < 182; i++) {\n",
    "        delete(&dynarray, i);\n",
    "        printf(\"i %d val %d upto %d\\n\", i, get(&dynarray, i), dynarray.upto);\n",
    "    }\n",
    "    for (i = 180; i < 195; i++) {\n",
    "        printf(\"val %d index %d\\n\", i, get_index(&dynarray, i));\n",
    "    }\n",
    "    DArray_free(&dynarray);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compile and run it thus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "!gcc -o dademo2 dademo2.c dynamic_array2.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1\r\n",
      "upto 1 size 1 val 0\r\n",
      "upto 2 size 2 val 1\r\n",
      "upto 3 size 4 val 2\r\n",
      "upto 4 size 4 val 3\r\n",
      "upto 5 size 8 val 4\r\n",
      "upto 6 size 8 val 5\r\n",
      "upto 7 size 8 val 6\r\n",
      "upto 8 size 8 val 7\r\n",
      "upto 9 size 16 val 8\r\n",
      "upto 10 size 16 val 9\r\n",
      "upto 11 size 16 val 10\r\n",
      "upto 12 size 16 val 11\r\n",
      "upto 13 size 16 val 12\r\n",
      "upto 14 size 16 val 13\r\n",
      "upto 15 size 16 val 14\r\n",
      "upto 16 size 16 val 15\r\n",
      "upto 17 size 32 val 16\r\n",
      "upto 18 size 32 val 17\r\n",
      "upto 19 size 32 val 18\r\n",
      "upto 20 size 32 val 19\r\n",
      "upto 21 size 32 val 20\r\n",
      "upto 22 size 32 val 21\r\n",
      "upto 23 size 32 val 22\r\n",
      "upto 24 size 32 val 23\r\n",
      "upto 25 size 32 val 24\r\n",
      "upto 26 size 32 val 25\r\n",
      "upto 27 size 32 val 26\r\n",
      "upto 28 size 32 val 27\r\n",
      "upto 29 size 32 val 28\r\n",
      "upto 30 size 32 val 29\r\n",
      "upto 31 size 32 val 30\r\n",
      "upto 32 size 32 val 31\r\n",
      "upto 33 size 64 val 32\r\n",
      "upto 34 size 64 val 33\r\n",
      "upto 35 size 64 val 34\r\n",
      "upto 36 size 64 val 35\r\n",
      "upto 37 size 64 val 36\r\n",
      "upto 38 size 64 val 37\r\n",
      "upto 39 size 64 val 38\r\n",
      "upto 40 size 64 val 39\r\n",
      "upto 41 size 64 val 40\r\n",
      "upto 42 size 64 val 41\r\n",
      "upto 43 size 64 val 42\r\n",
      "upto 44 size 64 val 43\r\n",
      "upto 45 size 64 val 44\r\n",
      "upto 46 size 64 val 45\r\n",
      "upto 47 size 64 val 46\r\n",
      "upto 48 size 64 val 47\r\n",
      "upto 49 size 64 val 48\r\n",
      "upto 50 size 64 val 49\r\n",
      "upto 51 size 64 val 50\r\n",
      "upto 52 size 64 val 51\r\n",
      "upto 53 size 64 val 52\r\n",
      "upto 54 size 64 val 53\r\n",
      "upto 55 size 64 val 54\r\n",
      "upto 56 size 64 val 55\r\n",
      "upto 57 size 64 val 56\r\n",
      "upto 58 size 64 val 57\r\n",
      "upto 59 size 64 val 58\r\n",
      "upto 60 size 64 val 59\r\n",
      "upto 61 size 64 val 60\r\n",
      "upto 62 size 64 val 61\r\n",
      "upto 63 size 64 val 62\r\n",
      "upto 64 size 64 val 63\r\n",
      "upto 65 size 128 val 64\r\n",
      "upto 66 size 128 val 65\r\n",
      "upto 67 size 128 val 66\r\n",
      "upto 68 size 128 val 67\r\n",
      "upto 69 size 128 val 68\r\n",
      "upto 70 size 128 val 69\r\n",
      "upto 71 size 128 val 70\r\n",
      "upto 72 size 128 val 71\r\n",
      "upto 73 size 128 val 72\r\n",
      "upto 74 size 128 val 73\r\n",
      "upto 75 size 128 val 74\r\n",
      "upto 76 size 128 val 75\r\n",
      "upto 77 size 128 val 76\r\n",
      "upto 78 size 128 val 77\r\n",
      "upto 79 size 128 val 78\r\n",
      "upto 80 size 128 val 79\r\n",
      "upto 81 size 128 val 80\r\n",
      "upto 82 size 128 val 81\r\n",
      "upto 83 size 128 val 82\r\n",
      "upto 84 size 128 val 83\r\n",
      "upto 85 size 128 val 84\r\n",
      "upto 86 size 128 val 85\r\n",
      "upto 87 size 128 val 86\r\n",
      "upto 88 size 128 val 87\r\n",
      "upto 89 size 128 val 88\r\n",
      "upto 90 size 128 val 89\r\n",
      "upto 91 size 128 val 90\r\n",
      "upto 92 size 128 val 91\r\n",
      "upto 93 size 128 val 92\r\n",
      "upto 94 size 128 val 93\r\n",
      "upto 95 size 128 val 94\r\n",
      "upto 96 size 128 val 95\r\n",
      "upto 97 size 128 val 96\r\n",
      "upto 98 size 128 val 97\r\n",
      "upto 99 size 128 val 98\r\n",
      "upto 100 size 128 val 99\r\n",
      "upto 101 size 128 val 100\r\n",
      "upto 102 size 128 val 101\r\n",
      "upto 103 size 128 val 102\r\n",
      "upto 104 size 128 val 103\r\n",
      "upto 105 size 128 val 104\r\n",
      "upto 106 size 128 val 105\r\n",
      "upto 107 size 128 val 106\r\n",
      "upto 108 size 128 val 107\r\n",
      "upto 109 size 128 val 108\r\n",
      "upto 110 size 128 val 109\r\n",
      "upto 111 size 128 val 110\r\n",
      "upto 112 size 128 val 111\r\n",
      "upto 113 size 128 val 112\r\n",
      "upto 114 size 128 val 113\r\n",
      "upto 115 size 128 val 114\r\n",
      "upto 116 size 128 val 115\r\n",
      "upto 117 size 128 val 116\r\n",
      "upto 118 size 128 val 117\r\n",
      "upto 119 size 128 val 118\r\n",
      "upto 120 size 128 val 119\r\n",
      "upto 121 size 128 val 120\r\n",
      "upto 122 size 128 val 121\r\n",
      "upto 123 size 128 val 122\r\n",
      "upto 124 size 128 val 123\r\n",
      "upto 125 size 128 val 124\r\n",
      "upto 126 size 128 val 125\r\n",
      "upto 127 size 128 val 126\r\n",
      "upto 128 size 128 val 127\r\n",
      "upto 129 size 256 val 128\r\n",
      "upto 130 size 256 val 129\r\n",
      "upto 131 size 256 val 130\r\n",
      "upto 132 size 256 val 131\r\n",
      "upto 133 size 256 val 132\r\n",
      "upto 134 size 256 val 133\r\n",
      "upto 135 size 256 val 134\r\n",
      "upto 136 size 256 val 135\r\n",
      "upto 137 size 256 val 136\r\n",
      "upto 138 size 256 val 137\r\n",
      "upto 139 size 256 val 138\r\n",
      "upto 140 size 256 val 139\r\n",
      "upto 141 size 256 val 140\r\n",
      "upto 142 size 256 val 141\r\n",
      "upto 143 size 256 val 142\r\n",
      "upto 144 size 256 val 143\r\n",
      "upto 145 size 256 val 144\r\n",
      "upto 146 size 256 val 145\r\n",
      "upto 147 size 256 val 146\r\n",
      "upto 148 size 256 val 147\r\n",
      "upto 149 size 256 val 148\r\n",
      "upto 150 size 256 val 149\r\n",
      "upto 151 size 256 val 150\r\n",
      "upto 152 size 256 val 151\r\n",
      "upto 153 size 256 val 152\r\n",
      "upto 154 size 256 val 153\r\n",
      "upto 155 size 256 val 154\r\n",
      "upto 156 size 256 val 155\r\n",
      "upto 157 size 256 val 156\r\n",
      "upto 158 size 256 val 157\r\n",
      "upto 159 size 256 val 158\r\n",
      "upto 160 size 256 val 159\r\n",
      "upto 161 size 256 val 160\r\n",
      "upto 162 size 256 val 161\r\n",
      "upto 163 size 256 val 162\r\n",
      "upto 164 size 256 val 163\r\n",
      "upto 165 size 256 val 164\r\n",
      "upto 166 size 256 val 165\r\n",
      "upto 167 size 256 val 166\r\n",
      "upto 168 size 256 val 167\r\n",
      "upto 169 size 256 val 168\r\n",
      "upto 170 size 256 val 169\r\n",
      "upto 171 size 256 val 170\r\n",
      "upto 172 size 256 val 171\r\n",
      "upto 173 size 256 val 172\r\n",
      "upto 174 size 256 val 173\r\n",
      "upto 175 size 256 val 174\r\n",
      "upto 176 size 256 val 175\r\n",
      "upto 177 size 256 val 176\r\n",
      "upto 178 size 256 val 177\r\n",
      "upto 179 size 256 val 178\r\n",
      "upto 180 size 256 val 179\r\n",
      "upto 181 size 256 val 180\r\n",
      "upto 182 size 256 val 181\r\n",
      "upto 183 size 256 val 182\r\n",
      "upto 184 size 256 val 183\r\n",
      "upto 185 size 256 val 184\r\n",
      "upto 186 size 256 val 185\r\n",
      "upto 187 size 256 val 186\r\n",
      "upto 188 size 256 val 187\r\n",
      "upto 189 size 256 val 188\r\n",
      "upto 190 size 256 val 189\r\n",
      "upto 191 size 256 val 190\r\n",
      "upto 192 size 256 val 191\r\n",
      "upto 193 size 256 val 192\r\n",
      "upto 194 size 256 val 193\r\n",
      "upto 195 size 256 val 194\r\n",
      "upto 196 size 256 val 195\r\n",
      "upto 197 size 256 val 196\r\n",
      "upto 198 size 256 val 197\r\n",
      "upto 199 size 256 val 198\r\n",
      "upto 200 size 256 val 199\r\n",
      "i 185 val 186\r\n",
      "i 186 val 187\r\n",
      "i 187 val 188\r\n",
      "i 188 val 189\r\n",
      "i 189 val 190\r\n",
      "i 180 val 181 upto 199\r\n",
      "i 181 val 183 upto 198\r\n",
      "val 180 index -1\r\n",
      "val 181 index -1\r\n",
      "val 182 index 180\r\n",
      "val 183 index 181\r\n",
      "val 184 index 182\r\n",
      "val 185 index -1\r\n",
      "val 186 index 183\r\n",
      "val 187 index 184\r\n",
      "val 188 index 185\r\n",
      "val 189 index 186\r\n",
      "val 190 index 187\r\n",
      "val 191 index 189\r\n",
      "val 192 index 190\r\n",
      "val 193 index 191\r\n",
      "val 194 index 192\r\n"
     ]
    }
   ],
   "source": [
    "!./dademo2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copy the above output into the first answer on the google form. (http://goo.gl/forms/rH5he0YC44)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Linked List\n",
    "\n",
    "If we put all our code into one file, we dont need to write the header file, since we use our interfaces in the same file. This does not makefor code usable by others, but as we hae seen ealier, is useful for quick playing and testing.\n",
    "\n",
    "Provided below are parts of a partially implemented linked list in C. Implement the functions:\n",
    "\n",
    "- `int get_index(Item* listptr, int value)` which returns the index at which the value is found, and otherwise -1.\n",
    "- `Item* remove_item(Item* listptr, int value)`. Be careful to return NULL if the item with `value` was not in the list, and make sure that deletion repoints the pointer of the previous item to the next item."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Writing linked_list_incomplete.c\n"
     ]
    }
   ],
   "source": [
    "%%file linked_list_incomplete.c\n",
    "\n",
    "#include <stdlib.h>\n",
    "#include <stdio.h>\n",
    "\n",
    "typedef struct item {\n",
    "    int value;\n",
    "    struct item* rest;\n",
    "} Item;\n",
    "\n",
    "Item* new_item(int value){\n",
    "    Item* newitem = (Item *) malloc(sizeof(Item));\n",
    "    newitem->value = value;\n",
    "    newitem->rest = NULL;\n",
    "    return newitem;\n",
    "}\n",
    "\n",
    "Item* insert_front(Item* listptr, int value){\n",
    "    Item* newitem = new_item(value);\n",
    "    newitem->rest = listptr;\n",
    "    return newitem;\n",
    "}\n",
    "\n",
    "\n",
    "int get(Item* listptr, int index){\n",
    "    int ctr = 0;\n",
    "    Item* p;\n",
    "    for(p = listptr; p!= NULL; p = p->rest){\n",
    "        if (ctr==index){\n",
    "            return p->value;\n",
    "        }\n",
    "        ctr++;\n",
    "    }\n",
    "    return -1;\n",
    "}\n",
    "\n",
    "\n",
    "void free_all(Item* listptr) {\n",
    "    Item *p;\n",
    "    Item *next;\n",
    "    for(p = listptr; p!= NULL; p = next){\n",
    "        next = p->rest;\n",
    "        free(p);\n",
    "    }\n",
    "}\n",
    "\n",
    "int main(){\n",
    "    Item* listptr;\n",
    "    int i;\n",
    "    listptr = new_item(0);\n",
    "    for (i=1; i < 6; i++){\n",
    "        listptr=insert_front(listptr, i);\n",
    "    }\n",
    "    for (i=0; i < 6; i++){\n",
    "        printf(\"i %d Item %d\\n\", i, get(listptr, i));\n",
    "    }\n",
    "    listptr = remove_item(listptr, 3);\n",
    "    for (i=0; i <= 5; i++){\n",
    "        printf(\"i %d Item %d\\n\", i, get(listptr, i));\n",
    "    }\n",
    "    printf(\"Index for 3 %d\\n\", get_index(listptr, 3));\n",
    "    free_all(listptr);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Add the two functions and write your code here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting linked_list.c\n"
     ]
    }
   ],
   "source": [
    "%%file linked_list.c\n",
    "\n",
    "//your code here\n",
    "#include <stdlib.h>\n",
    "#include <stdio.h>\n",
    "\n",
    "typedef struct item {\n",
    "    int value;\n",
    "    struct item* rest;\n",
    "} Item;\n",
    "\n",
    "Item* new_item(int value){\n",
    "    Item* newitem = (Item *) malloc(sizeof(Item));\n",
    "    newitem->value = value;\n",
    "    newitem->rest = NULL;\n",
    "    return newitem;\n",
    "}\n",
    "\n",
    "Item* insert_front(Item* listptr, int value){\n",
    "    Item* newitem = new_item(value);\n",
    "    newitem->rest = listptr;\n",
    "    return newitem;\n",
    "}\n",
    "\n",
    "\n",
    "int get(Item* listptr, int index){\n",
    "    int ctr = 0;\n",
    "    Item* p;\n",
    "    for(p = listptr; p!= NULL; p = p->rest){\n",
    "        if (ctr==index){\n",
    "            return p->value;\n",
    "        }\n",
    "        ctr++;\n",
    "    }\n",
    "    return -1;\n",
    "}\n",
    "\n",
    "\n",
    "void free_all(Item* listptr) {\n",
    "    Item *p;\n",
    "    Item *next;\n",
    "    for(p = listptr; p!= NULL; p = next){\n",
    "        next = p->rest;\n",
    "        free(p);\n",
    "    }\n",
    "}\n",
    "\n",
    "int get_index(Item* listptr, int value) {\n",
    "    int ctr = 0;\n",
    "    Item* p;\n",
    "    for(p = listptr; p!= NULL; p = p->rest){\n",
    "        if (p->value==value){\n",
    "            return ctr;\n",
    "        }\n",
    "        ctr++;\n",
    "    }\n",
    "    return -1;\n",
    "}\n",
    "\n",
    "Item* remove_item(Item* listptr, int value) {\n",
    "    Item* prev = listptr;\n",
    "    Item* p = prev->rest;\n",
    "    if (prev->value==value) {\n",
    "        free(prev);\n",
    "        return p;\n",
    "    }\n",
    "    \n",
    "    for(p = p; p != NULL; p = p->rest){\n",
    "        if (p->value==value) {\n",
    "            prev->rest=p->rest;\n",
    "            free(p);\n",
    "            return listptr;\n",
    "        }\n",
    "        prev = p;\n",
    "    }\n",
    "    \n",
    "    return NULL;\n",
    "}\n",
    "\n",
    "int main(){\n",
    "    Item* listptr;\n",
    "    int i;\n",
    "    listptr = new_item(0);\n",
    "    for (i=1; i < 6; i++){\n",
    "        listptr=insert_front(listptr, i);\n",
    "    }\n",
    "    for (i=0; i < 6; i++){\n",
    "        printf(\"i %d Item %d\\n\", i, get(listptr, i));\n",
    "    }\n",
    "    listptr = remove_item(listptr, 3);\n",
    "    for (i=0; i <= 5; i++){\n",
    "        printf(\"i %d Item %d\\n\", i, get(listptr, i));\n",
    "    }\n",
    "    printf(\"Index for 3 %d\\n\", get_index(listptr, 3));\n",
    "    free_all(listptr);\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "!gcc -o linked_list -g linked_list.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i 0 Item 5\r\n",
      "i 1 Item 4\r\n",
      "i 2 Item 3\r\n",
      "i 3 Item 2\r\n",
      "i 4 Item 1\r\n",
      "i 5 Item 0\r\n",
      "i 0 Item 5\r\n",
      "i 1 Item 4\r\n",
      "i 2 Item 2\r\n",
      "i 3 Item 1\r\n",
      "i 4 Item 0\r\n",
      "i 5 Item -1\r\n",
      "Index for 3 -1\r\n"
     ]
    }
   ],
   "source": [
    "!./linked_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copy this output to the second answer on the google form. (http://goo.gl/forms/rH5he0YC44)"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}