{
"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
}