{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Singly Linked List Implementation\n",
    "\n",
    "In this lecture we will implement a basic Singly Linked List.\n",
    "\n",
    "Remember, in a singly linked list, we have an ordered list of items as individual Nodes that have pointers to other Nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \n",
    "    def __init__(self,value):\n",
    "        \n",
    "        self.value = value\n",
    "        self.nextnode = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can build out Linked List with the collection of nodes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "a = Node(1)\n",
    "b = Node(2)\n",
    "c = Node(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a.nextnode = b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "b.nextnode = c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a Linked List the first node is called the **head** and the last node is called the **tail**. Let's discuss the pros and cons of Linked Lists:\n",
    "\n",
    "## Pros\n",
    "\n",
    "* Linked Lists have constant-time insertions and deletions in any position, in comparison, arrays require O(n) time to do the same thing.\n",
    "\n",
    "* Linked lists can continue to expand without having to specify their size ahead of time (remember our lectures on Array sizing form the Array Sequence section of the course!)\n",
    "\n",
    "## Cons\n",
    "\n",
    "* To access an element in a linked list, you need to take O(k) time to go from the head of the list to the kth element. In contrast, arrays have constant time operations to access elements in an array."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Good Job!\n",
    "\n",
    "That's it for the implementation (pretty simple right?). Up next we will learn about Doubly Linked Lists!"
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}