Easy C++ Code | Detailed Explanation | Doubly Linked List
\n# Approach\n Describe your approach to solving the problem. \nHi there, let\'s understand this code in detail. I have implemented the BrowserHistory using a d
\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHi there, let\'s understand this code in detail. I have implemented the ```BrowserHistory``` using a **doubly linked list**. If you\'re not familiar with what a doubly linked list is, don\'t worry, I\'ll explain it along the way. Let\'s dive in!\n\nThe first thing we need to do is to define a class called ```Node```. A node is an object that represents an element of the list. It has three attributes: url, prev and next. The url is a string that stores the web address of the page that the node corresponds to. The prev and next are pointers to other nodes that indicate the previous and next elements in the list.\n\nThe constructor of the Node class takes a url as an argument and assigns it to the url attribute. It also sets the prev and next attributes to NULL, which means they point to nothing initially.\n\nNext, we need to define another class called BrowserHistory. This is the main class that will handle the operations of browsing history. It has one attribute: root. The root is a pointer to a node that represents the current page that we are on.\n\nThe constructor of the ```BrowserHistory``` class takes a homepage as an argument and creates a new node with that url. It then assigns it to the root attribute.\n\nNow let\'s look at the methods of the BrowserHistory class. The first one is visit, which takes a url as an argument and creates a new node with that url. It then links this new node after the current root node by setting its prev attribute to point to root and setting root\'s next attribute to point to it. Finally, it updates root to point to this new node.\n\nThe second method is back, which takes an integer steps as an argument and moves backward in history by steps number of times or until we reach the beginning of history (whichever comes first). It does this by updating root to point to its prev attribute repeatedly until either steps becomes zero or root\'s prev becomes NULL (meaning there is no previous node). It then returns root\'s url as output.\n\nThe third method is forward, which takes an integer steps as an argument and moves forward in history by steps number of times or until we reach the end of history (whichever comes first). It does this by updating root to point to its next attribute repeatedly until either steps becomes zero or root\'s next becomes NULL (meaning there is no next node). It then returns root\'s url as output.\n\nThat\'s it! We have implemented a browser history using a doubly linked list.\n\nA doubly linked list is basically a sequence of nodes that can be traversed in both directions by following their prev and next pointers. It allows us to easily insert and delete nodes at any position without shifting other elements. It also allows us to access any element in constant time given its pointer.\n\n---\n\n\n**I hope you enjoyed this post and learned something new today.\nIf you have any questions or feedback, feel free to leave them in\nthe comments section below. Thanks for reading!**\n\n### And yeah don\'t forget to upvote this post if you liked it.\n\n# Complexity\n- Time complexity:\n  The time complexity of the visit method is O(1) because it involves constant time operations such as creating a new node and updating pointers. The time complexity of the back and forward methods is O(steps) because they involve traversing the linked list for a maximum of steps times.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n  The space complexity of this code is O(n), where n is the number of nodes in the linked list. This is because we need to store each visited URL in a node.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Node{\npublic:\n    string url;\n    Node* prev;\n    Node* next;\n\n    Node(string url){\n        this->url = url;\n        prev = NULL;\n        next = NULL;\n    }\n};\n\nclass BrowserHistory {\nprivate:\n    Node *root;\npublic:\n    BrowserHistory(string homepage) {\n        root = new Node(homepage);\n    }\n    \n    void visit(string url) {\n        Node* node = new Node(url);\n        root->next = node;\n        node->prev = root;\n        root = root->next;\n    }\n    \n    string back(int steps) {\n        for(int i = 0; i<steps && root->prev != NULL; i++){\n            root = root->prev;\n        }\n        return root->url;\n    }\n    \n    string forward(int steps) {\n        for(int i = 0; i<steps && root->next != NULL; i++){\n            root = root->next;\n        }\n        return root->url;\n    }\n};\n\n/**\n * Your BrowserHistory object will be instantiated and called as such:\n * BrowserHistory* obj = new BrowserHistory(homepage);\n * obj->visit(url);\n * string param_2 = obj->back(steps);\n * string param_3 = obj->forward(steps);\n */\n```
['Linked List', 'Doubly-Linked List', 'C++']