{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Linked List"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from enum import Enum"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"class Position(Enum):\n",
" START = 0\n",
" END = 2"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"class Node:\n",
" def __init__(self, data):\n",
" self.data = data\n",
" self.next = None\n",
" \n",
" def __repr__(self):\n",
" return f'{self.__class__.__name__}({self.data})'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Insertions\n",
"1. Start: **O(1)**\n",
"1. Insert After: **O(n)**\n",
"1. End: **O(1)**"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"class LinkedList:\n",
" def __init__(self, ls = []):\n",
" self.head = None\n",
" self.tail = None\n",
" self.count = len(ls)\n",
" \n",
" if self.count > 0:\n",
" for item in ls:\n",
" self._insertEnd(item)\n",
" \n",
" def _insertStart(self, data):\n",
" self.count += 1\n",
" \n",
" tmp = Node(data)\n",
" tmp.next = self.head\n",
" self.head = tmp\n",
" \n",
" if self.tail is None:\n",
" self.tail = self.head\n",
" \n",
" return tmp\n",
" \n",
" def _insertAfter(self, data, after):\n",
" self.count += 1\n",
"\n",
" q = self.head\n",
"\n",
" while q is not None:\n",
" if q.data == after:\n",
" tmp = Node(data)\n",
" tmp.next = q.next\n",
" q.next = tmp\n",
" \n",
" if tmp.next is None:\n",
" self.tail = tmp\n",
" \n",
" return tmp\n",
" \n",
" q = q.next\n",
" \n",
" def _insertEnd(self, data):\n",
" self.count += 1\n",
"\n",
" if self.head is None:\n",
" tmp = Node(data)\n",
" self.head = self.tail = tmp\n",
" return tmp\n",
" \n",
" tmp = Node(data)\n",
" self.tail.next = tmp\n",
" self.tail = self.tail.next\n",
" \n",
" return tmp"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Deletions\n",
"1. Start: **O(1)**\n",
"1. Delete Element: **O(n)**\n",
"1. End: **O(n)**"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def _deleteStart(self):\n",
" if self.count == 0:\n",
" return\n",
" \n",
" self.count -= 1\n",
" \n",
" if self.head == self.tail:\n",
" self.head = self.tail = None\n",
" return\n",
" \n",
" tmp = self.head\n",
" self.head = self.head.next\n",
" \n",
" return tmp\n",
"\n",
"def _deleteEle(self, ele):\n",
" if self.count == 0 or (self.count == 1 and self.head.data != ele):\n",
" return\n",
" \n",
" if self.head.data == ele:\n",
" return self._deleteStart()\n",
" \n",
" q = self.head\n",
" \n",
" while q.next is not None:\n",
" if q.next.data == ele:\n",
" tmp = q.next\n",
" q.next = tmp.next\n",
" \n",
" if q.next is None:\n",
" self.tail = q\n",
" \n",
" self.count -= 1\n",
" \n",
" return tmp\n",
" \n",
" q = q.next\n",
" \n",
"\n",
"def _deleteEnd(self):\n",
" if self.count == 0:\n",
" return\n",
" \n",
" self.count -= 1\n",
"\n",
" if self.head is self.tail:\n",
" self.head = self.tail = None\n",
" return\n",
" \n",
" q = self.head\n",
"\n",
" while q.next is not self.tail:\n",
" q = q.next\n",
"\n",
" tmp = self.tail\n",
" self.tail = q\n",
" self.tail.next = None\n",
"\n",
" return tmp\n",
"\n",
"LinkedList._deleteEle = _deleteEle\n",
"LinkedList._deleteStart = _deleteStart\n",
"LinkedList._deleteEnd = _deleteEnd"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Public Interface"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def push(self, data, ele = Position.END):\n",
" method = {\n",
" Position.START: self._insertStart,\n",
" Position.END: self._insertEnd\n",
" }.get(ele, self._insertAfter)\n",
"\n",
" if method == self._insertAfter:\n",
" return self._insertAfter(data, ele)\n",
"\n",
" return method(data)\n",
"\n",
"def pop(self, ele = Position.END):\n",
" method = {\n",
" Position.START: self._deleteStart,\n",
" Position.END: self._deleteEnd\n",
" }.get(ele, self._deleteEle)\n",
"\n",
" if method == self._deleteEle:\n",
" return method(ele)\n",
"\n",
" return method()\n",
"\n",
"LinkedList.push = push\n",
"LinkedList.pop = pop"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Dunders\n",
"To make life easier"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"def __repr__(self): # For Debug purpose: it returns the string which upon executing, results in exact same object\n",
" ls = []\n",
" q = self.head\n",
"\n",
" while q is not None:\n",
" ls.append(q.data)\n",
" q = q.next\n",
"\n",
" return f'{self.__class__.__name__}({ls})'\n",
"\n",
"def __str__(self): # For User, pretty print of object\n",
" q = self.head\n",
"\n",
" s = ''\n",
"\n",
" while q and q.next is not None:\n",
" s += f'{q.data} -> '\n",
" q = q.next\n",
"\n",
" s += f'{str(q.data)}' if q is not None else None\n",
"\n",
" return f'[{s}]'\n",
"\n",
"def __len__(self):\n",
" return self.count\n",
"\n",
"LinkedList.__repr__ = __repr__\n",
"LinkedList.__str__ = __str__\n",
"LinkedList.__len__ = __len__"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Tests"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Linked List (7) : [0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6]\n"
]
}
],
"source": [
"ls = LinkedList()\n",
"\n",
"ls.push(3, Position.END)\n",
"ls.push(1, Position.START)\n",
"\n",
"ls.push(4, ele = 3)\n",
"ls.push(2, ele = 1)\n",
"\n",
"ls.push(0, Position.START)\n",
"ls.push(5, Position.END)\n",
"\n",
"ls.push(6)\n",
"\n",
"print(f\"Linked List ({len(ls)}) : {ls}\")"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"LinkedList([0, 1, 2, 3, 4, 5, 6])"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ls"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6]\n"
]
}
],
"source": [
"print(LinkedList([0, 1, 2, 3, 4, 5, 6])) # Yield same result as all the above statements"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Linked List (4) : [1 -> 2 -> 4 -> 5]\n"
]
}
],
"source": [
"ls.pop(Position.START)\n",
"ls.pop(3)\n",
"ls.pop(Position.END)\n",
"print(f\"Linked List ({len(ls)}) : {ls}\")"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"LinkedList([1, 2, 4, 5])"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ls"
]
}
],
"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
}