Skip to content

Instantly share code, notes, and snippets.

@guocheng

guocheng/Python LinkedList.ipynb

Created June 29, 2019 13:55
Show Gist options
  • Save guocheng/88e2b76c25a60ccf9ebc17ecb30ae967 to your computer and use it in GitHub Desktop.
Save guocheng/88e2b76c25a60ccf9ebc17ecb30ae967 to your computer and use it in GitHub Desktop.
Download ZIP
Python implementation of LinkedList
Display the source blob
Display the rendered blob
Raw
Python LinkedList.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Array vs LinkedList\n",
"\n",
"1. When array is initialized, it is allocated with a fixed size. LinkedList only has a head to begin with.\n",
"2. Array is fixed in size (you can grow it but it is an O(n) operation) but LinkedList can be infinitely long.\n",
"3. Insertion using LinkedList is O(1), and array is O(n) (because everything after the insertion point has to shift to the right)\n",
"4. Deletion with LinkedList is O(1), and array is O(n)\n",
"5. Random access with LinkedList is O(n), but it is O(1) for array\n",
"\n",
"\n",
"For point 3 & 4 above:\n",
"The actually operation of insertion and deletion is O(1) for LinkedList, but to get to the place of insertion or deletion is O(n).\n",
"\n",
"Reference:\n",
"https://stackoverflow.com/questions/393556/when-to-use-a-linked-list-over-an-array-array-list"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import random"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"class Node(object):\n",
" def __init__(self, data):\n",
" self.data = data\n",
" self.next = None\n",
" \n",
" @property\n",
" def data(self):\n",
" return self._data\n",
" \n",
" @data.setter\n",
" def data(self, data):\n",
" self._data = data\n",
" \n",
" @property\n",
" def next(self):\n",
" return self._next\n",
" \n",
" @next.setter\n",
" def next(self, next):\n",
" self._next = next\n",
" \n",
" def __str__(self):\n",
" return f'data: {self._data} next: {self._next}'\n",
" \n",
" def __eq__(self, other):\n",
" return (self.data == other.data) and (self.next is other.next)"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [],
"source": [
"class LinkedList(object):\n",
" def __init__(self):\n",
" self.head = None\n",
" \n",
" @property\n",
" def head(self):\n",
" return self._head\n",
" \n",
" @head.setter\n",
" def head(self, node: Node) -> Node:\n",
" self._head = node\n",
" \n",
" def push(self, node_value: int) -> None:\n",
" \"\"\"\n",
" Push to the beginning of the LinkedList\n",
" \"\"\"\n",
" new_node = Node(node_value)\n",
" new_node.next = self.head\n",
" self.head = new_node\n",
" \n",
" def append(self, node_value: int) -> None:\n",
" \"\"\"\n",
" Append to the end of the LinkedList\n",
" \"\"\"\n",
" if self.head is None:\n",
" self.head = Node(node_value)\n",
"\n",
" else:\n",
" last_node = self.head\n",
" while last_node.next:\n",
" last_node = last_node.next\n",
" last_node.next = Node(node_value)\n",
" \n",
" def reverse(self) -> None:\n",
" \"\"\"\n",
" Reverse the order the LinkedList\n",
" \"\"\"\n",
" prev = None\n",
" cur = self.head\n",
" while cur:\n",
" next = cur.next\n",
" cur.next = prev\n",
" prev = cur\n",
" cur = next\n",
" self.head = prev\n",
" \n",
" def recursive_reverse(self, cur_node: Node, prev_node: Node) -> None:\n",
" if cur_node is None:\n",
" self.head = prev_node\n",
" return \n",
" \n",
" next = cur_node.next\n",
" cur_node.next = prev_node \n",
" self.recursive_reverse(next, cur_node)\n",
" \n",
" \n",
" def recursive_reverse_2(self, node: Node) -> None:\n",
" cur = node.next\n",
" if cur is None:\n",
" self.head = node\n",
" return\n",
" self.recursive_reverse_2(cur)\n",
" cur.next = node\n",
" node.next = None\n",
"\n",
" def __getitem__(self, at: int) -> Node:\n",
" \"\"\"\n",
" Support for [] access\n",
" \"\"\"\n",
" if self.is_empty():\n",
" raise IndexError('Index out of range') \n",
" \n",
" if at >= 0:\n",
" return self.get(at)\n",
" else:\n",
" length = self.__len__()\n",
" pos = length + at\n",
" if pos < 0:\n",
" raise IndexError('Index out of range')\n",
" return self.get(pos)\n",
" \n",
" def get(self, at: int) -> Node:\n",
" \"\"\"\n",
" Get value at a specified position\n",
" \"\"\"\n",
" i = self.head\n",
" counter = 0\n",
" while i:\n",
" if counter == at:\n",
" return i\n",
" counter += 1\n",
" i = i.next\n",
" if at >= counter:\n",
" raise IndexError('Index out of range')\n",
" \n",
" def search(self, value: int) -> bool:\n",
" \"\"\"\n",
" Find an item within the LinkedList\n",
" \"\"\"\n",
" i = self.head\n",
" while i is not None:\n",
" if i.data == value:\n",
" return True\n",
" i = i.next\n",
" return False\n",
" \n",
" def recursive_search(self, start_node: Node, n: int) -> None:\n",
" \"\"\"\n",
" Recursive version of search\n",
" \"\"\"\n",
" if start_node is None: \n",
" return False\n",
" \n",
" if start_node.data == n:\n",
" return True\n",
" \n",
" return self.recursive_search(start_node.next, n)\n",
" \n",
" def delete(self, value: int) -> None:\n",
" \"\"\"\n",
" Delete an item from the LinkedList\n",
" \"\"\"\n",
" i = self.head\n",
" while i is not None:\n",
" if i.data == value:\n",
" if i is self.head:\n",
" self.head = i.next\n",
" else:\n",
" prev.next = i.next\n",
" return\n",
" prev = i\n",
" i = i.next\n",
" raise ValueError('LinkedList.delete(value): value is not in list')\n",
" \n",
" def is_empty(self) -> bool:\n",
" return self.head is None\n",
" \n",
" def __len__(self) -> int:\n",
" i = self.head\n",
" counter = 0\n",
" while i is not None:\n",
" counter += 1\n",
" i = i.next\n",
" return counter\n",
" \n",
" def __str__(self) -> str:\n",
" if self.is_empty():\n",
" return '[]'\n",
" else:\n",
" r = []\n",
" i = self.head\n",
" while i is not None:\n",
" r.append(str(i.data))\n",
" i = i.next\n",
" return '[' + ', '.join(r) + ']'"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"............\n",
"----------------------------------------------------------------------\n",
"Ran 12 tests in 0.010s\n",
"\n",
"OK\n"
]
}
],
"source": [
"import unittest\n",
"from random import randint\n",
"\n",
"class TestLinkedList(unittest.TestCase):\n",
" \"\"\"\n",
" Test Cases for testing the LinkedList Class\n",
" \"\"\"\n",
" \n",
" def setUp(self):\n",
" self.l = LinkedList()\n",
" \n",
" def tearDown(self):\n",
" del self.l\n",
" \n",
" def test_append(self):\n",
" self.l.append(5)\n",
" self.l.append(6)\n",
" self.assertEqual(self.l[0].data, 5, 'append 5')\n",
" self.assertIs(self.l[0].next, self.l[1], 'Identity not equal')\n",
" \n",
" def test_reverse(self):\n",
" for i in range(10):\n",
" self.l.append(i)\n",
" \n",
" self.l.reverse()\n",
" for i in range(10):\n",
" self.assertEqual(self.l[i].data, 9-i, 'reverse does not equal')\n",
" \n",
" self.l.recursive_reverse(self.l.head, None)\n",
" for i in range(10):\n",
" self.assertEqual(self.l[i].data, i)\n",
" \n",
" \n",
" def test_reverse_2(self):\n",
" for i in range(10):\n",
" self.l.append(i)\n",
" \n",
" self.l.recursive_reverse_2(self.l.head)\n",
" for i in range(10):\n",
" self.assertEqual(self.l[i].data, 9-i)\n",
" \n",
" def test_is_empty(self):\n",
" self.l.append(5)\n",
" self.assertEqual(self.l.is_empty(), False)\n",
" \n",
" def test_get(self):\n",
" for i in range(5):\n",
" self.l.append(i)\n",
" \n",
" self.assertEqual(self.l.get(3).data, 3)\n",
" self.assertEqual(self.l[4].data, 4)\n",
" \n",
" def test_search(self):\n",
" self.l.append(5)\n",
" self.assertEqual(self.l.search(5), True)\n",
" self.assertEqual(self.l.search(6), False)\n",
" \n",
" \n",
" def test_len(self):\n",
" length = randint(1,50)\n",
" for i in range(length):\n",
" self.l.append(i)\n",
" \n",
" self.assertEqual(len(self.l), length)\n",
" \n",
" \n",
" def test_push(self):\n",
" self.l.push(5)\n",
" self.l.push(6)\n",
" self.assertEqual(self.l.head.data, 6)\n",
" \n",
" \n",
" def test_delete_from_head(self):\n",
" for i in range(5):\n",
" self.l.append(i) \n",
" self.l.delete(0)\n",
" self.assertEqual(self.l.head.data, 1)\n",
" self.assertEqual(self.l.head.next.data, 2)\n",
" self.assertEqual(len(self.l), 4)\n",
" \n",
" \n",
" def test_delete_from_tail(self):\n",
" for i in range(5):\n",
" self.l.append(i) \n",
" self.l.delete(4)\n",
" self.assertEqual(self.l[-1].data, 3)\n",
" self.assertIsNone(self.l[-1].next)\n",
" \n",
" def test_delete_from_middle(self):\n",
" for i in range(5):\n",
" self.l.append(i) \n",
" self.l.delete(2)\n",
" self.assertEqual(self.l[2].data, 3)\n",
" self.assertEqual(self.l[2].next.data, 4)\n",
" \n",
" def test_node_equality(self):\n",
" n = Node(7)\n",
" a = Node(5)\n",
" a.next = n\n",
" b = Node(5)\n",
" b.next = n\n",
" self.assertEqual(a,b)\n",
" \n",
" \n",
"if __name__ == '__main__':\n",
" unittest.main(argv=['first-arg-is-ignored'], exit=False)"
]
}
],
"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.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment