LinkedLists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked Lists\n",
    "- https://opendsa-server.cs.vt.edu/ODSA/Books/CS2/html/ListLinked.html\n",
    "\n",
    "### Table of Contents\n",
    "- **[Introduction](#intro)**<br>\n",
    "- **[Singly Linked List](#singly)**<br>\n",
    "- **[Implementation of Node](#node)**<br>\n",
    "- **[Operations on Linked List](#operations)**<br>\n",
    "- **[Linked List as ADT](#adt)**<br>\n",
    "- **[Array-based Vs Linked List](#arrayvslinked)**<br>\n",
    "\n",
    "## Introduction\n",
    "- fundamentally different way of storing a large collection of data as list\n",
    "- consists of list of nodes connected (\"linked\") together via pointers\n",
    "- uses dynamic memory allocation\n",
    "    - allocates memory for new list element/node as needed\n",
    "- commonly two types: \n",
    "    1. singly linked list ([STL forward_list](https://en.cppreference.com/w/cpp/container/forward_list))\n",
    "    2. [doubly linked list (STL list)](./DoublyLinkedLists.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Singly Linked List\n",
    "- also called one-way list\n",
    "- each node is depicted with two boxes (members) each holding:\n",
    "    1. data (left box)\n",
    "    2. address/pointer to the next node in the list (right box)\n",
    "    \n",
    "<img src=\"./resources/linkedlist1.png\">\n",
    "\n",
    "- diagonal slash (see last node) represents NULL pointer meaning it's not pointing to another node\n",
    "- head or first is a special pointer pointing to the first (header) node\n",
    "- tail or last is a special pointer pointing to the last (trailer) node\n",
    "- use pointer to traverse through the linked list (unlike index in array-based list)\n",
    "\n",
    "<img src=\"./resources/linkedlist2.png\">\n",
    "\n",
    "- inserting and deleting node are common operations but need to deal with many cases.\n",
    "    - see visualization at: https://opendsa-server.cs.vt.edu/ODSA/Books/CS2/html/ListLinked.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implemenation of Node\n",
    "- since a node is a complex type with data (of various type) and a pointer, we use struct or class to implement it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "struct Int_Node {\n",
    "    int data; // int data\n",
    "    Int_Node * next; // address of the next node\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "// better implementation\n",
    "template <class T>\n",
    "struct Node {\n",
    "    T data; // data of some type T\n",
    "    Node<T> * next;\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "// linked list of: 10 -> 20 -> 30\n",
    "#include <iostream>\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating a linked list\n",
    "- add elements 10, 20, 30, etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "Int_Node *head, *tail, *temp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "// empty linked list\n",
    "head = tail = NULL;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Push Back Element\n",
    "- inserting element at the end of the linked list\n",
    "- algorithm steps:\n",
    "    1. create a new node with data\n",
    "    - handle special case where linked list is empty\n",
    "    - make tail->next point to new node\n",
    "    - make tail point to the new node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "@0x7ffee81618d0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// create and add the first node\n",
    "temp = new Int_Node;\n",
    "temp->data = 10;\n",
    "temp->next = NULL;\n",
    "\n",
    "// list is empty so far so add the first node\n",
    "head = temp; //update head\n",
    "tail = temp; // update tail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "//push_back more elements\n",
    "temp = new Int_Node;\n",
    "temp->data = 20;\n",
    "temp->next = NULL;\n",
    "\n",
    "tail->next = temp;\n",
    "// update tail\n",
    "tail = temp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "//push_back more elements\n",
    "temp = new Int_Node;\n",
    "temp->data = 30;\n",
    "temp->next = NULL;\n",
    "\n",
    "tail->next = temp;\n",
    "// update tail\n",
    "tail = temp;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Traversing Linked List\n",
    "- visiting every node of the linked list\n",
    "    - access data, check and or update data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "void traverse(Int_Node *head) { // start from head and go through every node\n",
    "    Int_Node * curr = head;\n",
    "    cout << \"[\";\n",
    "    while (curr != NULL) {\n",
    "        cout << \" \" << curr->data;\n",
    "        curr = curr->next;\n",
    "    }\n",
    "    cout << \" ]\";\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 10 20 30 ]"
     ]
    }
   ],
   "source": [
    "traverse(head);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualize Push Back using pythontutor.com: https://goo.gl/iQ8xJH"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Push Front Element\n",
    "- inserting element at the beginning of the linked list\n",
    "- algorithm steps:\n",
    "    1. create a new node with data\n",
    "    - make new node->next point to the head\n",
    "    - update head to point to the new node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "// insert a new node at the beginning (push_front)\n",
    "temp = new Int_Node;\n",
    "temp->data = 200;\n",
    "temp->next = head;\n",
    "\n",
    "head = temp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 200 10 20 30 ]"
     ]
    }
   ],
   "source": [
    "traverse(head);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "// insert a new node at the beginning (push_front)\n",
    "temp = new Int_Node;\n",
    "temp->data = 100;\n",
    "temp->next = head;\n",
    "\n",
    "head = temp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 100 200 10 20 30 ]"
     ]
    }
   ],
   "source": [
    "traverse(head);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualize Push Front using pythontutor.com: https://goo.gl/Qnq51b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked List Remove\n",
    "- remove an element/node from the linked list\n",
    "- algorithm steps:\n",
    "    1. use two pointers, previous and current\n",
    "        - current is the node that needs to be deleted if found\n",
    "        - previous is the node right before current\n",
    "    2. if node is found delete it\n",
    "        - update the linked list\n",
    "    - if head is deleted, update head\n",
    "    - if tail is deleted, update tail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "Int_Node * curr;\n",
    "Int_Node * pre;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "// delete 2nd node from the list\n",
    "curr = head->next;\n",
    "pre = head;\n",
    "pre->next = curr->next;\n",
    "delete curr;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 100 10 20 30 ]"
     ]
    }
   ],
   "source": [
    "traverse(head);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked List Insert\n",
    "- insert an element/node after certain node in the linked list\n",
    "- algorithm steps:\n",
    "    1. create a new node\n",
    "    - find the location where the new node needs to be inserted\n",
    "    - insert the new node at that location\n",
    "    - if the new node is inserted at the beginning, update head\n",
    "    - if the new node is inserted at the end, update tail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "@0x7ffee81618d0"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// insert element as the 2nd node (after the first node) with key value 100\n",
    "temp = new Int_Node;\n",
    "temp->data = 200;\n",
    "temp->next = NULL;\n",
    "curr = head; // pointing to the first node\n",
    "temp->next = curr->next;\n",
    "curr->next = temp; // insert temp after current"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 100 200 10 20 30 ]"
     ]
    }
   ],
   "source": [
    "traverse(head);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Detect and remove cycle from a linked list \n",
    "- let's say the next of some node points to some earlier nodes creating a cycle (by error)\n",
    "- determine if the linked list has a cycle\n",
    "- return 1 if there's a cycle; 0 otherwise\n",
    "- use unordered_set to keep track of visited node's addresses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# include <unordered_set>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "int detectAndRemoveCycle(Int_Node * head) {\n",
    "    Int_Node * last = nullptr;\n",
    "    unordered_set< Int_Node* > visited;\n",
    "    bool cycle = false;\n",
    "    while (!cycle && head != nullptr) {\n",
    "        // if the node is not in visited set, add it into the set\n",
    "        if (visited.find(head) == visited.end()) {\n",
    "            visited.insert(head);\n",
    "            last = head;\n",
    "            head = head->next;\n",
    "        }\n",
    "        else {\n",
    "            cycle = true;\n",
    "            last->next = nullptr;\n",
    "        }\n",
    "    }\n",
    "    return cycle?1:0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30"
     ]
    }
   ],
   "source": [
    "// test detectAndRemoveCycle by adding a cycle\n",
    "cout << tail->data;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10"
     ]
    }
   ],
   "source": [
    "tail->next = head->next->next;\n",
    "// not there's a cycle\n",
    "cout << tail->next->data;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1"
     ]
    }
   ],
   "source": [
    "cout << detectAndRemoveCycle(head);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 100 200 10 20 30 ]"
     ]
    }
   ],
   "source": [
    "traverse(head);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A Better Approach to Represent Linked List\n",
    "- insert and delete algorithms stated above have many special cases to worry about\n",
    "    - makes it harder to understand, and increases the chance of introducing bugs\n",
    "- many special cases can be eliminated if **header node** and **trailer node** are used\n",
    "    - these nodes do not store actual data/value\n",
    "- the following diagram shows empty linked list with header and trailer nodes\n",
    "<img src=\"./resources/betterLinkedList1.png\">\n",
    "- the following diagram shows linked lists with some nodes with data, header and trailer nodes\n",
    "<img src=\"./resources/betterLinkedList2.png\">\n",
    "\n",
    "## Remove\n",
    "- algorithm steps to remove a node\n",
    "    1. find the node to be deleted\n",
    "    - delete the node\n",
    "    \n",
    "## Insert\n",
    "- algorithm steps to insert an element after certain node\n",
    "    1. find the node to insert after\n",
    "    2. insert new node after the node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked List Implementation as ADT\n",
    "- following Linked list as ADT works for integer data\n",
    "- it can be easily converted into template class\n",
    "    - this is left as an exercise"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <sstream>\n",
    "#include <cassert>\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "struct Int_Node {\n",
    "    int data; // int data\n",
    "    Int_Node * next; // address of the next node\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "class IntLinkedList {\n",
    "    private:\n",
    "        Int_Node * head; // pointer to the header node\n",
    "        Int_Node * tail; // pointer to the trailer node\n",
    "        size_t nodeCount; // keep track of number of nodes\n",
    "        \n",
    "    public:\n",
    "        IntLinkedList() {\n",
    "            this->nodeCount = 0;\n",
    "            Int_Node *temp = new Int_Node;\n",
    "            temp->data = 0;\n",
    "            temp->next = nullptr;\n",
    "            this->head = temp;\n",
    "            temp = new Int_Node;\n",
    "            temp->data = 0;\n",
    "            temp->next = nullptr;\n",
    "            this->tail = temp;\n",
    "            \n",
    "            // link head with tail\n",
    "            this->head->next = this->tail;\n",
    "        }\n",
    "    \n",
    "        bool empty() const {\n",
    "            return this->nodeCount == 0;\n",
    "        }\n",
    "    \n",
    "        // adds an element to the end (insert end)\n",
    "        void push_back(int data) {\n",
    "            Int_Node * node = new Int_Node;\n",
    "            node->data = 0;\n",
    "            node->next = NULL;\n",
    "            \n",
    "            this->tail->data = data; // update trailer node's data\n",
    "            this->tail->next = node; // link new node at the end\n",
    "            this->tail = node; // make new node the trailer node\n",
    "            \n",
    "            this->nodeCount++;\n",
    "        }\n",
    "    \n",
    "        // inserts an element to the beginning\n",
    "        void push_front(int data) {\n",
    "            // FIXME\n",
    "        }\n",
    "        \n",
    "        // return the size of the list\n",
    "        size_t size() {\n",
    "            return this->nodeCount;\n",
    "        }\n",
    "    \n",
    "        // access the first element\n",
    "        // FIXME - implement method to access the data in first node\n",
    "    \n",
    "        // return string representation of linked list\n",
    "        string toString() {\n",
    "            stringstream ss;\n",
    "            ss << \"[\";\n",
    "            Int_Node * curr = head->next; // ignore header\n",
    "            while (curr != tail) { // stop before trailer\n",
    "                ss << \" \" << curr->data;\n",
    "                curr = curr->next;\n",
    "            }\n",
    "            ss << \" ]\";\n",
    "            return ss.str();\n",
    "        }\n",
    "        \n",
    "    \n",
    "        // remove node with given key\n",
    "        void remove(int key) {\n",
    "            assert(!empty());\n",
    "            Int_Node *curr = head; //start from header node\n",
    "            bool found = false;\n",
    "            while (curr->next != tail) {\n",
    "                if (curr->next->data == key) {\n",
    "                    found = true;\n",
    "                    break;\n",
    "                }\n",
    "                curr = curr->next;\n",
    "            }\n",
    "            if (found) {\n",
    "                // node found delete it\n",
    "                Int_Node *node = curr->next; //copy curr->next to properly delete it\n",
    "                // point around unneeded node\n",
    "                curr->next = curr->next->next;\n",
    "                delete node;\n",
    "                this->nodeCount--;\n",
    "            }\n",
    "        }\n",
    "        \n",
    "    \n",
    "        // insert a node with a given data after the node with the after_key value\n",
    "        // if the element with after_key not found, insert data at the end\n",
    "        void insert_after(int after_key, int data) {\n",
    "            // FIXME\n",
    "        }\n",
    "\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "// test IntLinkedList with some data\n",
    "IntLinkedList ilist;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ ]"
     ]
    }
   ],
   "source": [
    "cout << ilist.toString();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 10 ]"
     ]
    }
   ],
   "source": [
    "ilist.push_back(10);\n",
    "cout << ilist.toString();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 10 20 30 ]"
     ]
    }
   ],
   "source": [
    "ilist.push_back(20);\n",
    "ilist.push_back(30);\n",
    "cout << ilist.toString();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linkedlist has 3 nodes.\n"
     ]
    }
   ],
   "source": [
    "cout << \"Linkedlist has \" << ilist.size() << \" nodes.\" << endl;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 10 30 ]"
     ]
    }
   ],
   "source": [
    "ilist.remove(20);\n",
    "cout << ilist.toString();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Array-based List Vs Linked List\n",
    "### Disadvantages of array-based lists\n",
    "- list size must be predetermined before the array can be allocated\n",
    "- list cannot grow beyond their predetermined size\n",
    "- memory is potentially wasted if array is not completely filled\n",
    "- insertion operation requires shifting elements down (at most $O(n)$ operations in the worst case)\n",
    "- deletion operation requires shifting elements up (at most $O(n)$ operations in the worst case)\n",
    "\n",
    "### Advantages of linked lists\n",
    "- list size must not be known before hand\n",
    "- list can grow dynamically as more data need to be stored\n",
    "- no over allocating space and waste of memory\n",
    "- if pointer is predetermined, insertion and deletion takes constant time $O(1)$ operation\n",
    "\n",
    "### Advantages of array-based lists\n",
    "- no extra space is required to store pointer in each node\n",
    "- better suited if the size of the data is known and array is guaranteed to be filled\n",
    "- provides random access to data via index\n",
    "\n",
    "### Disadvantages of linked lists\n",
    "- memory overhead for storing pointer in each node\n",
    "- no random access to data is possible... must traverse the list to access elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises\n",
    "1. In a linked list, the successive elements in the list:\n",
    "    1. Need not occupy contiguous space in memory\n",
    "    - Must not occupy contiguous space in memory\n",
    "    - Must occupy contiguous space in memory\n",
    "    - None of the above\n",
    "    \n",
    "2. Fix all the FIXMEs of Singly Linked List ADT above and test the fixes\n",
    "3. Convert Singly Linked List ADT to a template class to store data of any type in the node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}