Python Data Structures -- Linked Lists _ 2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "46bc6752-ddbf-495a-ac8f-af259c928ff0",
   "metadata": {},
   "source": [
    "# LinkedIn Learning\n",
    "# Python Data Structures -- Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2bdaa77-898c-41f3-87bd-c377fba616c7",
   "metadata": {},
   "source": [
    "## 3. Variations on a Theme"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8739c57d-67f1-4953-9d4e-9c51b4c57f69",
   "metadata": {},
   "source": [
    "### A. Circular Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1f450650-4396-468b-a726-9e70a1716e3a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(2000)\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "    def search(self, data):\n",
    "        if self.data == data:\n",
    "            return True\n",
    "        if self.next:\n",
    "            return self.next.search(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "31e66b20-d019-45f2-b0f2-47f379b153b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "class LL:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def append(self, data):\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "            return \n",
    "        \n",
    "        current = self.head\n",
    "        while current.next:\n",
    "            current = current.next\n",
    "        current.next = new_node\n",
    "\n",
    "    def search(self, data):\n",
    "        current = self.head\n",
    "        while current:\n",
    "            if current.data == data:\n",
    "                return True\n",
    "            current = current.next\n",
    "        return False\n",
    "\n",
    "    def delete(self, data):\n",
    "        if not self.head:\n",
    "            return \n",
    "        if self.head.data == data:\n",
    "            self.head = self.head.next\n",
    "            return \n",
    "\n",
    "        current = self.head\n",
    "        while current.next:\n",
    "            # stuff here\n",
    "            if current.next.data == data:\n",
    "                current.next = current.next.next\n",
    "                return\n",
    "            current = current.next\n",
    "            \n",
    "    def insert(self, data):\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "            return\n",
    "        if self.head.data > data:\n",
    "            self.head = new_node\n",
    "            return\n",
    "\n",
    "        current = self.head\n",
    "        while current.next and current.next.data < data:\n",
    "            current = current.next\n",
    "        new_node.next = current.next\n",
    "        current.next = new_node\n",
    "\n",
    "    def print(self):\n",
    "        output = []\n",
    "        current = self.head\n",
    "        while current:\n",
    "            output.append(str(current.data))\n",
    "            current = current.next\n",
    "        print('->'.join(output))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "421287ae-c373-4ae8-b1ca-baeb1249472a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class CLL:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "\n",
    "    def append(self, data):\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "            self.tail = self.head\n",
    "            self.head.next = self.head\n",
    "            return\n",
    "\n",
    "        self.tail.next = new_node\n",
    "        new_node.next = self.head\n",
    "        self.tail = new_node\n",
    "\n",
    "    def print(self):\n",
    "        if not self.head:\n",
    "            return\n",
    "        output = []\n",
    "\n",
    "        current = self.head\n",
    "        while current.next != self.head:\n",
    "            output.append(str(current.data))\n",
    "            current = current.next\n",
    "\n",
    "        output.append(str(self.tail.data))\n",
    "        print('->'.join(output) + '-> ... ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b10c3a85-c105-4373-83c8-9155975369b3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2->1->7->9->3->8->5->0->6->4-> ... \n"
     ]
    }
   ],
   "source": [
    "elements = [0,1,2,3,4,5,6,7,8,9]\n",
    "random.shuffle(elements)\n",
    "cll = CLL()\n",
    "for e in elements:\n",
    "    cll.append(e)\n",
    "cll.print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97c44331-751f-4913-a9bc-230d5dfa58d8",
   "metadata": {},
   "source": [
    "### B. Doubly Linked Lists (DLL)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "eba4ef16-a18f-475e-aab3-6b57c7a4d1ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "class DNode:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "        self.prev = None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "7dbd82e0-3a88-4b12-8be6-4c2fc4f64953",
   "metadata": {},
   "outputs": [],
   "source": [
    "class LL:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def append(self, data):\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "            return \n",
    "        \n",
    "        current = self.head\n",
    "        while current.next:\n",
    "            current = current.next\n",
    "        current.next = new_node\n",
    "\n",
    "    def search(self, data):\n",
    "        current = self.head\n",
    "        while current:\n",
    "            if current.data == data:\n",
    "                return current\n",
    "            current = current.next\n",
    "        return None\n",
    "\n",
    "    def delete(self, data):\n",
    "        if not self.head:\n",
    "            return \n",
    "        if self.head.data == data:\n",
    "            self.head = self.head.next\n",
    "            return \n",
    "\n",
    "        current = self.head\n",
    "        while current.next:\n",
    "            # stuff here\n",
    "            if current.next.data == data:\n",
    "                current.next = current.next.next\n",
    "                return\n",
    "            current = current.next\n",
    "            \n",
    "    def insert(self, data):\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "            return\n",
    "        if self.head.data > data:\n",
    "            self.head = new_node\n",
    "            return\n",
    "\n",
    "        current = self.head\n",
    "        while current.next and current.next.data < data:\n",
    "            current = current.next\n",
    "        new_node.next = current.next\n",
    "        current.next = new_node\n",
    "\n",
    "    def print(self):\n",
    "        output = []\n",
    "        current = self.head\n",
    "        while current:\n",
    "            output.append(str(current.data))\n",
    "            current = current.next\n",
    "        print('->'.join(output))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "1f8f648a-4c67-4bd8-9552-e468a2f38383",
   "metadata": {},
   "outputs": [],
   "source": [
    "class DLL(LL):\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def append(self, data):\n",
    "        new_node = DNode(data)\n",
    "        if self.head is None:\n",
    "            self.head = new_node\n",
    "            return\n",
    "        current = self.head\n",
    "        while current.next:\n",
    "            current = current.next\n",
    "        current.next = new_node\n",
    "        new_node.prev = current"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "543edff2-6145-4469-baee-539bd10fe7e6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0->1->2->3->4->5->6->7->8->9\n"
     ]
    }
   ],
   "source": [
    "elements = [0,1,2,3,4,5,6,7,8,9]\n",
    "dll = DLL()\n",
    "for e in elements:\n",
    "    dll.append(e)\n",
    "dll.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "8e6fc2d3-2bf9-4d77-a6c4-2a160cd32cf3",
   "metadata": {},
   "outputs": [],
   "source": [
    "class DLL(LL):\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def append(self, data):\n",
    "        new_node = DNode(data)\n",
    "        if self.head is None:\n",
    "            self.head = new_node\n",
    "            return\n",
    "        current = self.head\n",
    "        while current.next:\n",
    "            current = current.next\n",
    "        current.next = new_node\n",
    "        new_node.prev = current\n",
    "\n",
    "    def delete(self, data):\n",
    "        node = self.search(data)\n",
    "        if not node:\n",
    "            return\n",
    "        if node == self.head:\n",
    "            self.head = self.head.next\n",
    "            return\n",
    "        if node.prev:\n",
    "            node.prev.next = node.next\n",
    "        if node.next:\n",
    "            node.next.prev = node.prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "9019760f-e1a6-49b5-905d-20adc7705055",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0->1->2->3->4->5->6->7->8->9\n",
      "1->2->3->4->6->7->8\n"
     ]
    }
   ],
   "source": [
    "elements = [0,1,2,3,4,5,6,7,8,9]\n",
    "dll = DLL()\n",
    "for e in elements:\n",
    "    dll.append(e)\n",
    "dll.print()\n",
    "\n",
    "dll.delete(0)\n",
    "dll.delete(5)\n",
    "dll.delete(9)\n",
    "dll.print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1350ef90-71d3-41a6-93ee-a1cfb59dba4c",
   "metadata": {},
   "source": [
    "### C. Orthogonal Linked Lists (OLL)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02e92999-36a3-43e6-8747-806aa7f4197d",
   "metadata": {},
   "source": [
    "#### Orthogonal Linked Lists Node\n",
    "#### (ONode) Attributes\n",
    "##### Data\n",
    "##### Row\n",
    "##### Col\n",
    "##### Down\n",
    "##### Right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "65a382f8-2a22-4283-a351-cbefc5d0f633",
   "metadata": {},
   "outputs": [],
   "source": [
    "class ONode:\n",
    "    def __init__(self, data, row, col):\n",
    "        self.data = data\n",
    "        self.row = row\n",
    "        self.col = col\n",
    "        self.down = None\n",
    "        self.right = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "0109ff0c-33dc-40d7-beb4-cf62302ab794",
   "metadata": {},
   "outputs": [],
   "source": [
    "class OLL:\n",
    "    def __init__(self, rows, cols):\n",
    "        self.row_head = [ONode(None, i, -1) for i in range(0, rows)]\n",
    "        self.col_head = [ONode(None, -1, i) for i in range(0, cols)]\n",
    "        \n",
    "    def insert(self, new_node):\n",
    "        current = self.row_head[new_node.row]\n",
    "        while current.right and current.right.col < new_node.col:\n",
    "            current = current.right\n",
    "        new_node.right = current.right\n",
    "        current.right = new_node\n",
    "\n",
    "        current = self.col_head[new_node.col]\n",
    "        while current.down and current.down.row < new_node.row:\n",
    "            current = current.down\n",
    "        new_node.down = current.down\n",
    "        current.down = new_node\n",
    "\n",
    "    def print(self):\n",
    "        for row in self.row_head:\n",
    "            output = ['0'] * len(self.col_head)\n",
    "            current = row\n",
    "            while current.right:\n",
    "                current = current.right\n",
    "                output[current.col] = str(current.data)\n",
    "\n",
    "            print(' '.join(output))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "7396a8ca-7cd0-49de-b86e-212d84568bcb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 0 0 0 4\n",
      "0 0 2 0 0\n",
      "0 1 0 0 0\n",
      "0 0 0 0 0\n"
     ]
    }
   ],
   "source": [
    "#  3 0 0 0 4\n",
    "#  0 0 2 0 0\n",
    "#  0 1 0 0 0\n",
    "#  0 0 0 0 0\n",
    "# OLL(row, col)\n",
    "\n",
    "oll = OLL(4,5)\n",
    "oll.insert(ONode(3,0,0))\n",
    "oll.insert(ONode(4,0,4))\n",
    "oll.insert(ONode(2,1,2))\n",
    "oll.insert(ONode(1,2,1))\n",
    "\n",
    "oll.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d09c51e3-ab89-42df-8784-31e20500ebad",
   "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.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}