{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "eb4e80c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# singly-linked list data structure\n",
    "#\n",
    "class LinkedList:\n",
    "\n",
    "    # initial values for the properties of an empty LinkedList object\n",
    "    #\n",
    "    # they begin with an understore to mark that they should not\n",
    "    # be accessed directly from outside, only through methods\n",
    "    #\n",
    "    def __init__(self):\n",
    "        self._head = None\n",
    "        self._tail = None\n",
    "    \n",
    "    # inserts an additional item at the head of the list\n",
    "    #\n",
    "    def push_front(self, value):\n",
    "        new_node = LinkedListNode()\n",
    "        new_node.set_item(value)\n",
    "        if self.is_empty():\n",
    "            self._tail = new_node  # if the list is empty, the new node also becomes its tail\n",
    "        new_node.set_next(self._head)  # the old head is attached to the new element\n",
    "        self._head = new_node  # the new node now becomes the new head of the list\n",
    "    \n",
    "    # insert an item right after a given node;\n",
    "    # precondition/contract: the node must belong to the present list\n",
    "    #\n",
    "    def push_after(self, node, value):\n",
    "        new_node = LinkedListNode()\n",
    "        if not node.has_next():  # check whether we are inserting at the end of the list\n",
    "            self._tail = new_node   # if that is the case, the new node becomes the tail of the list\n",
    "        new_node.set_item(value)\n",
    "        new_node.set_next(node.get_next())\n",
    "        node.set_next(new_node)\n",
    "    \n",
    "    # inserts an additional item at the end of the list\n",
    "    #\n",
    "    def push_back(self, value):\n",
    "        if not self.is_empty():\n",
    "            self.push_after(self._tail, value)\n",
    "        else:\n",
    "            self.push_front(value)\n",
    "    \n",
    "    # removes the head element from the list, returning its value\n",
    "    #\n",
    "    def pop_front(self):\n",
    "        old_head_value = self._head.get_item()  # access value of the old head element\n",
    "        new_head_node = self._head.get_next()\n",
    "        self._head.set_next(None)  # detach the head from the list (not strictly required)\n",
    "        self._head = new_head_node  # designate its previous successor as the new head node\n",
    "        return old_head_value\n",
    "    \n",
    "    # removes the successor element of a given node from the list, returning its value;\n",
    "    # precondition/contract: the node must belong to the present list\n",
    "    #\n",
    "    def pop_after(self, node):\n",
    "        if node.has_next():\n",
    "            old_successor_node = node.get_next()\n",
    "            if old_successor_node.has_next():\n",
    "                new_successor_node = old_successor_node.get_next()\n",
    "                old_successor_node.set_next(None)  # detach the previous successor from the list\n",
    "                node.set_next(new_successor_node)\n",
    "            else:\n",
    "                node.set_next(None)\n",
    "                self._tail = node  # node becomes the tail element after the previous tail was detached\n",
    "            return old_successor_node.get_item()\n",
    "        else:\n",
    "            return None\n",
    "    \n",
    "    # deleting the content would be feasible just by setting head and tail to None\n",
    "    # for better consistency, we also detach all the nodes, which is not strictly necessary\n",
    "    #\n",
    "    def clear(self):\n",
    "        while not self.is_empty():\n",
    "            self.pop_front()\n",
    "\n",
    "    # states whether the list is empty\n",
    "    #\n",
    "    def is_empty(self):\n",
    "        return (self._head is None)\n",
    "    \n",
    "    # returns the first node of the list\n",
    "    #\n",
    "    def get_head(self):\n",
    "        return self._head\n",
    "\n",
    "    # return the number of elements in the linked list\n",
    "    #\n",
    "    def length(self):\n",
    "        if self.is_empty():\n",
    "            return 0\n",
    "        iterator = self._head\n",
    "        nodes = 1\n",
    "        while iterator.has_next():\n",
    "            iterator = iterator.get_next()\n",
    "            nodes += 1\n",
    "        return nodes\n",
    "\n",
    "    # returns a string representation of the list, for printing output\n",
    "    #\n",
    "    def string(self):\n",
    "        out = \"<\"\n",
    "        if not self.is_empty():\n",
    "            iterator = self._head\n",
    "            while iterator.has_next():\n",
    "                out = out + str(iterator.get_item()) + \"; \"\n",
    "                iterator = iterator.get_next()\n",
    "            out = out + str(iterator.get_item())\n",
    "        out = out + \">\"\n",
    "        return out\n",
    "    \n",
    "    # replaces the content of self with the content of a dyn. array (Python list)\n",
    "    #\n",
    "    def copy_from_dynarray(self, dynarray):\n",
    "        self.clear()  # remove all previous content from the linked list\n",
    "        for el in dynarray:\n",
    "            self.push_back(el)  # insert content of the Python list as new content of self\n",
    "\n",
    "    # replaces the contant of a dyn. array (Python list) with the content of self\n",
    "    #\n",
    "    def copy_into_dynarray(self, dynarray):\n",
    "        dynarray.clear()\n",
    "        iterator = self._head\n",
    "        data_left = True\n",
    "        while data_left:\n",
    "            dynarray.append(iterator.get_item())\n",
    "            if iterator.has_next():\n",
    "                iterator = iterator.get_next()\n",
    "            else:\n",
    "                data_left = False\n",
    "\n",
    "# node in a singly-linked list\n",
    "#\n",
    "class LinkedListNode:\n",
    "    def __init__(self):\n",
    "        self._item = None\n",
    "        self._next = None\n",
    "    \n",
    "    def set_item(self, value):\n",
    "        self._item = value\n",
    "    def set_next(self, next_node):\n",
    "        self._next = next_node\n",
    "    \n",
    "    def get_item(self):\n",
    "        return self._item\n",
    "    def get_next(self):\n",
    "        return self._next\n",
    "    \n",
    "    # returns True if there is a next element, false if the next\n",
    "    # element is None, i.e., if we are at the end of the list\n",
    "    #\n",
    "    def has_next(self):\n",
    "        return (self._next is not None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0956104f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# doubly-linked list data structure\n",
    "#\n",
    "class DoublyLinkedList:\n",
    "\n",
    "    # initial values for the properties of an empty LinkedList object\n",
    "    #\n",
    "    # they begin with an understore to mark that they should not\n",
    "    # be accessed directly from outside, only through methods\n",
    "    #\n",
    "    def __init__(self):\n",
    "        self._head = None\n",
    "        self._tail = None\n",
    "    \n",
    "    # inserts an additional item at the head of the list\n",
    "    #\n",
    "    def push_front(self, value):\n",
    "        new_node = DoublyLinkedListNode()\n",
    "        new_node.set_item(value)\n",
    "        if self.is_empty():\n",
    "            self._tail = new_node  # if the list is empty, the new node also becomes its tail\n",
    "        else:\n",
    "            self._head.set_prev(new_node)\n",
    "        new_node.set_next(self._head)  # the old head is attached to the new element\n",
    "        self._head = new_node  # the new node now becomes the new head of the list\n",
    "    \n",
    "    # insert an item right after a given node;\n",
    "    # precondition/contract: the node must belong to the present list\n",
    "    #\n",
    "    def push_after(self, node, value):\n",
    "        new_node = DoublyLinkedListNode()\n",
    "        if not node.has_next():  # check whether we are inserting at the end of the list\n",
    "            self._tail = new_node   # if that is the case, the new node becomes the tail of the list\n",
    "        else:\n",
    "            node.get_next().set_prev(new_node)\n",
    "        new_node.set_item(value)\n",
    "        new_node.set_next(node.get_next())\n",
    "        new_node.set_prev(node)\n",
    "        node.set_next(new_node)\n",
    "    \n",
    "    # inserts an additional item at the end of the list\n",
    "    #\n",
    "    def push_back(self, value):\n",
    "        if not self.is_empty():\n",
    "            self.push_after(self._tail, value)\n",
    "        else:\n",
    "            self.push_front(value)\n",
    "    \n",
    "    # removes the head element from the list, returning its value\n",
    "    #\n",
    "    def pop_front(self):\n",
    "        old_head_value = self._head.get_item()  # access value of the old head element\n",
    "        new_head_node = self._head.get_next()\n",
    "        self._head.set_next(None)  # detach the head from the list (not strictly required)\n",
    "        self._head.set_prev(None)  # detach the head from the list (not strictly required)\n",
    "        new_head_node.set_prev(None)\n",
    "        self._head = new_head_node  # designate its previous successor as the new head node\n",
    "        return old_head_value\n",
    "        \n",
    "    def pop(self, node):\n",
    "        prev_node = node.get_prev()\n",
    "        next_node = node.get_next()\n",
    "        \n",
    "        if prev_node is None:\n",
    "            return self.pop_front()\n",
    "        else:\n",
    "            prev_node.set_next(next_node)\n",
    "        if next_node is None:\n",
    "            self._tail = prev_node\n",
    "        else:\n",
    "            next_node.set_prev(prev_node)\n",
    "            \n",
    "        node.set_prev(None)\n",
    "        node.set_next(None)\n",
    "        return node.get_item()\n",
    "    \n",
    "    # deleting the content would be feasible just by setting head and tail to None\n",
    "    # for better consistency, we also detach all the nodes, which is not strictly necessary\n",
    "    #\n",
    "    def clear(self):\n",
    "        while not self.is_empty():\n",
    "            self.pop_front()\n",
    "\n",
    "    # states whether the list is empty\n",
    "    #\n",
    "    def is_empty(self):\n",
    "        return (self._head is None)\n",
    "    \n",
    "    # returns the first node of the list\n",
    "    #\n",
    "    def get_head(self):\n",
    "        return self._head\n",
    "\n",
    "    # return the number of elements in the linked list\n",
    "    #\n",
    "    def length(self):\n",
    "        if self.is_empty():\n",
    "            return 0\n",
    "        iterator = self._head\n",
    "        nodes = 1\n",
    "        while iterator.has_next():\n",
    "            iterator = iterator.get_next()\n",
    "            nodes += 1\n",
    "        return nodes\n",
    "\n",
    "    # returns a string representation of the list, for printing output\n",
    "    #\n",
    "    def string(self):\n",
    "        out = \"<\"\n",
    "        if not self.is_empty():\n",
    "            iterator = self._head\n",
    "            while iterator.has_next():\n",
    "                out = out + str(iterator.get_item()) + \"; \"\n",
    "                iterator = iterator.get_next()\n",
    "            out = out + str(iterator.get_item())\n",
    "        out = out + \">\"\n",
    "        return out\n",
    "    \n",
    "    # replaces the content of self with the content of a dyn. array (Python list)\n",
    "    #\n",
    "    def copy_from_dynarray(self, dynarray):\n",
    "        self.clear()  # remove all previous content from the linked list\n",
    "        for el in dynarray:\n",
    "            self.push_back(el)  # insert content of the Python list as new content of self\n",
    "\n",
    "    # replaces the contant of a dyn. array (Python list) with the content of self\n",
    "    #\n",
    "    def copy_into_dynarray(self, dynarray):\n",
    "        dynarray.clear()\n",
    "        iterator = self._head\n",
    "        data_left = True\n",
    "        while data_left:\n",
    "            dynarray.append(iterator.get_item())\n",
    "            if iterator.has_next():\n",
    "                iterator = iterator.get_next()\n",
    "            else:\n",
    "                data_left = False\n",
    "\n",
    "# node in a doubly-linked list\n",
    "#\n",
    "class DoublyLinkedListNode:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._prev = None\n",
    "        self._item = None\n",
    "        self._next = None\n",
    "    \n",
    "    def set_item(self, value):\n",
    "        self._item = value\n",
    "    def set_next(self, next_node):\n",
    "        self._next = next_node\n",
    "    def set_prev(self, prev_node):\n",
    "        self._prev = prev_node\n",
    "    \n",
    "    def get_item(self):\n",
    "        return self._item\n",
    "    def get_next(self):\n",
    "        return self._next\n",
    "    def get_prev(self):\n",
    "        return self._prev\n",
    "    \n",
    "    # returns True if there is a next element, false if the next\n",
    "    # element is None, i.e., if we are at the end of the list\n",
    "    #\n",
    "    def has_next(self):\n",
    "        return (self._next is not None)\n",
    "    \n",
    "    # returns True if there is a previous element, false if the previous\n",
    "    # element is None, i.e., if we are at the head of the list\n",
    "    #\n",
    "    def has_prev(self):\n",
    "        return (self._prev is not None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5c89bedc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "random_dynarray: [12, 19, 7, 8, 18]\n",
      "linked_list_copy: <12; 19; 7; 8; 18>\n",
      "length of linked list: 5\n",
      "doubly_linked_list_copy: <12; 19; 7; 8; 18>\n",
      "length of doubly linked list: 5\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "random_dynarray = [random.randrange(25) for i in range(5)]\n",
    "print(\"random_dynarray:\", random_dynarray)\n",
    "\n",
    "linked_list_copy = LinkedList()\n",
    "linked_list_copy.copy_from_dynarray(random_dynarray)\n",
    "print(\"linked_list_copy:\", linked_list_copy.string())\n",
    "print(\"length of linked list:\", linked_list_copy.length())\n",
    "\n",
    "doubly_linked_list_copy = DoublyLinkedList()\n",
    "doubly_linked_list_copy.copy_from_dynarray(random_dynarray)\n",
    "print(\"doubly_linked_list_copy:\", doubly_linked_list_copy.string())\n",
    "print(\"length of doubly linked list:\", doubly_linked_list_copy.length())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5867b8c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Problem/task:\n",
    "#\n",
    "# For each element (el) of a list, determine its value modulo three (el % 3),\n",
    "# and replace it with el % 3 copies of itself, adjacent to each other\n",
    "#\n",
    "# Precondition: The argument is a list (Python list or linked list, respectively) of integer numbers\n",
    "#\n",
    "# In other words, multiples of three are deleted, values of the type 3k+1 are unchanged,\n",
    "# and values of the type 3k+2 are copied so that they occur twice, next to each other\n",
    "#\n",
    "# For example, [4, 11, 8, 9, 20] should become [4, 11, 11, 8, 8, 20, 20]\n",
    "\n",
    "# Implementation for a Python list (dynamic array)\n",
    "#\n",
    "def mod3_copying_dynarray(dynarray):\n",
    "    # note that the length of the list changes during this operation;\n",
    "    # we need the index no. for inserting elements in the middle;\n",
    "    # therefore a loop over range(...) will be inappropriate\n",
    "    #\n",
    "    i = 0\n",
    "    while i < len(dynarray):\n",
    "        if dynarray[i] % 3 == 0:\n",
    "            dynarray.pop(i)  # multiple of 3, remove from list\n",
    "        elif dynarray[i] % 3 == 2:\n",
    "            dynarray.insert(i+1, dynarray[i])  # insert a copy of the present value\n",
    "            i += 2  # jump two forward, to the next value\n",
    "        else:\n",
    "            i += 1  # do nothing, proceed to the next value\n",
    "\n",
    "def mod3_copying_linked_list(linked_list):\n",
    "    if linked_list.is_empty():\n",
    "        return\n",
    "    #\n",
    "    # special treatment for the head element\n",
    "    #\n",
    "    # why is that necessary? the singly linked list distinguishes\n",
    "    # \"pop_after\" and \"push_after\" from \"pop_front\" and \"push_front\"\n",
    "    #\n",
    "    iterator = linked_list.get_head()\n",
    "    while iterator.get_item() % 3 == 0:\n",
    "        linked_list.pop_front()\n",
    "        iterator = linked_list.get_head()\n",
    "    if iterator.get_item() % 3 == 2:\n",
    "        linked_list.push_front(iterator.get_item())\n",
    "    #\n",
    "    # now traverse the remainder of the list\n",
    "    #\n",
    "    while iterator.has_next():\n",
    "        previous_node = iterator  # for \"pop_after\", to detach the present element, we need the previous node\n",
    "        iterator = iterator.get_next()\n",
    "        if iterator.get_item() % 3 == 0:\n",
    "            linked_list.pop_after(previous_node)\n",
    "            iterator = previous_node\n",
    "        elif iterator.get_item() % 3 == 2:\n",
    "            linked_list.push_after(iterator, iterator.get_item())\n",
    "            iterator = iterator.get_next()\n",
    "\n",
    "def mod3_copying_doubly_linked_list(linked_list):\n",
    "    if linked_list.is_empty():\n",
    "        return\n",
    "    #\n",
    "    # special treatment for the head element\n",
    "    #\n",
    "    # why is that necessary? the singly linked list distinguishes\n",
    "    # \"pop_after\" and \"push_after\" from \"pop_front\" and \"push_front\"\n",
    "    #\n",
    "    iterator = linked_list.get_head()\n",
    "    while iterator.get_item() % 3 == 0:\n",
    "        linked_list.pop_front()\n",
    "        iterator = linked_list.get_head()\n",
    "    if iterator.get_item() % 3 == 2:\n",
    "        linked_list.push_front(iterator.get_item())\n",
    "    #\n",
    "    # now traverse the remainder of the list\n",
    "    #\n",
    "    while iterator.has_next():\n",
    "        previous_node = iterator  # for \"pop_after\", to detach the present element, we need the previous node\n",
    "        iterator = iterator.get_next()\n",
    "        if iterator.get_item() % 3 == 0:\n",
    "            linked_list.pop(iterator)\n",
    "            iterator = previous_node\n",
    "        elif iterator.get_item() % 3 == 2:\n",
    "            linked_list.push_after(iterator, iterator.get_item())\n",
    "            iterator = iterator.get_next()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36391e0b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "random_dynarray = [random.randrange(25) for i in range(5)]\n",
    "print(\"random_dynarray:\", random_dynarray)\n",
    "\n",
    "linked_list_copy = LinkedList()\n",
    "linked_list_copy.copy_from_dynarray(random_dynarray)\n",
    "print(\"linked_list_copy:\", linked_list_copy.string())\n",
    "\n",
    "doubly_linked_list_copy = DoublyLinkedList()\n",
    "doubly_linked_list_copy.copy_from_dynarray(random_dynarray)\n",
    "print(\"doubly_linked_list_copy:\", doubly_linked_list_copy.string())\n",
    "\n",
    "print(\"\\n*** now running the mod-3 copy functions ***\\n\")\n",
    "\n",
    "mod3_copying_dynarray(random_dynarray)\n",
    "mod3_copying_linked_list(linked_list_copy)\n",
    "mod3_copying_doubly_linked_list(doubly_linked_list_copy)\n",
    "print(\"new status of dyn. array:\", random_dynarray)\n",
    "print(\"new status of linked list:\", linked_list_copy.string())\n",
    "print(\"new status of doubly linked list:\", doubly_linked_list_copy.string())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "091bf754",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import random\n",
    "\n",
    "step = 50\n",
    "nmax = 20000\n",
    "repetitions = 20\n",
    "\n",
    "perf_dynarray, perf_linked, = {}, {}\n",
    "random.seed()\n",
    "\n",
    "for n in range(0, nmax+1, step):\n",
    "    runtime_dynarray, runtime_linked = 0.0, 0.0\n",
    "    list_lengths_dynarray, list_lengths_linked = 0, 0\n",
    "    for i in range(repetitions):\n",
    "        test_dynarray_n = [random.randrange(n*n) for j in range(n)]\n",
    "        test_linked_n = LinkedList()\n",
    "        test_linked_n.copy_from_dynarray(test_dynarray_n)\n",
    "        \n",
    "        start = time.time()\n",
    "        mod3_copying_dynarray(test_dynarray_n)\n",
    "        runtime_dynarray += time.time() - start\n",
    "        list_lengths_dynarray += len(test_dynarray_n)\n",
    "        \n",
    "        start = time.time()\n",
    "        mod3_copying_linked_list(test_linked_n)\n",
    "        runtime_linked += time.time() - start\n",
    "        list_lengths_linked += test_linked_n.length()\n",
    "        \n",
    "    perf_dynarray[n] = runtime_dynarray / repetitions\n",
    "    perf_linked[n] = runtime_linked / repetitions\n",
    "    \n",
    "    print(n, perf_dynarray[n], perf_linked[n], \\\n",
    "          list_lengths_dynarray/repetitions, list_lengths_linked/repetitions, \\\n",
    "          sep='\\t')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e409cb0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import seaborn as sbn\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "keylist_dynarray = list(perf_dynarray.keys())\n",
    "vallist_dynarray = list(perf_dynarray.values())\n",
    "\n",
    "keylist_linked = list(perf_linked.keys())\n",
    "vallist_linked = list(perf_linked.values())\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "fig.set_size_inches(15, 9)\n",
    "plt.xticks(fontsize=18, color=\"#322300\")\n",
    "plt.yticks(fontsize=18, color=\"#322300\")\n",
    "ax.set_xlabel(\"input list size\", fontsize=24, color=\"#322300\")\n",
    "ax.set_ylabel(\"average runtime in seconds\", fontsize=24, color=\"#322300\")\n",
    "\n",
    "sbn.regplot(x=keylist_dynarray, y=vallist_dynarray, color='#005528', \\\n",
    "            order=2, scatter_kws={'s':5})  # green for dynamic array (Python list)\n",
    "sbn.regplot(x=keylist_linked, y=vallist_linked, color='#002855', \\\n",
    "            order=1, scatter_kws={'s':5})  # blue for singly-linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1de8c673",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}