Chapter_10_Elementary_Data_Structures/exercises_10.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10.2 Linked lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.2-1\n",
    "\n",
    "> Can you implement the dynamic-set operation INSERT on a singly linked list\n",
    "in $O(1)$ time? How about DELETE?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "INSERT: $O(1)$.\n",
    "\n",
    "DELETE: $O(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkListNode:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "def to_str(head):\n",
    "    values = []\n",
    "    head = head.next\n",
    "    while head is not None:\n",
    "        values.append(head.value)\n",
    "        head = head.next\n",
    "    return ' '.join(map(str, values))\n",
    "\n",
    "\n",
    "def insert(head, x):\n",
    "    new_node = LinkListNode(x)\n",
    "    new_node.next = head.next\n",
    "    head.next = new_node\n",
    "\n",
    "\n",
    "def delete(head, x):\n",
    "    while head is not None:\n",
    "        if head.next is not None and head.next.value == x:\n",
    "            head.next = head.next.next\n",
    "        else:\n",
    "            head = head.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.2-2\n",
    "\n",
    "> Implement a stack using a singly linked list $L$. The operations PUSH and POP should still take $O(1)$ time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkListNode:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "def push(head, x):\n",
    "    new_node = LinkListNode(x)\n",
    "    new_node.next = head.next\n",
    "    head.next = new_node\n",
    "\n",
    "\n",
    "def pop(head):\n",
    "    if head.next is None:\n",
    "        return None\n",
    "    x = head.next.value\n",
    "    head.next = head.next.next\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.2-3\n",
    "\n",
    "> Implement a queue by a singly linked list $L$. The operations ENQUEUE and DEQUEUE should still take $O(1)$ time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkListNode:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = LinkListNode(None)\n",
    "\n",
    "    def enqueue(self, x):\n",
    "        new_node = LinkListNode(x)\n",
    "        if self.tail.next is None:\n",
    "            self.head = new_node\n",
    "            self.tail.next = self.head\n",
    "        else:\n",
    "            self.head.next = new_node\n",
    "            self.head = new_node\n",
    "\n",
    "    def dequeue(self):\n",
    "        if self.tail.next is None:\n",
    "            return None\n",
    "        x = self.tail.next.value\n",
    "        self.tail = self.tail.next\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.2-4\n",
    "\n",
    "> As written, each loop iteration in the LIST-SEARCH' procedure requires two tests: one for $x \\ne L.nil$ and one for $x.key \\ne k$. Show how to eliminate the test for $x \\ne L.nil$ in each iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkListNode:\n",
    "    def __init__(self, key):\n",
    "        self.key = key\n",
    "        self.next = None\n",
    "        self.prev = None\n",
    "\n",
    "\n",
    "class LinkList:\n",
    "    def __init__(self):\n",
    "        self.nil = LinkListNode(None)\n",
    "        self.nil.next = self.nil\n",
    "        self.nil.prev = self.nil\n",
    "\n",
    "    def insert(self, x):\n",
    "        x = LinkListNode(x)\n",
    "        x.next = self.nil.next\n",
    "        x.prev = self.nil\n",
    "        x.next.prev = x\n",
    "        x.prev.next = x\n",
    "\n",
    "    def search(self, k):\n",
    "        self.nil.key = k\n",
    "        x = self.nil.next\n",
    "        while x.key != k:\n",
    "            x = x.next\n",
    "        if x == self.nil:\n",
    "            return None\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.2-5\n",
    "\n",
    "> Implement the dictionary operations INSERT, DELETE, and SEARCH using singly linked, circular lists. What are the running times of your procedures?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "INSERT $\\Theta(n)$, DELETE $\\Theta(n)$, SEARCH $\\Theta(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkListNode:\n",
    "    def __init__(self, key, value):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "        self.prev = None\n",
    "\n",
    "\n",
    "class Dict:\n",
    "    def __init__(self):\n",
    "        self.nil = LinkListNode(None, None)\n",
    "        self.nil.next = self.nil\n",
    "        self.nil.prev = self.nil\n",
    "\n",
    "    def insert(self, key, value):\n",
    "        x = self.search_node(key)\n",
    "        if x is None:\n",
    "            x = LinkListNode(key, value)\n",
    "            x.next = self.nil.next\n",
    "            x.prev = self.nil\n",
    "            x.next.prev = x\n",
    "            x.prev.next = x\n",
    "        else:\n",
    "            x.value = value\n",
    "\n",
    "    def delete(self, key):\n",
    "        x = self.search_node(key)\n",
    "        if x is not None:\n",
    "            x.next.prev = x.prev\n",
    "            x.prev.next = x.next\n",
    "\n",
    "    def search_node(self, key):\n",
    "        self.nil.key = key\n",
    "        x = self.nil.next\n",
    "        while x.key != key:\n",
    "            x = x.next\n",
    "        if x == self.nil:\n",
    "            return None\n",
    "        return x\n",
    "\n",
    "    def search(self, key):\n",
    "        x = self.search_node(key)\n",
    "        if x is None:\n",
    "            return None\n",
    "        return x.value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.2-6\n",
    "\n",
    "> The dynamic-set operation UNION takes two disjoint sets $S_1$ and $S_2$ as input, and it returns a set $S = S1 \\cup S2$ consisting of all the elements of $S_1$ and $S_2$. The sets $S_1$ and $S_2$ are usually destroyed by the operation. Show how to support UNION in $O(1)$ time using a suitable list data structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkListNode:\n",
    "    def __init__(self, key):\n",
    "        self.key = key\n",
    "        self.next = None\n",
    "        self.prev = None\n",
    "\n",
    "\n",
    "class LinkList:\n",
    "    def __init__(self):\n",
    "        self.nil = LinkListNode(None)\n",
    "        self.nil.next = self.nil\n",
    "        self.nil.prev = self.nil\n",
    "\n",
    "    def insert(self, key):\n",
    "        x = LinkListNode(key)\n",
    "        x.next = self.nil.next\n",
    "        x.prev = self.nil\n",
    "        x.next.prev = x\n",
    "        x.prev.next = x\n",
    "\n",
    "    def values(self):\n",
    "        values = []\n",
    "        x = self.nil.next\n",
    "        while x != self.nil:\n",
    "            values.append(x.key)\n",
    "            x = x.next\n",
    "        return values\n",
    "\n",
    "\n",
    "def union(list_1, list_2):\n",
    "    list_1.nil.next.prev = list_2.nil.prev\n",
    "    list_2.nil.prev.next = list_1.nil.next\n",
    "    list_1.nil.next = list_2.nil.next\n",
    "    list_2.nil.next.prev = list_1.nil\n",
    "    return list_1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.2-7\n",
    "\n",
    "> Give a $\\Theta(n)$-time nonrecursive procedure that reverses a singly linked list of $n$ elements. The procedure should use no more than constant storage beyond that needed for the list itself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkListNode:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "def to_list(head):\n",
    "    values = []\n",
    "    head = head.next\n",
    "    while head is not None:\n",
    "        values.append(head.value)\n",
    "        head = head.next\n",
    "    return values\n",
    "\n",
    "\n",
    "def insert(head, x):\n",
    "    new_node = LinkListNode(x)\n",
    "    new_node.next = head.next\n",
    "    head.next = new_node\n",
    "\n",
    "\n",
    "def reverse(head):\n",
    "    prev = None\n",
    "    node = head.next\n",
    "    while node is not None:\n",
    "        next_node = node.next\n",
    "        node.next = prev\n",
    "        prev = node\n",
    "        node = next_node\n",
    "    head.next = prev"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.2-8 $\\star$\n",
    "\n",
    "> Explain how to implement doubly linked lists using only one pointer value $x.np$ per item instead of the usual two ($next$ and $prev$). Assume all pointer values can be interpreted as $k$-bit integers, and define $x.np$ to be $x.np = x.next$ XOR $x.prev$, the $k$-bit \"exclusive-or\" of $x.next$ and $x.prev$. (The value NIL is represented by 0.) Be sure to describe what information you need to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in $O(1)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$head.np = next$\n",
    "\n",
    "$tail.np = prev$\n",
    "\n",
    "$next = x.np$ XOR $prev$\n",
    "\n",
    "$prev = x.np$ XOR $next$\n",
    "\n",
    "Reverse:\n",
    "\n",
    "$head.np.np = (head$ XOR $head.np.np)$ XOR $tail$\n",
    "\n",
    "$tail.np.np = (tail$ XOR $tail.np.np)$ XOR $head$\n",
    "\n",
    "$head.np, tail.np = tail.np, head.np$"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}