linked_list.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked lists (single)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The Node class\n",
    "\n",
    "The Node class provides with the purest implementation of inserting and deleting nodes in a singly linked list, i.e. the manipulation of the pointers. \n",
    "\n",
    "As such, both functions are **`O(1)`**. In contrast access costs **`O(n)`**. This is the opposite behaviour of an array list implementation, where accessing was `O(1)` and inserting/deleting was `O(n)`. However there is an advantage with linked lists: For example, stacks and queues support insertion and deletion at the head and at the end of the list and linked lists can do that faster than array lists. This is because access can be provided to this specific positions by use of the `head` and `tail` pointers in `O(1)` and there is no need of copying around values like in array lists.\n",
    "\n",
    "Note that it is easier to insert _after_ rather than _before_ a given node because you do not have a pointer to its previous node, as you would in a doubly linked list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,val):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "    \n",
    "    def insert_after(self,head,node): #insert given node after this node\n",
    "        assert(head!=None and node!=None), \"Null head or null object cannot be inserted\"\n",
    "        node.next = self.next\n",
    "        self.next = node\n",
    "        return head\n",
    "    \n",
    "    def delete_after(self): #delete the node after this node\n",
    "        temp = self.next\n",
    "        self.next = self.next.next\n",
    "        return temp.val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The List class\n",
    "\n",
    "A List class that holds a reference to the first node (the head) and the size of the linked list.\n",
    "\n",
    "It implements the usual high level list interface.\n",
    "\n",
    "All functions are now **O(n)**, as they need to traverse the list up to the given index. They then leverage the low level functions that are particular to the linked list implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.size = 0\n",
    "        self.head = None\n",
    "        self.tail = None #helper pointer to optimise append\n",
    "        \n",
    "    def insert(self,val,index):\n",
    "        assert(index>=0 and index<=self.size), \"index out of bounds\"\n",
    "        node = Node(val)\n",
    "        if index==0: #if inserting at the start, the head needs to change\n",
    "            if self.head!=None: node.next=self.head\n",
    "            else: self.tail = node\n",
    "            self.head = node \n",
    "        else:\n",
    "            if index==self.size: #if inserting at the end, the tail need to change\n",
    "                after = self.tail\n",
    "                self.head = after.insert_after(self.head,node)\n",
    "                self.tail=node\n",
    "            else:\n",
    "                itertr = self.access_previous(index)\n",
    "                self.head = itertr.insert_after(self.head,node)\n",
    "        self.size = self.size+1\n",
    "    \n",
    "    def delete(self,index):\n",
    "        assert(index>=0 and index<=self.size), \"index out of bounds\"\n",
    "        assert (self.size>0), \"nothing to delete\"\n",
    "        if index==0: #again treat deletion of first node as a special case \n",
    "            delval=self.head.val\n",
    "            self.head = self.head.next\n",
    "            self.size -= 1\n",
    "        else:\n",
    "            itertr = self.access_previous(index)\n",
    "            delval=itertr.delete_after()   \n",
    "            self.size -= 1\n",
    "        return delval\n",
    "    \n",
    "    def access_previous(self, index):\n",
    "        assert(index>=0 and index<=self.size), \"index out of bounds\"\n",
    "        itertr = self.head\n",
    "        for i in range(index-1): itertr=itertr.next \n",
    "        return itertr\n",
    "    \n",
    "    def search(self,value):\n",
    "        node = self.head\n",
    "        i=0\n",
    "        while node != None:\n",
    "            if node.val == value: return i\n",
    "            node=node.next\n",
    "            i=i+1\n",
    "        return False\n",
    "        \n",
    "    def append(self, value):\n",
    "        self.insert(value, self.size)\n",
    "        \n",
    "    def clear(self):\n",
    "        self.size = 0\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "    \n",
    "    def print_list(self):\n",
    "        node = self.head \n",
    "        i=0\n",
    "        while node != None:\n",
    "            print node.val, \"\", \n",
    "            node = node.next \n",
    "            i += 1\n",
    "        print \"size=\", self.size"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**`access_previous():`** Because inserting and deleting happen through the reference from the previous node (`insert_after()` and `delete_after()`), we need a function that gets hold of the previous node. So for example `accessPrevious(index=5)` returns node @ index=4. `access_previous(index=0)` will still return the `head` as there is no previous. `insert()` is handling inserting @ index=0 as a special case, without calling `access_previous()`.\n",
    "\n",
    "**`insert()`** uses `access_previous()` to get a reference to the previous node and subsequently calls `Node`'s `insert_after()` to insert it right there. Inserting at the beginning is handled as a special case as descibed above. `delete()` works the same way. Note that `insert()` accepts a value and creates the node to be added."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  1  2  3  4  5  size= 6\n"
     ]
    }
   ],
   "source": [
    "#Create a list\n",
    "alist = MyLinkedList()\n",
    "for i in range(6):\n",
    "    alist.insert(i,i)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  10  1  2  3  4  5  size= 7\n"
     ]
    }
   ],
   "source": [
    "#insert in the middle\n",
    "alist.insert(10,1)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99  0  10  1  2  3  4  5  900  size= 9\n"
     ]
    }
   ],
   "source": [
    "#insert at the beggining\n",
    "alist.insert(99,0)\n",
    "alist.append(900)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#search for values that exist\n",
    "alist.search(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99  0  1  2  3  4  5  900  size= 8\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "#delete in the middle\n",
    "a=alist.delete(2)\n",
    "alist.print_list()\n",
    "print a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99  0  1  2  3  4  5  900  60  size= 9\n"
     ]
    }
   ],
   "source": [
    "#insert at the end\n",
    "alist.append(60)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#search for values that do not exist\n",
    "alist.search(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  1  2  3  4  5  900  60  size= 8\n"
     ]
    }
   ],
   "source": [
    "#delete the first node\n",
    "alist.delete(0)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  1  2  3  4  5  900  size= 7\n"
     ]
    }
   ],
   "source": [
    "#delete at the end\n",
    "#delete the first node\n",
    "alist.delete(alist.size-1)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "#access nodes\n",
    "print alist.access_previous(3).val\n",
    "print alist.access_previous(3).next.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}