linked-list.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Single linked list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Trong trường hợp Stack được cài đặt bằng linked list thì chi phí của tất cả các hàm <br>\n",
    "pop(), push(), top(), len(), is_empty() đều là O(1) khác với khi cài đặt bằng mảng Array, vì ở đây không có phi phí resize kích thước mảng (amortized cost)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class LinkedStack:\n",
    "    class _Node:\n",
    "        __slots__ = '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next;\n",
    "        \n",
    "    def __init__(self):\n",
    "        self._head = None\n",
    "        self._size = 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def push(self, e):\n",
    "        self._head = self._Node(e, self._head)\n",
    "        self._size = 1\n",
    "        \n",
    "    def top(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty')\n",
    "            \n",
    "        return self._head._element\n",
    "    \n",
    "    def pop(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty')\n",
    "        \n",
    "        answer = self._head._element\n",
    "        self._head = self._head._next\n",
    "        self._size -= 1\n",
    "        return answer\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "6\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "class LinkedQueue:\n",
    "    class _Node:\n",
    "        __slots__ =  '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next\n",
    "            \n",
    "    def __init__(self):\n",
    "        self._head = None\n",
    "        self._tail = None\n",
    "        self._size = 0\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty')\n",
    "        return self._head._element\n",
    "    \n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty')\n",
    "        \n",
    "        answer = self._head._element\n",
    "        self._head = self._head._next\n",
    "        self._size -= 1\n",
    "        if self.is_empty():\n",
    "            self._tail = None\n",
    "            \n",
    "        return answer\n",
    "    \n",
    "    def enqueue(self, e):\n",
    "        newest = self._Node(e, None)\n",
    "        \n",
    "        if self.is_empty():\n",
    "            self._head = newest\n",
    "        else:\n",
    "            self._tail._next = newest\n",
    "        self._tail = newest\n",
    "        self._size += 1\n",
    "        \n",
    "S = LinkedQueue()\n",
    "S.enqueue(5)\n",
    "S.enqueue(6)\n",
    "S.enqueue(7)\n",
    "\n",
    "print(S.dequeue())\n",
    "print(S.dequeue())\n",
    "print(S.dequeue())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Circularly linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class CircleQueue:\n",
    "    class _Node:\n",
    "         __slots__ =  '_element', '_next'\n",
    "        \n",
    "        def __init__(self, element, next):\n",
    "            self._element = element\n",
    "            self._next = next\n",
    "            \n",
    "    def __init__(self):\n",
    "        self._tail = None\n",
    "        self._size = 0\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('CircleQueue is empty')\n",
    "            \n",
    "        head = self._tail._next\n",
    "        return head._element\n",
    "    \n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('CircleQueue is empty')\n",
    "        oldhead = self._tail._next\n",
    "        if self._size == 1:\n",
    "            self._tail = None\n",
    "        else:\n",
    "            self._tail._next = oldhead._next\n",
    "        self._size -= 1\n",
    "        return oldhead._element\n",
    "        \n",
    "    def enqueue(self, e):\n",
    "        newest = self._Node(e, None)\n",
    "        \n",
    "        if self.is_empty():\n",
    "            newest._next = newest\n",
    "        else:\n",
    "            newest._next = self._tail._next\n",
    "            self._tail._next = newest\n",
    "        self._tail = newest\n",
    "        self._size += 1\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Double linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class _DoubleLinkedBase:\n",
    "    class _Node:\n",
    "        __slots__ = '_element', \"_next\", \"_prev\"\n",
    "        \n",
    "        def __init__(self, e, prev, next):\n",
    "            self._element = e\n",
    "            self._prev = prev\n",
    "            self._next = next\n",
    "            \n",
    "    def __init__(self):\n",
    "        self._header = self._Node(None, None, None)\n",
    "        self._trailer = self._None(None, None, None)\n",
    "        self._header._next = self._trailer   # trailer is after header\n",
    "        self._trailer._prev = self._header   # header is before trailer\n",
    "        self._size = 0\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def _insert_between(self, e, predecessor, successor):\n",
    "        newest = self._Node(e, predecessor, successor)\n",
    "        predecessor._next = newest\n",
    "        successor._prev = newest\n",
    "        self._size += 1\n",
    "        return newest\n",
    "    \n",
    "    def _delete_node(self, node):\n",
    "        predecessor = node._prev\n",
    "        successor = node._next\n",
    "        predecessor._next = successor\n",
    "        successor._prev = predecessor\n",
    "        self._size -= 1\n",
    "        element = node._element\n",
    "        node._prev = node._next = node._element = None\n",
    "        return element\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class LinkedDeque(_DoubleLinkedBase):\n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Deque is empty')\n",
    "            \n",
    "        return self._header._next._element\n",
    "    \n",
    "    def last(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Deque is empty')\n",
    "            \n",
    "        return self._trailer._prev._element\n",
    "    \n",
    "    \n",
    "    def insert_first(self, e):\n",
    "        return self._insert_between(e, self._header, self._header._next)\n",
    "    \n",
    "    def insert_last(self, e):\n",
    "        return self._insert_between(e, self._trailer._prev, self._trailer._next)\n",
    "    \n",
    "    def delete_first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Deque is empty')\n",
    "            \n",
    "        return self._delete_node(self._head._next)\n",
    "    \n",
    "    def delete_last(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Deque is empty')\n",
    "        return self._delete_node(self._tail._prev)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class PositionalList(_DoubleLinkedBase):\n",
    "    \n",
    "    #--------------- Nested Position class ----------------#\n",
    "    class Position:\n",
    "        def __init__(self, container, node):\n",
    "            self._container = container\n",
    "            self._node = node\n",
    "            \n",
    "        def element(self):\n",
    "            return self._node._element\n",
    "        \n",
    "        def __eq__(self, other):\n",
    "            return type(other) is type(self) and other._node is self._node\n",
    "        \n",
    "        def __ne__(self, other):\n",
    "            return not (self == other)\n",
    "    \n",
    "    #-------------- Utility method ----------------------#\n",
    "    def _validate(self, p):\n",
    "        if not isinstance(p, self.Position):\n",
    "            raise TypeError('p must be proper Position type')\n",
    "        if p._container is not self:\n",
    "            raise TypeError('p does not belong to this container')\n",
    "        if p._node._next is None:\n",
    "            raise ValueError('p is no longer valid')\n",
    "        return p._node\n",
    "    \n",
    "    def _make_position(self, node):\n",
    "        if node is self._header or node is self._trailer:\n",
    "            return None\n",
    "        else:\n",
    "            return self.Position(self, node)\n",
    "        \n",
    "    # ------------ Accessor method ---------------------#\n",
    "    def first(self):\n",
    "        return self._make_position(self._header._next)\n",
    "    \n",
    "    def last(self):\n",
    "        return self._make_position(self._trailer._prev)\n",
    "    \n",
    "    def before(self, p):\n",
    "        node = self._validate(p)\n",
    "        return self._make_position(node._prev)\n",
    "    \n",
    "    def after(self, p):\n",
    "        node = self._validate(p)\n",
    "        return self._make_position(node._next)\n",
    "    \n",
    "    def __iter__(self):\n",
    "        cursor = self.first()\n",
    "        while cursor is not None:\n",
    "            yield cursor.element()\n",
    "            cursor = self.after(cursor)\n",
    "            \n",
    "    #------------ Mutator ----------------------------#\n",
    "    def _insert_between(self, e, predecessor, successor):\n",
    "        node = super()._insert_between(e, predecessor, successor)\n",
    "        return self._make_position(node)\n",
    "    \n",
    "    def add_first(self, e):\n",
    "        return self._insert_between(e, self._header, self._header._next)\n",
    "    \n",
    "    def add_last(self, e):\n",
    "        return self._insert_between(e, self._trailer._prev, self._trailer)\n",
    "    \n",
    "    def add_before(self, p, e):\n",
    "        original = self._validate(p)\n",
    "        return self._insert_between(e, original._prev, orignal)\n",
    "    \n",
    "    def add_after(self, p, e):\n",
    "        original = self._validate(p)\n",
    "        return self._insert_between(e, original, orginal._next)\n",
    "    \n",
    "    def delete(self, p):\n",
    "        orginal = self._validate(p)\n",
    "        return self._delele_node(original)\n",
    "    \n",
    "    def replace(self, p, e):\n",
    "        original = self._validate(p)\n",
    "        old_value = original._element\n",
    "        original._element = e\n",
    "        return old_value\n",
    "        "
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}