Skip to content

Instantly share code, notes, and snippets.

@travishen

travishen/linked-list-python.ipynb

Last active June 21, 2020 05:10
Show Gist options
  • Save travishen/df37a04582c48d386781077742908107 to your computer and use it in GitHub Desktop.
Save travishen/df37a04582c48d386781077742908107 to your computer and use it in GitHub Desktop.
Download ZIP
Linked list, double linked list implements using Python
Display the source blob
Display the rendered blob
Raw
linked-list-python.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from collections import Iterable\n",
"\n",
"class Node:\n",
" def __init__(self, data=None, next_node=None):\n",
" self.data = data\n",
" self.next_node = next_node\n",
" \n",
" def __repr__(self):\n",
" return 'Node(data={!r}, next_node={!r})'.format(self.data, self.next_node)\n",
"\n",
"class LinkedList(object):\n",
" def __init__(self, inital_nodes=None):\n",
" self.head = None\n",
" self.inital_nodes = inital_nodes\n",
" # garbage collect\n",
" for node in self:\n",
" del node\n",
" if isinstance(inital_nodes, Iterable):\n",
" for node in reversed(list(inital_nodes)):\n",
" self.insert(node) # insert to head\n",
" elif inital_nodes:\n",
" raise NotImplementedError('Inital with not iterable object')\n",
" \n",
" def __repr__(self):\n",
" return 'LinkedList(inital_nodes={!r})'.format(self.inital_nodes)\n",
" \n",
" def __len__(self): \n",
" count = 0\n",
" for node in self:\n",
" count += 1\n",
" return count\n",
" \n",
" def __setitem__(self, index, data):\n",
" self.insert(data, index)\n",
" \n",
" def __delitem__(self, index):\n",
" self.remove(index, by='index')\n",
" \n",
" def __getitem__(self, index):\n",
" count = 0\n",
" current = self.head\n",
" index = self.positive_index(index)\n",
" while count < index and current is not None:\n",
" current = current.next_node\n",
" count += 1\n",
" if current:\n",
" return current\n",
" else:\n",
" raise IndexError\n",
" \n",
" def middle(self):\n",
" slow_cursor = self.head\n",
" fast_cursor = self.head\n",
" \n",
" while fast_cursor.next_node and fast_cursor.next_node.next_node:\n",
" slow_cursor = slow_cursor.next_node\n",
" fast_cursor = fast_cursor.next_node.next_node\n",
" \n",
" return slow_cursor\n",
" \n",
" def reverse(self):\n",
" current_node = self.head\n",
" prev_node = None\n",
" next_node = None\n",
" \n",
" while current_node is not None:\n",
" next_node = current_node.next_node\n",
" current_node.next_node = prev_node\n",
" prev_node = current_node\n",
" current_node = next_node\n",
" \n",
" self.head = prev_node\n",
" \n",
" def positive_index(self, index): # inplement negative indexing\n",
" \"\"\"\n",
" Use nagative indexing will increase O(N) time complexity\n",
" We can improve it with double linded list\n",
" \"\"\"\n",
" if index < 0: \n",
" index = len(self) + index\n",
" return index\n",
" \n",
" def insert(self, data, index=0):\n",
" index = self.positive_index(index) \n",
" if self.head is None: # initial \n",
" self.head = Node(data, None)\n",
" elif index == 0: # insert to head\n",
" new_node = Node(data, self.head)\n",
" self.head = new_node\n",
" else: # insert to lst[index]\n",
" last_node = self[index]\n",
" last_node.next_node = Node(data, last_node.next_node) \n",
" return None # this instance has changed and didn't create instance\n",
" \n",
" def search(self, data):\n",
" for node in self:\n",
" if node.data == data:\n",
" return node\n",
" return None\n",
" \n",
" def remove(self, data_or_index, by='data'):\n",
" for i, node in enumerate(self):\n",
" if (by == 'data' and node.data == data_or_index) or (by == 'index' and i == data_or_index):\n",
" if i == 0:\n",
" self.head = node.next_node\n",
" node.next_node = None\n",
" else:\n",
" prev_node.next_node = node.next_node\n",
" break \n",
" prev_node = node\n",
" return None # this instance has changed and didn't create instance"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"LinkedList(inital_nodes=['A', ['B'], ('C',), {'D'}])"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"initial_nodes = ['A', ['B'], ('C',), {'D'}]\n",
"l = LinkedList(initial_nodes)\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# get length\n",
"len(l)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='A', next_node=Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=None))))\n",
"Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=None)))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=None))\n",
"Node(data={'D'}, next_node=None)\n"
]
}
],
"source": [
"# iter through LinkedList instance\n",
"for node in l:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='Z', next_node=Node(data='A', next_node=Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=None)))))\n",
"Node(data='A', next_node=Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=None))))\n",
"Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=None)))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=None))\n",
"Node(data={'D'}, next_node=None)\n"
]
}
],
"source": [
"# insert to head\n",
"l.insert('Z')\n",
"for node in l:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='Z', next_node=Node(data='A', next_node=Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None))))))\n",
"Node(data='A', next_node=Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))))\n",
"Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None))))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))\n",
"Node(data={'D'}, next_node=Node(data='E', next_node=None))\n",
"Node(data='E', next_node=None)\n"
]
}
],
"source": [
"# insert to foot\n",
"l.insert('E', index=-1)\n",
"for node in l:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# search by data\n",
"l.search(('C',))"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='Z', next_node=Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))))\n",
"Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None))))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))\n",
"Node(data={'D'}, next_node=Node(data='E', next_node=None))\n",
"Node(data='E', next_node=None)\n"
]
}
],
"source": [
"# remove by data\n",
"l.remove(['B'])\n",
"for node in l:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='Z', next_node=Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))))\n",
"Node(data='E', next_node=None)\n"
]
}
],
"source": [
"# __getitem__\n",
"print(l[0])\n",
"print(l[-1])"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None))))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))\n",
"Node(data={'D'}, next_node=Node(data='E', next_node=None))\n",
"Node(data='E', next_node=None)\n"
]
}
],
"source": [
"# __delitem__\n",
"del l[0]\n",
"for node in l:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='Z', next_node=Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))))\n",
"Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None))))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))\n",
"Node(data={'D'}, next_node=Node(data='E', next_node=None))\n",
"Node(data='E', next_node=None)\n"
]
}
],
"source": [
"# __setitem__\n",
"l[0] = 'Z'\n",
"for node in l:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# find middle node\n",
"l.middle()"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='E', next_node=Node(data={'D'}, next_node=Node(data=('C',), next_node=Node(data='A', next_node=Node(data='Z', next_node=None)))))\n",
"Node(data={'D'}, next_node=Node(data=('C',), next_node=Node(data='A', next_node=Node(data='Z', next_node=None))))\n",
"Node(data=('C',), next_node=Node(data='A', next_node=Node(data='Z', next_node=None)))\n",
"Node(data='A', next_node=Node(data='Z', next_node=None))\n",
"Node(data='Z', next_node=None)\n"
]
}
],
"source": [
"# reverse\n",
"l.reverse()\n",
"for n in l:\n",
" print(n)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"class DoubleLinkedNode(Node):\n",
" def __init__(self, data=None, last_node=None, next_node=None):\n",
" self.data = data\n",
" self.next_node = next_node\n",
" self.last_node = last_node\n",
" if next_node:\n",
" next_node.last_node = self\n",
" \n",
" \n",
"class DoubleLinkedList(LinkedList):\n",
" def __init__(self, *args, **kwargs):\n",
" self.foot = None\n",
" super(DoubleLinkedList, self).__init__(*args, **kwargs) \n",
" \n",
" def __repr__(self):\n",
" return 'DoubleLinkedList(inital_nodes={})'.format(self.inital_nodes)\n",
" \n",
" def __getitem__(self, index):\n",
" \"\"\"\n",
" Support negative indexing in O(N) by setting footer\n",
" \"\"\"\n",
" count = 0\n",
" if index >= 0:\n",
" current = self.head\n",
" while count < index and current is not None:\n",
" current = current.next_node\n",
" count += 1\n",
" else:\n",
" current = self.foot\n",
" while count > (index + 1) and current is not None:\n",
" current = current.last_node\n",
" count -= 1\n",
" if current:\n",
" return current\n",
" else:\n",
" raise IndexError\n",
" \n",
" def insert(self, data, index=0):\n",
" if self.head is None: # initial \n",
" self.head = self.foot = DoubleLinkedNode(data, None, None)\n",
" elif index == 0: # insert to head\n",
" new_node = DoubleLinkedNode(data, None, self.head)\n",
" self.head = new_node\n",
" else: # insert to lst[index]\n",
" last_node = self[index]\n",
" last_node.next_node = DoubleLinkedNode(data, last_node, last_node.next_node) \n",
" if last_node.next_node.next_node is None: # set foot\n",
" self.foot = last_node.next_node\n",
" return None # this instance has changed and didn't create instance"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"DoubleLinkedList(inital_nodes=['A', ['B'], ('C',), {'D'}])"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"initial_nodes = ['A', ['B'], ('C',), {'D'}]\n",
"dl = DoubleLinkedList(initial_nodes)\n",
"dl"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(dl)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='A', next_node=Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=None))))\n",
"Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=None)))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=None))\n",
"Node(data={'D'}, next_node=None)\n"
]
}
],
"source": [
"# iter through DoubleLinkedList instance\n",
"for node in dl:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='Z', next_node=Node(data='A', next_node=Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=None)))))\n",
"Node(data='A', next_node=Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=None))))\n",
"Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=None)))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=None))\n",
"Node(data={'D'}, next_node=None)\n"
]
}
],
"source": [
"# insert to head\n",
"dl.insert('Z')\n",
"for node in dl:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='Z', next_node=Node(data='A', next_node=Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None))))))\n",
"Node(data='A', next_node=Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))))\n",
"Node(data=['B'], next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None))))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))\n",
"Node(data={'D'}, next_node=Node(data='E', next_node=None))\n",
"Node(data='E', next_node=None)\n"
]
}
],
"source": [
"# insert to footer\n",
"dl.insert('E', index=-1)\n",
"for node in dl:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# search by data\n",
"dl.search(('C',))"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='Z', next_node=Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))))\n",
"Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None))))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))\n",
"Node(data={'D'}, next_node=Node(data='E', next_node=None))\n",
"Node(data='E', next_node=None)\n"
]
}
],
"source": [
"# remove by data\n",
"dl.remove(['B'])\n",
"for node in dl:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='Z', next_node=Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))))\n",
"Node(data='E', next_node=None)\n"
]
}
],
"source": [
"# __getitem__\n",
"print(dl[0])\n",
"print(dl[-1])"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None))))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))\n",
"Node(data={'D'}, next_node=Node(data='E', next_node=None))\n",
"Node(data='E', next_node=None)\n"
]
}
],
"source": [
"# __delitem__\n",
"del dl[0]\n",
"for node in dl:\n",
" print(node)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(data='Z', next_node=Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))))\n",
"Node(data='A', next_node=Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None))))\n",
"Node(data=('C',), next_node=Node(data={'D'}, next_node=Node(data='E', next_node=None)))\n",
"Node(data={'D'}, next_node=Node(data='E', next_node=None))\n",
"Node(data='E', next_node=None)\n"
]
}
],
"source": [
"# __setitem__\n",
"dl[0] = 'Z'\n",
"for node in dl:\n",
" print(node)"
]
}
],
"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.5.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment