Insertion sort on singly- and doubly-linked list

linkedlistinsertionsort.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "LinkedListInsertionSort.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyNqlxX1K3DZ4lpBmeZJEX5E",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/ibeauregard/0b42b42f60be7042484b3439dfa3d6ae/linkedlistinsertionsort.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WTW7lPdVvOFg"
      },
      "source": [
        "# Insertion sort of a linked list"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xIaG_aWsjc2e"
      },
      "source": [
        "Here is some minimal code to demonstrate insertion sort on both a singly-linked list and a doubly-linked list."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "q_cId2Kxv1Hc"
      },
      "source": [
        "from random import randint\n",
        "from abc import ABC, abstractmethod"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "num9RIspiXYE"
      },
      "source": [
        "## Abstract base class for a linked list node"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "julcok0TibjG"
      },
      "source": [
        "class LinkedListNode(ABC):\n",
        "    def __init__(self, val, next=None):\n",
        "        self.val = val\n",
        "        self.next = next\n",
        "\n",
        "    @abstractmethod\n",
        "    def __repr__(self):\n",
        "        pass\n",
        "    \n",
        "    def link_to(self, next_node):\n",
        "        self.next = next_node\n",
        "\n",
        "    def insert_after(self, pre_insertion):\n",
        "        post_insertion = pre_insertion.next\n",
        "        pre_insertion.link_to(self)\n",
        "        self.link_to(post_insertion)"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uhrFv-ySilhs"
      },
      "source": [
        "## Derived classes for linked list nodes"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "x8Rk_Ru0ik8F"
      },
      "source": [
        "class SinglyLinkedListNode(LinkedListNode):\n",
        "    def __repr__(self):\n",
        "        return f\"{self.val} => \""
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "L6LsNRtKjGc9"
      },
      "source": [
        "class DoublyLinkedListNode(LinkedListNode):\n",
        "    def __init__(self, val, prev=None, next=None):\n",
        "        super().__init__(val, next)\n",
        "        self.prev = prev\n",
        "    \n",
        "    def __repr__(self):\n",
        "        return f\"< {self.val} >\"        \n",
        "\n",
        "    def link_to(self, next_node):\n",
        "        super().link_to(next_node)\n",
        "        if next_node is not None:\n",
        "            next_node.prev = self"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-RUGN_BrjWbt"
      },
      "source": [
        "## Abstract base class for a linked list"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "esYkT7V4jV5V"
      },
      "source": [
        "class LinkedList(ABC):\n",
        "    def __init__(self, head):\n",
        "        self.head = head\n",
        "\n",
        "    def __repr__(self):\n",
        "        repr = []\n",
        "        node = self.head\n",
        "        while node is not None:\n",
        "            repr.append(node.__repr__())\n",
        "            node = node.next\n",
        "        return ''.join(repr)\n",
        "    \n",
        "    @classmethod\n",
        "    def generate_random(cls, *, num_nodes):\n",
        "        dummy = cls.Node(None)\n",
        "        node = dummy\n",
        "        for i in range(num_nodes):\n",
        "            new_node = cls.Node(randint(0, 999))\n",
        "            node.link_to(new_node)\n",
        "            node = new_node\n",
        "        return cls(dummy.next)\n",
        "\n",
        "    def insertion_sort(self):\n",
        "        dummy_head = self.Node(None)\n",
        "        def insert(node):\n",
        "            pre_insertion = dummy_head\n",
        "            while pre_insertion.next is not None and pre_insertion.next.val < node.val:\n",
        "                pre_insertion = pre_insertion.next\n",
        "            node.insert_after(pre_insertion)\n",
        "        \n",
        "        node = self.head\n",
        "        while node is not None:\n",
        "            next_node = node.next\n",
        "            insert(node)\n",
        "            node = next_node\n",
        "        self.head = dummy_head.next\n",
        "        return self"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eG-oAudokGxz"
      },
      "source": [
        "## Derived classes for linked lists"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "19kQoDvpkJSl"
      },
      "source": [
        "class SinglyLinkedList(LinkedList):\n",
        "    Node = SinglyLinkedListNode"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VcBUAPFakJkU"
      },
      "source": [
        "class DoublyLinkedList(LinkedList):\n",
        "    Node = DoublyLinkedListNode"
      ],
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZJT5PNIizeME"
      },
      "source": [
        "## Demonstrations"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "dQyl2Ybtvq5p",
        "outputId": "70bb3611-94af-4327-a19e-db9304f2f28c"
      },
      "source": [
        "singly_linked_list = SinglyLinkedList.generate_random(num_nodes=20)\n",
        "singly_linked_list.insertion_sort()"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "250 => 270 => 284 => 323 => 497 => 512 => 517 => 545 => 596 => 611 => 642 => 702 => 785 => 829 => 941 => 953 => 956 => 963 => 988 => 988 => "
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_SuWGkCTB1g9",
        "outputId": "77049e84-8374-4d93-cdea-273f4170c6e5"
      },
      "source": [
        "doubly_linked_list = DoublyLinkedList.generate_random(num_nodes=20)\n",
        "doubly_linked_list.insertion_sort()"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "< 6 >< 86 >< 115 >< 187 >< 198 >< 330 >< 409 >< 418 >< 504 >< 534 >< 553 >< 664 >< 679 >< 696 >< 696 >< 789 >< 883 >< 947 >< 948 >< 974 >"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 9
        }
      ]
    }
  ]
}