{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Linked Lists\n", "http://openbookproject.net/thinkcs/python/english3e/linked_lists.html\n", "\n", "## forward list\n", "- made up of nodes linked to each other such that a not contains a reference to the next node in the list\n", "- first node is often called head and last node is also called tail\n", "- each node also contains a data field also called cargo\n", "- recursive definition:\n", " - a linked list is either:\n", " 1. the empyt list, represented by None, or\n", " 2. a node that contains a cargo object and a reference to a linked list\n", "- this definition of linked-list is also called forward list or singly linked list as opposed to doubly linked list\n", "- drawbacks:\n", " - can't directly access nodes by their position as opposed to built-in data structure list\n", " - consume some extra memory to keep the linking information associated to each element (may be an important factor for large lists of small-sized elements)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Node class" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "class Node:\n", " def __init__(self, cargo=None, next=None):\n", " self.cargo = cargo\n", " self.next = next\n", " \n", " def __str__(self):\n", " return str(self.cargo)\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "test\n" ] } ], "source": [ "node = Node(\"test\")\n", "print(node)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "node1 = Node(1)\n", "node2 = Node(2)\n", "node3 = Node(3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## visualize with Pythontutor.com\n", "https://goo.gl/u1vePS" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.display import IFrame\n", "src = \"\"\"\n", "http://pythontutor.com/iframe-embed.html#code=class%20Node%3A%0A%20%20%20%20def%20__init__%28self,%20cargo%3DNone,%20next%3DNone%29%3A%0A%20%20%20%20%20%20%20%20self.cargo%20%3D%20cargo%0A%20%20%20%20%20%20%20%20self.next%20%3D%20next%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20def%20__str__%28self%29%3A%0A%20%20%20%20%20%20%20%20return%20str%28self.cargo%29%0A%20%20%20%20%20%20%20%20%0Anode1%20%3D%20Node%281%29%0Anode2%20%3D%20Node%282%29%0Anode3%20%3D%20Node%283%29%0A&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=16&heapPrimitives=false&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\n", "\"\"\"\n", "IFrame(src, width=900, height=600)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### link the nodes to form linked list" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "node1.next = node2\n", "node2.next = node3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### visualize the linked-list with pythontutor\n", "https://goo.gl/tNhz4a" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.display import IFrame\n", "src = \"\"\"\n", "http://pythontutor.com/iframe-embed.html#code=class%20Node%3A%0A%20%20%20%20def%20__init__%28self,%20cargo%3DNone,%20next%3DNone%29%3A%0A%20%20%20%20%20%20%20%20self.cargo%20%3D%20cargo%0A%20%20%20%20%20%20%20%20self.next%20%3D%20next%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20def%20__str__%28self%29%3A%0A%20%20%20%20%20%20%20%20return%20str%28self.cargo%29%0A%20%20%20%20%20%20%20%20%0Anode1%20%3D%20Node%281%29%0Anode2%20%3D%20Node%282%29%0Anode3%20%3D%20Node%283%29%0A%0Anode1.next%20%3D%20node2%0Anode2.next%20%3D%20node3&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=16&heapPrimitives=false&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\n", "\"\"\"\n", "IFrame(src, width=900, height=700)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### list as collection\n", "- first node, node1 of the list serves as a reference to the entire list; also called root/first node\n", "- to pass list as a parameter, we only have to pass a reference to the first node" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "def print_list(node):\n", " while node is not None:\n", " print(node, end=\" \")\n", " node = node.next\n", " print()" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 2 3 \n" ] } ], "source": [ "print_list(node1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Lists and recursion\n", "- because of recursive definition, it naturally lends to many recursive operations\n", "- print list backward\n", " 1. General case:\n", " 1. separate the lists into two pieces: the first node (head) and the rest (tail)\n", " 2. recursive print the tail\n", " 3. print the head\n", " " ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "def print_backward(alist):\n", " if alist is None:\n", " return\n", " head = alist\n", " tail = alist.next\n", " print_backward(tail)\n", " print(head, end=\" \")" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3 1 " ] } ], "source": [ "print_backward(node1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Modifying lists\n", "- change cargo/data of a node\n", "- add a new node\n", "- delete an existing node\n", "- re-order nodes" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "# function that removes the second node in the list and returns reference to the removed node\n", "def remove_second(alist):\n", " if alist is None: return\n", " first = alist\n", " second = alist.next\n", " # Make the first node point to the third\n", " first.next = second.next\n", " # Separate the second node from the rest of the list\n", " second.next = None\n", " return second" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 2 3 \n" ] } ], "source": [ "print_list(node1)" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "removed = remove_second(node1)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2\n" ] } ], "source": [ "print(removed)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 3 \n" ] } ], "source": [ "print_list(node1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## wrappers and helpers" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": [ "def print_backward_nicely(alist):\n", " print(\"[\", end=\" \")\n", " print_backward(alist)\n", " print(\"]\")" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 3 1 ]\n" ] } ], "source": [ "print_backward_nicely(node1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## LinkedList container class\n", "### better approach\n", "- define LinkeList class that keeps track of all the meta-data and methods to work with linked lists such as traversing and printing, adding, deleting, etc." ] }, { "cell_type": "code", "execution_count": 88, "metadata": {}, "outputs": [], "source": [ "class LinkedList(object):\n", " def __init__(self):\n", " self.length = 0\n", " self.head = None\n", " self.tail = None\n", " \n", " def append(self, data):\n", " node = Node(data)\n", " if not self.head: # empty linked list\n", " # make the first and last point to the new node\n", " self.head = node\n", " self.tail = node\n", " else:\n", " self.tail.next = node # make the current tail's next node point to the new node\n", " self.tail = node # node is the last node\n", " self.length += 1\n", " \n", " def __str__(self):\n", " \"\"\"\n", " traverse linked list and return all the cargos/data\n", " \"\"\"\n", " llist = list()\n", " current = self.head\n", " while current:\n", " llist.append(current.cargo)\n", " current = current.next\n", " return str(llist)\n", " \n", " def print(self):\n", " current = self.head\n", " while current is not None:\n", " print(current, end=\" \")\n", " current = current.next\n", " print()\n", " \n", " def print_reverse(self):\n", " current = self.head\n", " if not current:\n", " return\n", " print_backward(current.next)\n", " print(current, end=\" \")\n", " \n", " def find(self, data):\n", " # find and return the node with given data\n", " current = self.head\n", " found = False\n", " while (current and not found):\n", " if current.cargo == data:\n", " found = True\n", " else:\n", " current = current.next\n", " return current\n", " \n", " \n", " def remove(self, data):\n", " \"\"\"\n", " We need to consider several cases:\n", " Case 1: the list is empty - do nothing\n", " Case 2: The first node is the node with the given cargo/data, we need to adjust head and may be tail\n", " Case 3: The node with the given info is somewhere in the list. \n", " i. find the node and delete\n", " ii. If the node to be deleted is the tail,\n", " we must adjust tail.\n", " Case 4: The list doesn't contain a node with the given info - do nothing\n", " \"\"\"\n", " # case 1\n", " if not self.head:\n", " return # done\n", " # case 2\n", " if self.head.cargo == data:\n", " self.head = self.head.next # 2nd node becomes the head\n", " # if list becomes empty; update tail as well\n", " if not self.head:\n", " self.tail = None\n", " self.length -= 1\n", " else:\n", " # search the list for the node with given data\n", " found = False\n", " trailCurrent = self.head # first node\n", " current = self.head.next # second node\n", " while(current and not found):\n", " if current.cargo == data:\n", " found = True\n", " else:\n", " trailCurrent = current\n", " current = current.next\n", " if found: #case 3\n", " trailCurrent.next = current.next\n", " if self.tail is current:\n", " self.tail = trailCurrent\n", " self.length -= 1\n", " else: # case 4\n", " return\n", " \n", " def clear(self):\n", " self.length = 0\n", " self.head = None\n", " self.tail = None\n", " \n", " def __len__(self):\n", " return self.length" ] }, { "cell_type": "code", "execution_count": 89, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[10, 5, 15, 'a', 'ball'] 5\n" ] } ], "source": [ "alist = LinkedList()\n", "alist.append(10)\n", "alist.append(5)\n", "alist.append(15)\n", "alist.append('a')\n", "alist.append('ball')\n", "print(alist, len(alist))" ] }, { "cell_type": "code", "execution_count": 90, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[10, 5, 'a', 'ball']\n", "4\n" ] } ], "source": [ "alist.remove(15)\n", "print(alist)\n", "print(len(alist))" ] }, { "cell_type": "code", "execution_count": 91, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[5, 'a', 'ball']\n" ] } ], "source": [ "alist.remove(10)\n", "print(alist)" ] }, { "cell_type": "code", "execution_count": 92, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[5, 'a']\n" ] } ], "source": [ "alist.remove('ball')\n", "print(alist)" ] }, { "cell_type": "code", "execution_count": 93, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[5, 'a', 'cat']\n" ] } ], "source": [ "alist.append('cat')\n", "print(alist)\n", "assert len(alist) == alist.length" ] }, { "cell_type": "code", "execution_count": 94, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n" ] } ], "source": [ "print(alist.length)" ] }, { "cell_type": "code", "execution_count": 95, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "cat a 5 " ] } ], "source": [ "alist.print_reverse()" ] }, { "cell_type": "code", "execution_count": 96, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5 a cat \n" ] } ], "source": [ "alist.print()" ] }, { "cell_type": "code", "execution_count": 97, "metadata": {}, "outputs": [], "source": [ "node = alist.find('cat')" ] }, { "cell_type": "code", "execution_count": 98, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "cat\n" ] } ], "source": [ "print(node)" ] }, { "cell_type": "code", "execution_count": 99, "metadata": {}, "outputs": [], "source": [ "node.cargo = 'Cat'" ] }, { "cell_type": "code", "execution_count": 100, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5 a Cat \n" ] } ], "source": [ "alist.print()" ] }, { "cell_type": "code", "execution_count": 102, "metadata": {}, "outputs": [], "source": [ "alist.remove('dog')" ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5 a Cat \n" ] } ], "source": [ "alist.print()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## exercises\n", "\n", "1. By convention, lists are often printed in brackets with commas between the elements, as in [1, 2, 3]. Modify print_list function so that it generates output in this format." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2. By convention, lists are often printed in brackets with commas between the elements, as in [1, 2, 3]. Modify print method of LinkeList class so that it generates output in this format." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "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.6.2" } }, "nbformat": 4, "nbformat_minor": 2 }