{"id":"89ac0a9e-e07d-44e4-96d5-7b136fb63657","name":"Remove Before In Doubly Linkedlist","description":"1. You are given a partially written DoublyLinkedList class.\r\n2. You are required to complete the body of removeBefore function. This function is supposed to remove value Before given Node. \r\n3. If size of list is zero then return \"ListIsEmpty: -1\".\r\n4. If Index is Invalid then return \"IndexIsInValid: -1\".\r\n5. If Location which we want to remove is null then return \"LocationIsInvalid: -1\".\r\n6. You are required to update head, tail and size as required.\r\n7. Input and Output is managed for you. Just update the code in incomplete function.\r\n\r\nNote -> Use the code snippet and follow the algorithm discussed in question video. The judge can't \r\n force you but the intention is to teach a concept. Play in spirit of the question.\r\n","inputFormat":"input in managed for you.\r\n","outputFormat":"output in managed for you.\r\n","constraints":"0 &lt;= N &lt;= 10^6\r\n","sampleCode":{"cpp":{"code":"#include<iostream>\nusing namespace std;\n#include<vector>\n\n\nclass DoublyLinkedList {\n public : class Node {\n public:\n int data = 0;\n Node* prev = nullptr;\n Node* next = nullptr;\n\n Node(int data) {\n this->data = data;\n }\n\n };\n\n Node* head = nullptr;\n Node* tail = nullptr;\n int size = 0;\n\n string toString() {\n string sb;\n Node* curr = this->head;\n sb += \"[\";\n while (curr != nullptr) {\n sb += (to_string)(curr->data);\n if (curr->next != nullptr)\n sb+=\", \";\n curr = curr->next;\n }\n sb += \"]\";\n\n return sb;\n }\n\n // Exceptions========================================\n\n private: bool indexIsInvalidException(int index, int leftRange, int rightRange) {\n if (index < leftRange || index > rightRange) {\n cout << (\"IndexIsInValid: \");\n return true;\n }\n return false;\n }\n\n\n private:bool ListIsEmptyException() {\n if (this->size == 0) {\n cout << \"ListIsEmpty: \";\n return true;\n }\n return false;\n }\n\n // BasicFunctions======================================\n\n public:int Size() {\n // write your code here\n return size;\n }\n\n public:bool isEmpty() {\n // write your code here\n\n return this->size==0;\n \n }\n\n // AddFunctions======================================\n\n public:void addFirstNode(Node* node) {\n if (this->size == 0)\n this->head = this->tail = node;\n else {\n node->next = this->head;\n this->head->prev = node;\n this->head = node;\n }\n this->size++;\n }\n\n public: void addFirst(int val) {\n Node* node = new Node(val);\n addFirstNode(node);\n }\n\n public:void addLastNode(Node* node) {\n if (this->size == 0)\n this->head = this->tail = node;\n else {\n this->tail->next = node;\n node->prev = this->tail;\n this->tail = node;\n }\n this->size++;\n }\n\n public:void addLast(int val) {\n Node* node = new Node(val);\n addLastNode(node);\n }\n\n // RemoveFunctions======================================\n\n public:Node *removeFirstNode() {\n Node* node = this->head;\n if (this->size == 1)\n this->head = this->tail = nullptr;\n else {\n Node* nextNode = this->head->next;\n nextNode->prev = nullptr;\n node->next = nullptr;\n\n this->head = nextNode;\n }\n\n this->size--;\n return node;\n }\n\n public:int removeFirst() {\n if (ListIsEmptyException())\n return -1;\n Node* node = removeFirstNode();\n return node->data;\n }\n\n public:Node* removeLastNode() {\n Node* node = this->tail;\n if (this->size == 1)\n this->head = this->tail = nullptr;\n else {\n Node* prevNode = this->tail->prev;\n prevNode->next = nullptr;\n node->prev = nullptr;\n\n this->tail = prevNode;\n }\n\n this->size--;\n return node;\n }\n\n public:int removeLast() {\n if (ListIsEmptyException())\n return -1;\n Node* node = removeLastNode();\n return node->data;\n }\n\n // getFunctions======================================\n\n public:int getFirst() {\n if(ListIsEmptyException()){\n return -1;\n }\n return head->data;\n \n }\n private: Node* getNodeAt(int index) {\n Node*curr = this->head;\n while (curr != nullptr && index-- > 0)\n curr = curr->next;\n\n return curr;\n }\n \n public:int getLast() {\n //write your code here\n if(ListIsEmptyException()){\n return -1;\n }\n return tail->data;\n }\n\n private: void addNodeAt(int index, Node* node) {\n if (index == 0)\n addFirstNode(node);\n else if (index == this->size)\n addLastNode(node);\n else {\n Node* forw = getNodeAt(index);\n Node* prev = forw->prev;\n\n prev->next = node;\n node->prev = prev;\n\n node->next = forw;\n forw->prev = node;\n\n this->size++;\n }\n }\n public : int getAt(int index){\n if(ListIsEmptyException()){\n return -1;\n }else if(indexIsInvalidException(index , 0, this->size-1)){\n return -1;\n }\n \n Node* curr = head;\n for(int i=1 ; i <= index ; i++){\n curr = curr->next;\n }\n \n return curr->data;\n \n }\n public:void addAt(int index, int data) {\n if (indexIsInvalidException(index, 0, this->size))\n cout << -1 << endl;\n else {\n Node* node = new Node(data);\n addNodeAt(index, node);\n }\n }\n private: Node* removeAtNode(int index) {\n if (index == 0)\n return removeFirstNode();\n else if (index == this->size - 1)\n return removeLastNode();\n else {\n Node* node = getNodeAt(index);\n Node* prev = node->prev;\n Node* forw = node->next;\n\n prev->next = forw;\n forw->prev = prev;\n\n node->next = nullptr;\n node->prev = nullptr;\n\n this->size--;\n return node;\n }\n }\n\n public: int removeAt(int index) {\n if (ListIsEmptyException() )\n return -1;\n\t\t\t\n \n //reason for the error, the below condition was missing\n if(indexIsInvalidException(index, 0, this->size-1)) {\n return -1;\n }\n \n Node* node = removeAtNode(index);\n return node->data;\n }\n public :void addBefore(Node* refNode, int data) {\n Node* node = new Node(data);\n Node* prev = refNode->prev;\n\n if (prev == nullptr) {\n node->next = refNode;\n refNode->prev = node;\n this->head = node;\n } else {\n prev->next = node;\n node->prev = prev;\n\n node->next = refNode;\n refNode->prev = node;\n }\n\n this->size++;\n }\n\n public: void addBefore(int idx, int data) {\n Node* node = getNodeAt(idx);\n addBefore(node, data);\n }\n\n public :void addAfter(Node* refNode, int data) {\n Node* node = new Node(data);\n Node* forw = refNode->next;\n\n if (forw == nullptr) {\n refNode->next = node;\n node->prev = refNode;\n this->tail = node;\n } else {\n forw->prev = node;\n node->next = forw;\n\n node->prev = refNode;\n refNode->next = node;\n }\n\n this->size++;\n }\n\n public: void addAfter(int idx, int data) {\n Node* node = getNodeAt(idx);\n addAfter(node, data);\n }\n \n private: Node *removeAfterNode(Node* refNode) {\n Node* forw = refNode->next;\n if (forw->next == nullptr) {\n refNode->next = nullptr;\n forw->prev = nullptr;\n this->tail = refNode;\n } else {\n refNode->next = forw->next;\n forw->next->prev = refNode;\n\n forw->next = nullptr;\n forw->prev = nullptr;\n }\n this->size--;\n return forw;\n }\n\n public: int removeAfter(Node* refNode) {\n if (refNode == nullptr || refNode->next == nullptr) {\n cout << (\"LocationIsInvalid: \") << endl;\n return -1;\n }\n return removeAfterNode(refNode)->data;\n }\n\n public :int removeAfter(int idx) {\n if(idx < 0 || idx >= this->size) {\n cout << \"LocationIsInvalid: \" << endl;\n return -1;\n }\n Node* node = getNodeAt(idx);\n return removeAfter(node);\n }\n\n public: int removeBefore(int idx) {\n // Write your code here\n }\n };\n \n\n int main() {\n DoublyLinkedList *dll = new DoublyLinkedList();\n \n string str;\n cin >> str;\n \n while(str != \"stop\"){\n int data;\n if(str == (\"addFirst\")){\n cin >> data;\n dll->addFirst(data);\n }\n else if (str == (\"addLast\")){\n cin >> data;\n dll->addLast((data));\n }\n else if (str == (\"removeFirst\"))\n cout << (dll->removeFirst()) << endl;\n else if (str == (\"removeLast\"))\n cout << (dll->removeLast()) << endl;\n else if (str == (\"getFirst\"))\n cout << (dll->getFirst()) << endl;\n else if (str == (\"getLast\"))\n cout << (dll->getLast()) << endl;\n else if (str == (\"size\"))\n cout << (dll->Size()) << endl;\n else if (str == (\"isEmpty\"))\n cout << (dll->isEmpty() == 0 ? \"false\" : \"true\") << endl;\n else if(str == (\"getAt\")){\n cin >> data;\n cout << dll->getAt(data) << endl ;\n }\n else if (str == (\"addAt\")){\n cin >> data;\n int val;\n cin >> val;\n dll->addAt(data , val);\n }\n else if (str == (\"removeAt\")){\n cin >> data;\n dll->removeAt(data);\n }\n else if (str == (\"addBefore\")){\n cin >> data;\n int val;\n cin >> val;\n dll->addBefore(data , val);\n }\n else if (str == (\"addAfter\")){\n cin >> data;\n int val;\n cin >> val;\n dll->addAfter(data, val);\n }\n else if (str == (\"removeAfter\")){\n cin >> data;\n cout << (dll->removeAfter(data)) << endl;\n }\n else if (str == (\"removeBefore\")){\n cin >> data;\n cout << (dll->removeBefore(data)) << endl;\n }\n cin >> str;\n }\n cout << dll->toString();\n \n return 0; \n }"},"java":{"code":"import java.util.*;\r\n\r\nclass Main {\r\n\r\n public static class DoublyLinkedList {\r\n private class Node {\r\n int data = 0;\r\n Node prev = null;\r\n Node next = null;\r\n\r\n Node(int data) {\r\n this.data = data;\r\n }\r\n\r\n }\r\n\r\n private Node head = null;\r\n private Node tail = null;\r\n private int size = 0;\r\n\r\n public String toString() {\r\n StringBuilder sb = new StringBuilder();\r\n Node curr = this.head;\r\n sb.append(\"[\");\r\n while (curr != null) {\r\n sb.append(curr.data);\r\n if (curr.next != null)\r\n sb.append(\", \");\r\n curr = curr.next;\r\n }\r\n sb.append(\"]\");\r\n\r\n return sb.toString();\r\n }\r\n\r\n // Exceptions========================================\r\n\r\n private boolean ListIsEmptyException() {\r\n if (this.size == 0) {\r\n System.out.print(\"ListIsEmpty: \");\r\n return true;\r\n }\r\n return false;\r\n }\r\n\r\n private boolean indexIsInvalidException(int index, int leftRange, int rightRange) {\r\n if (index < leftRange || index > rightRange) {\r\n System.out.print(\"IndexIsInValid: \");\r\n return true;\r\n }\r\n return false;\r\n }\r\n\r\n // BasicFunctions======================================\r\n\r\n public int size() {\r\n return this.size;\r\n }\r\n\r\n public boolean isEmpty() {\r\n return this.size == 0;\r\n }\r\n\r\n // AddFunctions======================================\r\n\r\n private void addFirstNode(Node node) {\r\n if (this.size == 0)\r\n this.head = this.tail = node;\r\n else {\r\n node.next = this.head;\r\n this.head.prev = node;\r\n this.head = node;\r\n }\r\n this.size++;\r\n }\r\n\r\n public void addFirst(int val) {\r\n Node node = new Node(val);\r\n addFirstNode(node);\r\n }\r\n\r\n private void addLastNode(Node node) {\r\n if (this.size == 0)\r\n this.head = this.tail = node;\r\n else {\r\n this.tail.next = node;\r\n node.prev = this.tail;\r\n this.tail = node;\r\n }\r\n this.size++;\r\n }\r\n\r\n public void addLast(int val) {\r\n Node node = new Node(val);\r\n addLastNode(node);\r\n }\r\n\r\n private void addNodeAt(int index, Node node) {\r\n if (index == 0)\r\n addFirstNode(node);\r\n else if (index == this.size)\r\n addLastNode(node);\r\n else {\r\n Node forw = getNodeAt(index);\r\n Node prev = forw.prev;\r\n\r\n prev.next = node;\r\n node.prev = prev;\r\n\r\n node.next = forw;\r\n forw.prev = node;\r\n\r\n this.size++;\r\n }\r\n }\r\n\r\n public void addAt(int index, int data) {\r\n if (indexIsInvalidException(index, 0, this.size))\r\n System.out.println(-1);\r\n else {\r\n Node node = new Node(data);\r\n addNodeAt(index, node);\r\n }\r\n }\r\n\r\n public void addBefore(Node refNode, int data) {\r\n Node node = new Node(data);\r\n Node prev = refNode.prev;\r\n\r\n if (prev == null) {\r\n node.next = refNode;\r\n refNode.prev = node;\r\n this.head = node;\r\n } else {\r\n prev.next = node;\r\n node.prev = prev;\r\n\r\n node.next = refNode;\r\n refNode.prev = node;\r\n }\r\n\r\n this.size++;\r\n }\r\n\r\n public void addBefore(int idx, int data) {\r\n Node node = getNodeAt(idx);\r\n addBefore(node, data);\r\n }\r\n\r\n public void addAfter(Node refNode, int data) {\r\n Node node = new Node(data);\r\n Node forw = refNode.next;\r\n\r\n if (forw == null) {\r\n refNode.next = node;\r\n node.prev = refNode;\r\n this.tail = node;\r\n } else {\r\n forw.prev = node;\r\n node.next = forw;\r\n\r\n node.prev = refNode;\r\n refNode.next = node;\r\n }\r\n\r\n this.size++;\r\n }\r\n\r\n public void addAfter(int idx, int data) {\r\n Node node = getNodeAt(idx);\r\n addAfter(node, data);\r\n }\r\n\r\n // RemoveFunctions======================================\r\n\r\n private Node removeFirstNode() {\r\n Node node = this.head;\r\n if (this.size == 1)\r\n this.head = this.tail = null;\r\n else {\r\n Node nextNode = this.head.next;\r\n nextNode.prev = null;\r\n node.next = null;\r\n\r\n this.head = nextNode;\r\n }\r\n\r\n this.size--;\r\n return node;\r\n }\r\n\r\n public int removeFirst() {\r\n if (ListIsEmptyException())\r\n return -1;\r\n Node node = removeFirstNode();\r\n return node.data;\r\n }\r\n\r\n private Node removeLastNode() {\r\n Node node = this.tail;\r\n if (this.size == 1)\r\n this.head = this.tail = null;\r\n else {\r\n Node prevNode = this.tail.prev;\r\n prevNode.next = null;\r\n node.prev = null;\r\n\r\n this.tail = prevNode;\r\n }\r\n\r\n this.size--;\r\n return node;\r\n }\r\n\r\n public int removeLast() {\r\n if (ListIsEmptyException())\r\n return -1;\r\n Node node = removeLastNode();\r\n return node.data;\r\n }\r\n\r\n private Node removeAtNode(int index) {\r\n if (index == 0)\r\n return removeFirstNode();\r\n else if (index == this.size - 1)\r\n return removeLastNode();\r\n else {\r\n Node node = getNodeAt(index);\r\n Node prev = node.prev;\r\n Node forw = node.next;\r\n\r\n prev.next = forw;\r\n forw.prev = prev;\r\n\r\n node.next = null;\r\n node.prev = null;\r\n\r\n this.size--;\r\n return node;\r\n }\r\n }\r\n\r\n public int removeAt(int index) {\r\n if (ListIsEmptyException())\r\n return -1;\r\n if (indexIsInvalidException(index, 0, this.size - 1))\r\n return -1;\r\n\r\n Node node = removeAtNode(index);\r\n return node.data;\r\n }\r\n\r\n private Node removeAfterNode(Node refNode) {\r\n Node forw = refNode.next;\r\n if (forw.next == null) {\r\n refNode.next = null;\r\n forw.prev = null;\r\n this.tail = refNode;\r\n } else {\r\n refNode.next = forw.next;\r\n forw.next.prev = refNode;\r\n\r\n forw.next = null;\r\n forw.prev = null;\r\n }\r\n this.size--;\r\n return forw;\r\n }\r\n\r\n public int removeAfter(Node refNode) {\r\n if (refNode.next == null) {\r\n System.out.print(\"LocationIsInvalid: \");\r\n return -1;\r\n }\r\n return removeAfterNode(refNode).data;\r\n }\r\n\r\n public int removeAfter(int idx) {\r\n Node node = getNodeAt(idx);\r\n return removeAfter(node);\r\n }\r\n\r\n public int removeBefore(Node refNode) {\r\n // complete your code.\r\n }\r\n\r\n public int removeBefore(int idx) {\r\n Node node = getNodeAt(idx);\r\n return removeBefore(node);\r\n }\r\n\r\n // getFunctions======================================\r\n\r\n public int getFirst() {\r\n if (ListIsEmptyException())\r\n return -1;\r\n\r\n return this.head.data;\r\n }\r\n\r\n public int getLast() {\r\n if (ListIsEmptyException())\r\n return -1;\r\n\r\n return this.tail.data;\r\n }\r\n\r\n private Node getNodeAt(int index) {\r\n Node curr = this.head;\r\n while (index-- > 0)\r\n curr = curr.next;\r\n\r\n return curr;\r\n }\r\n\r\n public int getAt(int index) {\r\n if (ListIsEmptyException())\r\n return -1;\r\n else if (indexIsInvalidException(index, 0, this.size - 1))\r\n return -1;\r\n\r\n Node node = getNodeAt(index);\r\n return node.data;\r\n }\r\n\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n DoublyLinkedList dll = new DoublyLinkedList();\r\n\r\n String str = scn.nextLine();\r\n while (!str.equals(\"stop\")) {\r\n String[] s = str.split(\" \");\r\n if (s[0].equals(\"addFirst\"))\r\n dll.addFirst(Integer.parseInt(s[1]));\r\n else if (s[0].equals(\"addLast\"))\r\n dll.addLast(Integer.parseInt(s[1]));\r\n else if (s[0].equals(\"removeFirst\"))\r\n System.out.println(dll.removeFirst());\r\n else if (s[0].equals(\"removeLast\"))\r\n System.out.println(dll.removeLast());\r\n else if (s[0].equals(\"getFirst\"))\r\n System.out.println(dll.getFirst());\r\n else if (s[0].equals(\"getLast\"))\r\n System.out.println(dll.getLast());\r\n else if (s[0].equals(\"size\"))\r\n System.out.println(dll.size());\r\n else if (s[0].equals(\"isEmpty\"))\r\n System.out.println(dll.isEmpty());\r\n else if (s[0].equals(\"getAt\"))\r\n System.out.println(dll.getAt(Integer.parseInt(s[1])));\r\n else if (s[0].equals(\"addAt\"))\r\n dll.addAt(Integer.parseInt(s[1]), Integer.parseInt(s[2]));\r\n else if (s[0].equals(\"removeAt\"))\r\n dll.removeAt(Integer.parseInt(s[1]));\r\n else if (s[0].equals(\"addBefore\"))\r\n dll.addBefore(Integer.parseInt(s[1]), Integer.parseInt(s[2]));\r\n else if (s[0].equals(\"addAfter\"))\r\n dll.addAfter(Integer.parseInt(s[1]), Integer.parseInt(s[2]));\r\n else if (s[0].equals(\"removeAfter\"))\r\n System.out.println(dll.removeAfter(Integer.parseInt(s[1])));\r\n else if (s[0].equals(\"removeBefore\"))\r\n System.out.println(dll.removeBefore(Integer.parseInt(s[1])));\r\n\r\n str = scn.nextLine();\r\n }\r\n\r\n System.out.println(dll);\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"addFirst 4\r\naddFirst 4\r\naddLast 5\r\naddFirst 7\r\ngetAt 4 3\r\naddAt 4 34\r\naddAt 0 43\r\nremoveAt 4\r\naddAfter 2 33\r\naddAfter 0 33\r\naddAfter 4 33\r\nremoveAt 0\r\nremoveAfter 3\r\nremoveBefore 3\r\naddAt 8 545\r\naddLast 1\r\nremoveFirst\r\nremoveFirst\r\nsize\r\nisEmpty\r\ngetFirst\r\nremoveFirst\r\nremoveLast\r\ngetLast\r\nremoveFirst\r\nremoveFirst\r\naddAt 0 345\r\nstop","sampleOutput":"IndexIsInValid: -1\r\n33\r\n4\r\nIndexIsInValid: -1\r\n33\r\n7\r\n4\r\nfalse\r\n33\r\n33\r\n1\r\n34\r\n4\r\n34\r\n[345]\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1e4c8949-5890-4d15-be5b-6601c7e2029a","name":"Linked List For Intermediate","slug":"linked-list-for-intermediate-637","type":0},{"id":"2e9fd95c-604e-4f9b-b742-a11764e45520","name":"Remove Before In Doubly Linkedlist","slug":"remove-before-in-doubly-linkedlist","type":1}],"next":{"id":"beb03c68-99b2-442d-b9d4-1e87d40f43cf","name":"Remove Before In Doubly Linkedlist","type":3,"slug":"remove-before-in-doubly-linkedlist"},"prev":{"id":"e90bfcc1-fcfc-4fa2-bcbd-44e97bfcd929","name":"Remove Node In Doubly Linkedlist","type":3,"slug":"remove-node-in-doubly-linkedlist"}}}

Remove Before In Doubly Linkedlist

1. You are given a partially written DoublyLinkedList class. 2. You are required to complete the body of removeBefore function. This function is supposed to remove value Before given Node. 3. If size of list is zero then return "ListIsEmpty: -1". 4. If Index is Invalid then return "IndexIsInValid: -1". 5. If Location which we want to remove is null then return "LocationIsInvalid: -1". 6. You are required to update head, tail and size as required. 7. Input and Output is managed for you. Just update the code in incomplete function. Note -> Use the code snippet and follow the algorithm discussed in question video. The judge can't force you but the intention is to teach a concept. Play in spirit of the question.

{"id":"89ac0a9e-e07d-44e4-96d5-7b136fb63657","name":"Remove Before In Doubly Linkedlist","description":"1. You are given a partially written DoublyLinkedList class.\r\n2. You are required to complete the body of removeBefore function. This function is supposed to remove value Before given Node. \r\n3. If size of list is zero then return \"ListIsEmpty: -1\".\r\n4. If Index is Invalid then return \"IndexIsInValid: -1\".\r\n5. If Location which we want to remove is null then return \"LocationIsInvalid: -1\".\r\n6. You are required to update head, tail and size as required.\r\n7. Input and Output is managed for you. Just update the code in incomplete function.\r\n\r\nNote -> Use the code snippet and follow the algorithm discussed in question video. The judge can't \r\n force you but the intention is to teach a concept. Play in spirit of the question.\r\n","inputFormat":"input in managed for you.\r\n","outputFormat":"output in managed for you.\r\n","constraints":"0 &lt;= N &lt;= 10^6\r\n","sampleCode":{"cpp":{"code":"#include<iostream>\nusing namespace std;\n#include<vector>\n\n\nclass DoublyLinkedList {\n public : class Node {\n public:\n int data = 0;\n Node* prev = nullptr;\n Node* next = nullptr;\n\n Node(int data) {\n this->data = data;\n }\n\n };\n\n Node* head = nullptr;\n Node* tail = nullptr;\n int size = 0;\n\n string toString() {\n string sb;\n Node* curr = this->head;\n sb += \"[\";\n while (curr != nullptr) {\n sb += (to_string)(curr->data);\n if (curr->next != nullptr)\n sb+=\", \";\n curr = curr->next;\n }\n sb += \"]\";\n\n return sb;\n }\n\n // Exceptions========================================\n\n private: bool indexIsInvalidException(int index, int leftRange, int rightRange) {\n if (index < leftRange || index > rightRange) {\n cout << (\"IndexIsInValid: \");\n return true;\n }\n return false;\n }\n\n\n private:bool ListIsEmptyException() {\n if (this->size == 0) {\n cout << \"ListIsEmpty: \";\n return true;\n }\n return false;\n }\n\n // BasicFunctions======================================\n\n public:int Size() {\n // write your code here\n return size;\n }\n\n public:bool isEmpty() {\n // write your code here\n\n return this->size==0;\n \n }\n\n // AddFunctions======================================\n\n public:void addFirstNode(Node* node) {\n if (this->size == 0)\n this->head = this->tail = node;\n else {\n node->next = this->head;\n this->head->prev = node;\n this->head = node;\n }\n this->size++;\n }\n\n public: void addFirst(int val) {\n Node* node = new Node(val);\n addFirstNode(node);\n }\n\n public:void addLastNode(Node* node) {\n if (this->size == 0)\n this->head = this->tail = node;\n else {\n this->tail->next = node;\n node->prev = this->tail;\n this->tail = node;\n }\n this->size++;\n }\n\n public:void addLast(int val) {\n Node* node = new Node(val);\n addLastNode(node);\n }\n\n // RemoveFunctions======================================\n\n public:Node *removeFirstNode() {\n Node* node = this->head;\n if (this->size == 1)\n this->head = this->tail = nullptr;\n else {\n Node* nextNode = this->head->next;\n nextNode->prev = nullptr;\n node->next = nullptr;\n\n this->head = nextNode;\n }\n\n this->size--;\n return node;\n }\n\n public:int removeFirst() {\n if (ListIsEmptyException())\n return -1;\n Node* node = removeFirstNode();\n return node->data;\n }\n\n public:Node* removeLastNode() {\n Node* node = this->tail;\n if (this->size == 1)\n this->head = this->tail = nullptr;\n else {\n Node* prevNode = this->tail->prev;\n prevNode->next = nullptr;\n node->prev = nullptr;\n\n this->tail = prevNode;\n }\n\n this->size--;\n return node;\n }\n\n public:int removeLast() {\n if (ListIsEmptyException())\n return -1;\n Node* node = removeLastNode();\n return node->data;\n }\n\n // getFunctions======================================\n\n public:int getFirst() {\n if(ListIsEmptyException()){\n return -1;\n }\n return head->data;\n \n }\n private: Node* getNodeAt(int index) {\n Node*curr = this->head;\n while (curr != nullptr && index-- > 0)\n curr = curr->next;\n\n return curr;\n }\n \n public:int getLast() {\n //write your code here\n if(ListIsEmptyException()){\n return -1;\n }\n return tail->data;\n }\n\n private: void addNodeAt(int index, Node* node) {\n if (index == 0)\n addFirstNode(node);\n else if (index == this->size)\n addLastNode(node);\n else {\n Node* forw = getNodeAt(index);\n Node* prev = forw->prev;\n\n prev->next = node;\n node->prev = prev;\n\n node->next = forw;\n forw->prev = node;\n\n this->size++;\n }\n }\n public : int getAt(int index){\n if(ListIsEmptyException()){\n return -1;\n }else if(indexIsInvalidException(index , 0, this->size-1)){\n return -1;\n }\n \n Node* curr = head;\n for(int i=1 ; i <= index ; i++){\n curr = curr->next;\n }\n \n return curr->data;\n \n }\n public:void addAt(int index, int data) {\n if (indexIsInvalidException(index, 0, this->size))\n cout << -1 << endl;\n else {\n Node* node = new Node(data);\n addNodeAt(index, node);\n }\n }\n private: Node* removeAtNode(int index) {\n if (index == 0)\n return removeFirstNode();\n else if (index == this->size - 1)\n return removeLastNode();\n else {\n Node* node = getNodeAt(index);\n Node* prev = node->prev;\n Node* forw = node->next;\n\n prev->next = forw;\n forw->prev = prev;\n\n node->next = nullptr;\n node->prev = nullptr;\n\n this->size--;\n return node;\n }\n }\n\n public: int removeAt(int index) {\n if (ListIsEmptyException() )\n return -1;\n\t\t\t\n \n //reason for the error, the below condition was missing\n if(indexIsInvalidException(index, 0, this->size-1)) {\n return -1;\n }\n \n Node* node = removeAtNode(index);\n return node->data;\n }\n public :void addBefore(Node* refNode, int data) {\n Node* node = new Node(data);\n Node* prev = refNode->prev;\n\n if (prev == nullptr) {\n node->next = refNode;\n refNode->prev = node;\n this->head = node;\n } else {\n prev->next = node;\n node->prev = prev;\n\n node->next = refNode;\n refNode->prev = node;\n }\n\n this->size++;\n }\n\n public: void addBefore(int idx, int data) {\n Node* node = getNodeAt(idx);\n addBefore(node, data);\n }\n\n public :void addAfter(Node* refNode, int data) {\n Node* node = new Node(data);\n Node* forw = refNode->next;\n\n if (forw == nullptr) {\n refNode->next = node;\n node->prev = refNode;\n this->tail = node;\n } else {\n forw->prev = node;\n node->next = forw;\n\n node->prev = refNode;\n refNode->next = node;\n }\n\n this->size++;\n }\n\n public: void addAfter(int idx, int data) {\n Node* node = getNodeAt(idx);\n addAfter(node, data);\n }\n \n private: Node *removeAfterNode(Node* refNode) {\n Node* forw = refNode->next;\n if (forw->next == nullptr) {\n refNode->next = nullptr;\n forw->prev = nullptr;\n this->tail = refNode;\n } else {\n refNode->next = forw->next;\n forw->next->prev = refNode;\n\n forw->next = nullptr;\n forw->prev = nullptr;\n }\n this->size--;\n return forw;\n }\n\n public: int removeAfter(Node* refNode) {\n if (refNode == nullptr || refNode->next == nullptr) {\n cout << (\"LocationIsInvalid: \") << endl;\n return -1;\n }\n return removeAfterNode(refNode)->data;\n }\n\n public :int removeAfter(int idx) {\n if(idx < 0 || idx >= this->size) {\n cout << \"LocationIsInvalid: \" << endl;\n return -1;\n }\n Node* node = getNodeAt(idx);\n return removeAfter(node);\n }\n\n public: int removeBefore(int idx) {\n // Write your code here\n }\n };\n \n\n int main() {\n DoublyLinkedList *dll = new DoublyLinkedList();\n \n string str;\n cin >> str;\n \n while(str != \"stop\"){\n int data;\n if(str == (\"addFirst\")){\n cin >> data;\n dll->addFirst(data);\n }\n else if (str == (\"addLast\")){\n cin >> data;\n dll->addLast((data));\n }\n else if (str == (\"removeFirst\"))\n cout << (dll->removeFirst()) << endl;\n else if (str == (\"removeLast\"))\n cout << (dll->removeLast()) << endl;\n else if (str == (\"getFirst\"))\n cout << (dll->getFirst()) << endl;\n else if (str == (\"getLast\"))\n cout << (dll->getLast()) << endl;\n else if (str == (\"size\"))\n cout << (dll->Size()) << endl;\n else if (str == (\"isEmpty\"))\n cout << (dll->isEmpty() == 0 ? \"false\" : \"true\") << endl;\n else if(str == (\"getAt\")){\n cin >> data;\n cout << dll->getAt(data) << endl ;\n }\n else if (str == (\"addAt\")){\n cin >> data;\n int val;\n cin >> val;\n dll->addAt(data , val);\n }\n else if (str == (\"removeAt\")){\n cin >> data;\n dll->removeAt(data);\n }\n else if (str == (\"addBefore\")){\n cin >> data;\n int val;\n cin >> val;\n dll->addBefore(data , val);\n }\n else if (str == (\"addAfter\")){\n cin >> data;\n int val;\n cin >> val;\n dll->addAfter(data, val);\n }\n else if (str == (\"removeAfter\")){\n cin >> data;\n cout << (dll->removeAfter(data)) << endl;\n }\n else if (str == (\"removeBefore\")){\n cin >> data;\n cout << (dll->removeBefore(data)) << endl;\n }\n cin >> str;\n }\n cout << dll->toString();\n \n return 0; \n }"},"java":{"code":"import java.util.*;\r\n\r\nclass Main {\r\n\r\n public static class DoublyLinkedList {\r\n private class Node {\r\n int data = 0;\r\n Node prev = null;\r\n Node next = null;\r\n\r\n Node(int data) {\r\n this.data = data;\r\n }\r\n\r\n }\r\n\r\n private Node head = null;\r\n private Node tail = null;\r\n private int size = 0;\r\n\r\n public String toString() {\r\n StringBuilder sb = new StringBuilder();\r\n Node curr = this.head;\r\n sb.append(\"[\");\r\n while (curr != null) {\r\n sb.append(curr.data);\r\n if (curr.next != null)\r\n sb.append(\", \");\r\n curr = curr.next;\r\n }\r\n sb.append(\"]\");\r\n\r\n return sb.toString();\r\n }\r\n\r\n // Exceptions========================================\r\n\r\n private boolean ListIsEmptyException() {\r\n if (this.size == 0) {\r\n System.out.print(\"ListIsEmpty: \");\r\n return true;\r\n }\r\n return false;\r\n }\r\n\r\n private boolean indexIsInvalidException(int index, int leftRange, int rightRange) {\r\n if (index < leftRange || index > rightRange) {\r\n System.out.print(\"IndexIsInValid: \");\r\n return true;\r\n }\r\n return false;\r\n }\r\n\r\n // BasicFunctions======================================\r\n\r\n public int size() {\r\n return this.size;\r\n }\r\n\r\n public boolean isEmpty() {\r\n return this.size == 0;\r\n }\r\n\r\n // AddFunctions======================================\r\n\r\n private void addFirstNode(Node node) {\r\n if (this.size == 0)\r\n this.head = this.tail = node;\r\n else {\r\n node.next = this.head;\r\n this.head.prev = node;\r\n this.head = node;\r\n }\r\n this.size++;\r\n }\r\n\r\n public void addFirst(int val) {\r\n Node node = new Node(val);\r\n addFirstNode(node);\r\n }\r\n\r\n private void addLastNode(Node node) {\r\n if (this.size == 0)\r\n this.head = this.tail = node;\r\n else {\r\n this.tail.next = node;\r\n node.prev = this.tail;\r\n this.tail = node;\r\n }\r\n this.size++;\r\n }\r\n\r\n public void addLast(int val) {\r\n Node node = new Node(val);\r\n addLastNode(node);\r\n }\r\n\r\n private void addNodeAt(int index, Node node) {\r\n if (index == 0)\r\n addFirstNode(node);\r\n else if (index == this.size)\r\n addLastNode(node);\r\n else {\r\n Node forw = getNodeAt(index);\r\n Node prev = forw.prev;\r\n\r\n prev.next = node;\r\n node.prev = prev;\r\n\r\n node.next = forw;\r\n forw.prev = node;\r\n\r\n this.size++;\r\n }\r\n }\r\n\r\n public void addAt(int index, int data) {\r\n if (indexIsInvalidException(index, 0, this.size))\r\n System.out.println(-1);\r\n else {\r\n Node node = new Node(data);\r\n addNodeAt(index, node);\r\n }\r\n }\r\n\r\n public void addBefore(Node refNode, int data) {\r\n Node node = new Node(data);\r\n Node prev = refNode.prev;\r\n\r\n if (prev == null) {\r\n node.next = refNode;\r\n refNode.prev = node;\r\n this.head = node;\r\n } else {\r\n prev.next = node;\r\n node.prev = prev;\r\n\r\n node.next = refNode;\r\n refNode.prev = node;\r\n }\r\n\r\n this.size++;\r\n }\r\n\r\n public void addBefore(int idx, int data) {\r\n Node node = getNodeAt(idx);\r\n addBefore(node, data);\r\n }\r\n\r\n public void addAfter(Node refNode, int data) {\r\n Node node = new Node(data);\r\n Node forw = refNode.next;\r\n\r\n if (forw == null) {\r\n refNode.next = node;\r\n node.prev = refNode;\r\n this.tail = node;\r\n } else {\r\n forw.prev = node;\r\n node.next = forw;\r\n\r\n node.prev = refNode;\r\n refNode.next = node;\r\n }\r\n\r\n this.size++;\r\n }\r\n\r\n public void addAfter(int idx, int data) {\r\n Node node = getNodeAt(idx);\r\n addAfter(node, data);\r\n }\r\n\r\n // RemoveFunctions======================================\r\n\r\n private Node removeFirstNode() {\r\n Node node = this.head;\r\n if (this.size == 1)\r\n this.head = this.tail = null;\r\n else {\r\n Node nextNode = this.head.next;\r\n nextNode.prev = null;\r\n node.next = null;\r\n\r\n this.head = nextNode;\r\n }\r\n\r\n this.size--;\r\n return node;\r\n }\r\n\r\n public int removeFirst() {\r\n if (ListIsEmptyException())\r\n return -1;\r\n Node node = removeFirstNode();\r\n return node.data;\r\n }\r\n\r\n private Node removeLastNode() {\r\n Node node = this.tail;\r\n if (this.size == 1)\r\n this.head = this.tail = null;\r\n else {\r\n Node prevNode = this.tail.prev;\r\n prevNode.next = null;\r\n node.prev = null;\r\n\r\n this.tail = prevNode;\r\n }\r\n\r\n this.size--;\r\n return node;\r\n }\r\n\r\n public int removeLast() {\r\n if (ListIsEmptyException())\r\n return -1;\r\n Node node = removeLastNode();\r\n return node.data;\r\n }\r\n\r\n private Node removeAtNode(int index) {\r\n if (index == 0)\r\n return removeFirstNode();\r\n else if (index == this.size - 1)\r\n return removeLastNode();\r\n else {\r\n Node node = getNodeAt(index);\r\n Node prev = node.prev;\r\n Node forw = node.next;\r\n\r\n prev.next = forw;\r\n forw.prev = prev;\r\n\r\n node.next = null;\r\n node.prev = null;\r\n\r\n this.size--;\r\n return node;\r\n }\r\n }\r\n\r\n public int removeAt(int index) {\r\n if (ListIsEmptyException())\r\n return -1;\r\n if (indexIsInvalidException(index, 0, this.size - 1))\r\n return -1;\r\n\r\n Node node = removeAtNode(index);\r\n return node.data;\r\n }\r\n\r\n private Node removeAfterNode(Node refNode) {\r\n Node forw = refNode.next;\r\n if (forw.next == null) {\r\n refNode.next = null;\r\n forw.prev = null;\r\n this.tail = refNode;\r\n } else {\r\n refNode.next = forw.next;\r\n forw.next.prev = refNode;\r\n\r\n forw.next = null;\r\n forw.prev = null;\r\n }\r\n this.size--;\r\n return forw;\r\n }\r\n\r\n public int removeAfter(Node refNode) {\r\n if (refNode.next == null) {\r\n System.out.print(\"LocationIsInvalid: \");\r\n return -1;\r\n }\r\n return removeAfterNode(refNode).data;\r\n }\r\n\r\n public int removeAfter(int idx) {\r\n Node node = getNodeAt(idx);\r\n return removeAfter(node);\r\n }\r\n\r\n public int removeBefore(Node refNode) {\r\n // complete your code.\r\n }\r\n\r\n public int removeBefore(int idx) {\r\n Node node = getNodeAt(idx);\r\n return removeBefore(node);\r\n }\r\n\r\n // getFunctions======================================\r\n\r\n public int getFirst() {\r\n if (ListIsEmptyException())\r\n return -1;\r\n\r\n return this.head.data;\r\n }\r\n\r\n public int getLast() {\r\n if (ListIsEmptyException())\r\n return -1;\r\n\r\n return this.tail.data;\r\n }\r\n\r\n private Node getNodeAt(int index) {\r\n Node curr = this.head;\r\n while (index-- > 0)\r\n curr = curr.next;\r\n\r\n return curr;\r\n }\r\n\r\n public int getAt(int index) {\r\n if (ListIsEmptyException())\r\n return -1;\r\n else if (indexIsInvalidException(index, 0, this.size - 1))\r\n return -1;\r\n\r\n Node node = getNodeAt(index);\r\n return node.data;\r\n }\r\n\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n DoublyLinkedList dll = new DoublyLinkedList();\r\n\r\n String str = scn.nextLine();\r\n while (!str.equals(\"stop\")) {\r\n String[] s = str.split(\" \");\r\n if (s[0].equals(\"addFirst\"))\r\n dll.addFirst(Integer.parseInt(s[1]));\r\n else if (s[0].equals(\"addLast\"))\r\n dll.addLast(Integer.parseInt(s[1]));\r\n else if (s[0].equals(\"removeFirst\"))\r\n System.out.println(dll.removeFirst());\r\n else if (s[0].equals(\"removeLast\"))\r\n System.out.println(dll.removeLast());\r\n else if (s[0].equals(\"getFirst\"))\r\n System.out.println(dll.getFirst());\r\n else if (s[0].equals(\"getLast\"))\r\n System.out.println(dll.getLast());\r\n else if (s[0].equals(\"size\"))\r\n System.out.println(dll.size());\r\n else if (s[0].equals(\"isEmpty\"))\r\n System.out.println(dll.isEmpty());\r\n else if (s[0].equals(\"getAt\"))\r\n System.out.println(dll.getAt(Integer.parseInt(s[1])));\r\n else if (s[0].equals(\"addAt\"))\r\n dll.addAt(Integer.parseInt(s[1]), Integer.parseInt(s[2]));\r\n else if (s[0].equals(\"removeAt\"))\r\n dll.removeAt(Integer.parseInt(s[1]));\r\n else if (s[0].equals(\"addBefore\"))\r\n dll.addBefore(Integer.parseInt(s[1]), Integer.parseInt(s[2]));\r\n else if (s[0].equals(\"addAfter\"))\r\n dll.addAfter(Integer.parseInt(s[1]), Integer.parseInt(s[2]));\r\n else if (s[0].equals(\"removeAfter\"))\r\n System.out.println(dll.removeAfter(Integer.parseInt(s[1])));\r\n else if (s[0].equals(\"removeBefore\"))\r\n System.out.println(dll.removeBefore(Integer.parseInt(s[1])));\r\n\r\n str = scn.nextLine();\r\n }\r\n\r\n System.out.println(dll);\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"addFirst 4\r\naddFirst 4\r\naddLast 5\r\naddFirst 7\r\ngetAt 4 3\r\naddAt 4 34\r\naddAt 0 43\r\nremoveAt 4\r\naddAfter 2 33\r\naddAfter 0 33\r\naddAfter 4 33\r\nremoveAt 0\r\nremoveAfter 3\r\nremoveBefore 3\r\naddAt 8 545\r\naddLast 1\r\nremoveFirst\r\nremoveFirst\r\nsize\r\nisEmpty\r\ngetFirst\r\nremoveFirst\r\nremoveLast\r\ngetLast\r\nremoveFirst\r\nremoveFirst\r\naddAt 0 345\r\nstop","sampleOutput":"IndexIsInValid: -1\r\n33\r\n4\r\nIndexIsInValid: -1\r\n33\r\n7\r\n4\r\nfalse\r\n33\r\n33\r\n1\r\n34\r\n4\r\n34\r\n[345]\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1e4c8949-5890-4d15-be5b-6601c7e2029a","name":"Linked List For Intermediate","slug":"linked-list-for-intermediate-637","type":0},{"id":"2e9fd95c-604e-4f9b-b742-a11764e45520","name":"Remove Before In Doubly Linkedlist","slug":"remove-before-in-doubly-linkedlist","type":1}],"next":{"id":"beb03c68-99b2-442d-b9d4-1e87d40f43cf","name":"Remove Before In Doubly Linkedlist","type":3,"slug":"remove-before-in-doubly-linkedlist"},"prev":{"id":"e90bfcc1-fcfc-4fa2-bcbd-44e97bfcd929","name":"Remove Node In Doubly Linkedlist","type":3,"slug":"remove-node-in-doubly-linkedlist"}}}
plane

Editor


Loading...

Remove Before In Doubly Linkedlist

medium

1. You are given a partially written DoublyLinkedList class. 2. You are required to complete the body of removeBefore function. This function is supposed to remove value Before given Node. 3. If size of list is zero then return "ListIsEmpty: -1". 4. If Index is Invalid then return "IndexIsInValid: -1". 5. If Location which we want to remove is null then return "LocationIsInvalid: -1". 6. You are required to update head, tail and size as required. 7. Input and Output is managed for you. Just update the code in incomplete function. Note -> Use the code snippet and follow the algorithm discussed in question video. The judge can't force you but the intention is to teach a concept. Play in spirit of the question.

Constraints

0 <= N <= 10^6

Format

Input

input in managed for you.

Output

output in managed for you.

Example

Sample Input

addFirst 4 addFirst 4 addLast 5 addFirst 7 getAt 4 3 addAt 4 34 addAt 0 43 removeAt 4 addAfter 2 33 addAfter 0 33 addAfter 4 33 removeAt 0 removeAfter 3 removeBefore 3 addAt 8 545 addLast 1 removeFirst removeFirst size isEmpty getFirst removeFirst removeLast getLast removeFirst removeFirst addAt 0 345 stop

Sample Output

IndexIsInValid: -1 33 4 IndexIsInValid: -1 33 7 4 false 33 33 1 34 4 34 [345]

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode