DLList.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DLList:\n",
    "    class Node:\n",
    "        def __init__(self, content, prev, next):\n",
    "            self.content = content\n",
    "            self.prev = prev\n",
    "            self.next = next\n",
    "    def __init__(self):\n",
    "        self.dummy = DLList.Node(None, None, None)\n",
    "        self.dummy.prev = self.dummy\n",
    "        self.dummy.next = self.dummy\n",
    "        self.length = 0\n",
    "    def __len__(self):\n",
    "        return self.length\n",
    "    def _get_node(self, i):\n",
    "        res = self.dummy\n",
    "        if i < len(self) // 2:\n",
    "            for _ in range(i + 1):\n",
    "                res = res.next\n",
    "        else:\n",
    "            for _ in range(len(self) - i):\n",
    "                res = res.prev\n",
    "        return res\n",
    "    def __getitem__(self, i):\n",
    "        if i < 0 or i >= len(self):\n",
    "            raise IndexError()\n",
    "        return self._get_node(i).content\n",
    "    def __setitem__(self, i, value):\n",
    "        if i < 0 or i >= len(self):\n",
    "            raise IndexError()\n",
    "        self._get_node(i).content = value\n",
    "    def __iter__(self):\n",
    "        cursor = self.dummy\n",
    "        for _ in range(len(self)):\n",
    "            cursor = cursor.next\n",
    "            yield cursor.content\n",
    "    def _add_before(self, node, value):\n",
    "        newnode = DLList.Node(value, node.prev, node)\n",
    "        newnode.prev.next = newnode\n",
    "        newnode.next.prev = newnode\n",
    "        self.length += 1\n",
    "    def add(self, i, value):\n",
    "        if i < 0 or i > len(self):\n",
    "            raise IndexError()\n",
    "        self._add_before(self._get_node(i), value)\n",
    "    def _remove(self, node):\n",
    "        node.prev.next = node.next\n",
    "        node.next.prev = node.prev\n",
    "        self.length -= 1\n",
    "    def remove(self, i):\n",
    "        if i < 0 or i >= len(self):\n",
    "            raise IndexError()\n",
    "        self._remove(self._get_node(i))\n",
    "    def __list__(self):\n",
    "        return [x for x in self]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dl = DLList()\n",
    "list(dl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "dl.add(0,'zero')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "dl.add(1,'one')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['zero', 'one']"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(dl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "dl.add(1,'intervention')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['zero', 'intervention', 'one']"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(dl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "dl.add(0,'negone')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['negone', 'zero', 'intervention', 'one']"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(dl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "dl.remove(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['negone', 'zero', 'one']"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(dl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "dl.add(3, 'new')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['negone', 'zero', 'one', 'new']"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(dl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "dl.remove(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['zero', 'one', 'new']"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(dl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "dl.remove(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['zero', 'new']"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(dl)"
   ]
  },
  {
   "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}