CircularDoublyLinkedList_cpp.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Circular Doubly Linked List\n",
    "[**ctrl + Click here**](https://mybinder.org/v2/gh/abhiyantaabhishek/algorithm/master?filepath=CircularDoublyLinkedList_cpp.ipynb) to run this code live in the Jupyetr Notebook. _Please don't click if you are already there in the Jupyter Notebook as it will create a new kernel._"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <assert.h> \n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "template <class T>\n",
    "struct node\n",
    "{\n",
    "    T data;\n",
    "    struct node<T> *prev;\n",
    "    struct node<T> *next;\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "template <class T>\n",
    "class CircularDoublyLinkedList\n",
    "{\n",
    "public:\n",
    "    struct node<T> * mHead;\n",
    "    struct node<T> * mTail;\n",
    "    CircularDoublyLinkedList()\n",
    "    {\n",
    "        mHead = NULL;\n",
    "        mTail = NULL;\n",
    "    }\n",
    "\n",
    "    void insertStart(T data);\n",
    "    void deleteStart( );\n",
    "    void insertEnd( T data);\n",
    "    void deleteEnd();\n",
    "    void insertPos(T data, int pos);\t\t// insert any position except start and end;\n",
    "    void deletePos( int pos);\t\t\t\t// delete any position except start and end;\n",
    "    void insertAnyPos( T data, int pos);\t// insert any position including start and end;\n",
    "    void deleteAnyPos( int pos);\t\t\t// delete any position including start and end;\n",
    "    void display();\n",
    "\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "template<class T>\n",
    "void CircularDoublyLinkedList<T> ::insertStart(T data)\n",
    "{\n",
    "    struct node<T> * newNode = new node<T>;\n",
    "    newNode->data = data;\n",
    "    if (mHead == NULL && mTail == NULL)\n",
    "    {\n",
    "        newNode->next = newNode;\n",
    "        newNode->prev = newNode;\n",
    "        mHead = newNode;\n",
    "        mTail = newNode;\n",
    "    }\n",
    "    else if (mHead != NULL)\n",
    "    {\n",
    "        newNode->next = mHead;\n",
    "        newNode->prev = mTail;\n",
    "        mHead->prev = newNode;\n",
    "        mTail->next = newNode;\n",
    "        mHead = newNode;\n",
    "    }\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "template<class T>\n",
    "void CircularDoublyLinkedList<T> ::deleteStart()\n",
    "{\n",
    "    struct node<T> * toDel = mHead;\n",
    "    if (toDel != NULL)\n",
    "    {\n",
    "        if (mHead == mTail) // onely one element to del\n",
    "        {\n",
    "            mHead = NULL;\n",
    "            mTail = NULL;\n",
    "            delete toDel;\n",
    "        }\n",
    "        else\n",
    "        {\n",
    "            mTail->next = mHead->next;\n",
    "            mHead = mHead->next;\n",
    "            mHead->prev = mTail;\n",
    "            delete toDel;\n",
    "        }\n",
    "\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "        cout << \"\\nCan not delete from empty List\";\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "template <class T>\n",
    "void CircularDoublyLinkedList<T> ::insertEnd(T data)\n",
    "{\n",
    "    struct node<T> *newNode = new node < T > ;\n",
    "    newNode->data = data;\n",
    "    if (mHead == NULL && mTail == NULL)\n",
    "    {\n",
    "        newNode->next = newNode;\n",
    "        newNode->prev = newNode;\n",
    "        mHead = newNode;\n",
    "        mTail = newNode;\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "        newNode->prev = mTail;\n",
    "        newNode->next = mHead;\n",
    "        mHead->prev = newNode;\n",
    "        mTail->next = newNode;\n",
    "        mTail = newNode;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "template<class T>\n",
    "void CircularDoublyLinkedList<T> ::deleteEnd()\n",
    "{\n",
    "    if (mHead != NULL && mTail != NULL)\n",
    "    {\n",
    "        struct node<T> * toDel = mTail;\n",
    "        if (mHead == mTail) // onely one element to del\n",
    "        {\n",
    "            mHead = NULL;\n",
    "            mTail = NULL;\n",
    "            delete toDel;\n",
    "        }\n",
    "        else\n",
    "        {\n",
    "            mHead->prev = mTail->prev;\n",
    "            mTail->prev->next = mHead;\n",
    "            mTail = mTail->prev;\n",
    "            delete toDel;\n",
    "        }\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "        cout << \"\\nCan't delete from empty list\";\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "template<class T>\n",
    "void CircularDoublyLinkedList<T> ::insertPos(T data, int pos)\n",
    "{\n",
    "    struct node<T> * newNode = new node < T > ;\n",
    "    newNode->data = data;\n",
    "    struct node<T> * currNode = mHead;\n",
    "    struct node<T> * prevNode = mTail;\n",
    "    int iter = 1;\n",
    "    for (iter = 1; iter <=pos; iter++)\n",
    "    {\n",
    "        prevNode = currNode;\n",
    "        currNode = currNode->next;\n",
    "    }\n",
    "    newNode->next = currNode;\n",
    "    newNode->prev = prevNode;\n",
    "    currNode->prev = newNode;\n",
    "    prevNode->next = newNode;\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "template<class T>\n",
    "void CircularDoublyLinkedList<T> ::deletePos(int pos)\n",
    "{\n",
    "\n",
    "    struct node<T> * currNode = mHead;\n",
    "    struct node<T> * prevNode = mTail;\n",
    "    int iter = 1;\n",
    "    for (iter = 1; iter <= pos; iter++)\n",
    "    {\n",
    "        prevNode = currNode;\n",
    "        currNode = currNode->next;\n",
    "    }\n",
    "    prevNode->next = currNode->next;\n",
    "    currNode->next->prev = currNode->prev;\n",
    "    delete currNode;\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "template<class T>\n",
    "void CircularDoublyLinkedList<T> ::insertAnyPos(T data, int pos)\n",
    "{\n",
    "    int overflow = 0;\n",
    "    struct node<T> * newNode = new node < T >;\n",
    "    newNode->data = data;\n",
    "    struct node<T> * currNode = mHead;\n",
    "    struct node<T> * prevNode = mTail;\n",
    "    int iter = 1;\n",
    "    if (pos >= 0)\n",
    "    {\n",
    "        for (iter = 0; iter < pos; iter++)\n",
    "        {\n",
    "            if (currNode == mHead && iter!=0)\n",
    "            {\n",
    "                overflow = 1;\n",
    "                cout << \"cant not insert at doscontinuous  position\";\n",
    "                break;\n",
    "            }\n",
    "            prevNode = currNode;\n",
    "            currNode = currNode->next;\n",
    "        }\n",
    "        if (overflow == 0)\n",
    "        {\n",
    "            if (iter == 0)\n",
    "            {\n",
    "                if (mHead == NULL && mTail == NULL)\n",
    "                {\n",
    "                    newNode->next = newNode;\n",
    "                    newNode->prev = newNode;\n",
    "                    mHead = newNode;\n",
    "                    mTail = newNode;\n",
    "                }\n",
    "                else if (mHead != NULL)\n",
    "                {\n",
    "                    newNode->next = currNode;\n",
    "                    newNode->prev = prevNode;\n",
    "                    currNode->prev = newNode;\n",
    "                    prevNode->next = newNode;\n",
    "                    mHead = newNode;\n",
    "                }\n",
    "            }\n",
    "            if (currNode->next == mHead)\n",
    "            {\n",
    "                if (mHead == NULL && mTail == NULL)\n",
    "                {\n",
    "                    newNode->next = newNode;\n",
    "                    newNode->prev = newNode;\n",
    "                    mHead = newNode;\n",
    "                    mTail = newNode;\n",
    "                }\n",
    "                else\n",
    "                {\n",
    "                    newNode->next = currNode;\n",
    "                    newNode->prev = prevNode;\n",
    "                    currNode->prev = newNode;\n",
    "                    prevNode->next = newNode;\n",
    "                    mTail = newNode;\n",
    "                }\n",
    "            }\n",
    "            else\n",
    "            {\n",
    "                newNode->next = currNode;\n",
    "                newNode->prev = prevNode;\n",
    "                currNode->prev = newNode;\n",
    "                prevNode->next = newNode;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "        cout << \"\\n Index can not be negative\";\n",
    "    }\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "template <class T>\n",
    "void CircularDoublyLinkedList<T> ::deleteAnyPos(int pos)\n",
    "{\n",
    "    int overflow = 0;\n",
    "    struct node<T> * toDel = NULL;\n",
    "    struct node<T> * currNode = mHead;\n",
    "    struct node<T> * prevNode = mTail;\n",
    "    int iter = 1;\n",
    "    if (pos >= 0)\n",
    "    {\n",
    "        for (iter = 0; iter < pos; iter++)\n",
    "        {\n",
    "\n",
    "            prevNode = currNode;\n",
    "            currNode = currNode->next;\n",
    "            if (currNode == mHead)\n",
    "            {\n",
    "                overflow = 1;\n",
    "                cout << \"\\nInvalid position \";\n",
    "                break;\n",
    "            }\n",
    "        }\n",
    "        if (currNode == mHead) // delete first node\n",
    "        {\n",
    "\n",
    "            if (currNode != NULL)\n",
    "            {\n",
    "                if (mHead == mTail) // onely one element to del\n",
    "                {\n",
    "                    mHead = NULL;\n",
    "                    mTail = NULL;\n",
    "                    delete currNode;\n",
    "                }\n",
    "                else\n",
    "                {\n",
    "                    prevNode->next = currNode->next;\n",
    "                    currNode->next->prev = currNode->prev;\n",
    "                    mHead = currNode->next;\n",
    "                    delete currNode;\n",
    "                }\n",
    "\n",
    "            }\n",
    "            else\n",
    "            {\n",
    "                cout << \"\\nCan not delete from empty List\";\n",
    "            }\n",
    "        }\n",
    "        else if (currNode == mTail)//delete last node\n",
    "        {\n",
    "            if (mHead != NULL && mTail != NULL)\n",
    "            {\n",
    "                struct node<T> * toDel = mTail;\n",
    "                if (mHead == mTail) // onely one element to del\n",
    "                {\n",
    "                    mHead = NULL;\n",
    "                    mTail = NULL;\n",
    "                    delete toDel;\n",
    "                }\n",
    "                else\n",
    "                {\n",
    "\n",
    "                    prevNode->next = currNode->next;\n",
    "                    currNode->next->prev = currNode->prev;\n",
    "                    mTail = currNode->prev;\n",
    "                    delete toDel;\n",
    "                }\n",
    "            }\n",
    "            else\n",
    "            {\n",
    "                cout << \"\\nCan't delete from empty list\";\n",
    "            }\n",
    "\n",
    "        }\n",
    "        else  // delete node other than first and last \n",
    "        {\n",
    "            prevNode->next = currNode->next;\n",
    "            currNode->next->prev = currNode->prev;\n",
    "            delete currNode;\n",
    "        }\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "        cout << \"\\n Index can't be negative\";\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "template<class T>\n",
    "void CircularDoublyLinkedList<T> ::display()\n",
    "{\n",
    "    struct node<T> * curr = mHead;\n",
    "    if (mHead != NULL && mTail != NULL)\n",
    "    {\n",
    "\n",
    "        do \n",
    "        {\n",
    "            cout<<curr->data<<\" \";\n",
    "            curr = curr->next;\n",
    "        } while (curr != mHead);\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "        cout << \"\\nList is empty\";\n",
    "    }\n",
    "\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "int __main()\n",
    "{\n",
    "    CircularDoublyLinkedList<int> circularDoublyLinkedList;\n",
    "    circularDoublyLinkedList.insertStart(5);\n",
    "    circularDoublyLinkedList.insertStart(6);\n",
    "    cout << \"Data : \\n\";\n",
    "    circularDoublyLinkedList.display();\n",
    "    circularDoublyLinkedList.deleteStart();\n",
    "    circularDoublyLinkedList.insertEnd(7);\n",
    "    circularDoublyLinkedList.insertEnd(8);\n",
    "    cout << \"\\nData : \\n\";\n",
    "    circularDoublyLinkedList.display();\n",
    "    circularDoublyLinkedList.deleteEnd();\n",
    "    circularDoublyLinkedList.deleteEnd();\n",
    "    circularDoublyLinkedList.deleteEnd();\n",
    "    cout << \"\\nData : \\n\";\n",
    "    circularDoublyLinkedList.display();\n",
    "    circularDoublyLinkedList.insertStart(5);\n",
    "    circularDoublyLinkedList.insertStart(6);\n",
    "    circularDoublyLinkedList.insertEnd(7);\n",
    "    circularDoublyLinkedList.insertEnd(8);\n",
    "    cout << \"\\nData : \\n\";\n",
    "    circularDoublyLinkedList.display();\n",
    "    circularDoublyLinkedList.insertPos(9, 2);\n",
    "    cout << \"\\nData : \\n\";\n",
    "    circularDoublyLinkedList.display();\n",
    "    circularDoublyLinkedList.deletePos(2);\n",
    "    cout << \"\\nData : \\n\";\n",
    "    circularDoublyLinkedList.display();\n",
    "    circularDoublyLinkedList.insertAnyPos(9, 4);\n",
    "    cout << \"\\nData : \\n\";\n",
    "    circularDoublyLinkedList.display();\n",
    "    circularDoublyLinkedList.deleteAnyPos(5);\n",
    "    cout << \"\\nData : \\n\";\n",
    "    circularDoublyLinkedList.display();\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Data : \n",
      "6 5 \n",
      "Data : \n",
      "5 7 8 \n",
      "Data : \n",
      "\n",
      "List is empty\n",
      "Data : \n",
      "6 5 7 8 \n",
      "Data : \n",
      "6 5 9 7 8 \n",
      "Data : \n",
      "6 5 7 8 \n",
      "Data : \n",
      "6 5 7 8 9 \n",
      "Invalid position \n",
      "Data : \n",
      "5 7 8 9 "
     ]
    }
   ],
   "source": [
    "__main();"
   ]
  }
 ],
 "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": 4
}