{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Linked List"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"class Element(object):\n",
" def __init__(self, value):\n",
" self.value = value\n",
" self.next = None"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"class LinkedList(object):\n",
" def __init__(self, head=None):\n",
" self.head = head\n",
" \n",
" \n",
" \n",
" '''Append the element'''\n",
" def append(self, new_element):\n",
" current = self.head\n",
" if self.head:\n",
" while current.next:\n",
" current = current.next\n",
" current.next = new_element\n",
" else:\n",
" self.head = new_element\n",
" \n",
" \n",
" \n",
" '''get the element form a given position'''\n",
" def get_position(self, position):\n",
" current = self.head\n",
" count = 1\n",
" if self.head:\n",
" while count < position:\n",
" current = current.next\n",
" count += 1\n",
" return current\n",
" else:\n",
" return None\n",
"\n",
" '''incert a new element at a given position'''\n",
" def insert(self, new_element, position):\n",
" current = self.head\n",
" count = 1\n",
" if position == 1:\n",
" new_element.next = current\n",
" self.head = new_element\n",
" else:\n",
" while count < position - 1:\n",
" current = current.next\n",
" count += 1\n",
" new_element.next = current.next\n",
" current.next = new_element\n",
"\n",
" \n",
" '''Delete the first node with a given value'''\n",
" \n",
" def delete(self, value):\n",
" current = self.head\n",
" prev = None\n",
" while current and current.value != value:\n",
" prev = current\n",
" current = current.next\n",
" if current is not None:\n",
" if current == self.head:\n",
" self.head = self.head.next\n",
" else:\n",
" prev.next = current.next\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"# Test cases\n",
"# Set up some Elements\n",
"e1 = Element(101)\n",
"e2 = Element(203)\n",
"e3 = Element(304)\n",
"e4 = Element(494)\n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"# Start setting up a LinkedList\n",
"ll = LinkedList(e1)\n",
"ll.append(e2)\n",
"ll.append(e3)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"494\n"
]
}
],
"source": [
"# Test get_position\n",
"# Should print 3\n",
"print(ll.head.next.next.value)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"304\n"
]
}
],
"source": [
"# Should also print 3\n",
"print(ll.get_position(4).value)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"494\n"
]
}
],
"source": [
"# Test insert\n",
"ll.insert(e4, 3)\n",
"# Should print 4 now\n",
"print (ll.get_position(3).value)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"101\n"
]
}
],
"source": [
"# Test delete\n",
"ll.delete(1)\n",
"# Should print 2 now\n",
"print (ll.get_position(1).value)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"203\n"
]
}
],
"source": [
"# Should print 4 now\n",
"print (ll.get_position(2).value)"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"494\n"
]
}
],
"source": [
"# Should print 3 now\n",
"print (ll.get_position(3).value)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Assignment"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" - Create a Linked List to store 10000 random numbers and \n",
" - delete odd positioned numbers and \n",
" - insert value '555' \n",
" - write a function to find a sum of all values and calculate sum"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"import random as random\n",
"E =[]\n",
"for k in range(100):\n",
" E.append(Element(random.randint(1,10000)))"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [],
"source": [
"ll = LinkedList()"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [],
"source": [
"for k in range(100):\n",
" ll.append(E[k])"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"9656\n",
"9656\n",
"4509\n",
"1356\n",
"9312\n",
"8289\n",
"7020\n",
"9412\n",
"4431\n",
"2283\n",
"8265\n",
"9535\n",
"4155\n",
"9205\n",
"4135\n",
"9736\n",
"5228\n",
"4380\n",
"5084\n",
"3540\n",
"7285\n",
"5262\n",
"2848\n",
"3315\n",
"912\n",
"5989\n",
"3884\n",
"6281\n",
"179\n",
"5496\n",
"5660\n",
"4249\n",
"6588\n",
"3374\n",
"2093\n",
"8686\n",
"3882\n",
"2106\n",
"2014\n",
"5232\n",
"712\n",
"8064\n",
"5489\n",
"1096\n",
"9049\n",
"8249\n",
"9278\n",
"1333\n",
"8010\n",
"6917\n",
"9583\n",
"2687\n",
"6262\n",
"2035\n",
"2881\n",
"2176\n",
"6238\n",
"230\n",
"7835\n",
"6427\n",
"8934\n",
"5016\n",
"5557\n",
"6439\n",
"9998\n",
"7756\n",
"3268\n",
"1722\n",
"4205\n",
"8121\n",
"4732\n",
"2966\n",
"4188\n",
"6723\n",
"7726\n",
"5965\n",
"8040\n",
"567\n",
"181\n",
"4605\n",
"2461\n",
"7387\n",
"3866\n",
"5203\n",
"1940\n",
"4572\n",
"5532\n",
"8942\n",
"883\n",
"9101\n",
"513\n",
"4534\n",
"872\n",
"8980\n",
"5252\n",
"7153\n",
"5669\n",
"499\n",
"1785\n",
"8385\n"
]
}
],
"source": [
"for i in range(100):\n",
" print(ll.get_position(i).value)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### This is not a solution. Do it yourself....."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"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.7.1"
},
"widgets": {
"state": {},
"version": "1.1.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}