Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code in Python
3.2.
Complexities
3.2.1.
Time Complexity
4.
Frequently Asked Questions
4.1.
Why did we use a Doubly linked list and not a single-linked list?
4.2.
Can we make browser history using vector(i.e. array) or stack?
5.
Conclusion
Last Updated: Mar 27, 2024

Design Browser History (Doubly linked list)

Author HET FADIA
0 upvote
Linked List

Introduction

This article aims to familiarise you with the Doubly-linked List data structure. Also, see Linked Lists.

To brush up on your knowledge of Doubly-linked lists,  you can read the article Doubly Linked List on Code studio.

Let’s see the problem statement in the next section.

Problem Statement

You have to design a browser history where a person can visit any page and go backward or forward in browser history in any number of steps.

Suppose we have to go forward x steps, but we can go only y(where y<x) steps forward because of the last Node, then we return the last node. Similarly, we will return the first node while traveling back.

Note: Whenever we visit a new URL/page, we clear the forward history and add the URL in the Doubly LinkedList.

A few examples are as follows:

Input 1

obj=browser_history("https://www.google.com/")
function=["visit","visit","visit","back","forward","visit","back","forward","back"]
links=["https://web.whatsapp.com/","https://www.facebook.com/","https://www.youtube.com/",2,3,"https://www.google.com/",1,100,2]

Output 1

https://web.whatsapp.com/
https://www.youtube.com/
https://www.youtube.com/
https://www.google.com/
https://www.facebook.com/

Explanation

First we create obj=browser_history(google.com)

So our Doubly LinkedList will look like this:

Showing Doubly LinkedList

Figure 1: Showing Doubly LinkedList

 

Then we visit whatsapp.com, facebook.com, and youtube.com.

Then our doubly LinkedList will look like this.

Showing DLL after adding nodes along with the current node

Figure 2: Showing DLL after adding nodes along with the current node

Our current pointer will point to the last URL node, i.e. youtube.com.

Then there is the query of back(2). Thus we will move two nodes backwards, and our current_node will point to the whatsapp.com node.

Curr_node points to whatsapp.com

Figure 3: Curr_node points to whatsapp.com

Thus https://web.whatsapp.com/ will be printed.

The next query is three steps forward. As we can only go two steps ahead, our current node will point to youtube.com, and we will print “https://www.youtube.com/”.

Now we have a query to add google.com. Thus we add google.com, and our current_node will point to google.com.

Finally, after adding google.com, the DLL looks like this, as seen below.

Current Node points to google.com.

Figure 4: The Doubly LinkedList is shown.

Current Node points to google.com.

 

Now we call back(1), so the current_node will point to youtube.com, and “https://www.youtube.com/” will be printed.

Again forward(100) is called, but the current_node can only go forward by one node. So it will go to 1 node further, and we print “https://www.google.com/”.

The current pointer is pointing at the last node google.com.

When again back(2) is called facebook.com will be printed.

We note from the above explanation that we print output when we call the forward or back function. And when we reach end nodes and can’t go further, we print that node URL.

Approach

Here we assume that the front node is the head node, and we add new nodes towards the tail node.

The approach is simple. The current pointer will give us the link to the current URL. When we want to go x nodes back, we will simply go to the previous pointer for x times. While traversing back, if we encounter a head node, we will stop there and return to the current node.

Similarly, when we want to go x steps forward in history, we will simply go forward in the Doubly linked list.

When we visit a new URL, we will simply clear all the forward URLs and add the given URL to the Doubly linked list.

Code in Python

Here is the code for the problem in python3.

class url_node:
    def __init__(self, url):
        # we are intitializing node with the url given
        self.url=url
        self.next=self.prev=None

class browser_history:
    def __init__(self, curr_page):
        # initializing history with the current page
        self.curr_url = url_node(curr_page)
   
    def delete_next_url(self,curr_url):
        # here the next node is deleted
        next_node=curr_url.next
        curr_url.next=next_node.next
        if curr_url.next:
            curr_url.next.prev=curr_url
        next_node.next=None
        next_node.prev=None
        next_node.url=None
   
    def visit(self, url):
        while self.curr_url.next:
            # while the next node is present we delete the next node
            self.delete_next_url(self.curr_url)
        # we create a new node with the url given
        self.next_page = url_node(url)
        # we make the current as the previous of the next node
        self.next_page.prev = self.curr_url
        # we set the next node of the current node to the new node
        self.curr_url.next=self.next_page
        self.curr_url=self.next_page
           
    def back(self, steps):
        # we go for "steps" step backwards
        for i in range(steps):
            # if the previous pointer is NULL i.e. it is head node then we break
            # because there is no node before head node
            if self.curr_url.prev==None:
                break
            self.curr_url=self.curr_url.prev
        # we return the required url
        return self.curr_url.url

    def forward(self,steps):
        # we go for "steps" step forward
        for i in range(steps):
            # if the next node is NULL i.e. it is tail node then we break
            # because there is no node after tail node
            if self.curr_url.next==None:
                break
            self.curr_url=self.curr_url.next
        # we return the required url
        return self.curr_url.url

obj=browser_history("https://www.google.com/")
function=["visit","visit","visit","back","forward","visit","back","forward","back"]
links=["https://web.whatsapp.com/","https://www.facebook.com/","https://www.youtube.com/",2,3,"https://www.google.com/",1,100,2]

for i,j in zip(function,links):
    if i=="visit":
        obj.visit(j)
    elif i=="back":
        url=obj.back(j)
        print(url)
    else:
        url=obj.forward(j)
        print(url)
You can also try this code with Online Python Compiler
Run Code

Output

https://web.whatsapp.com/
https://www.youtube.com/
https://www.youtube.com/
https://www.google.com/
https://www.facebook.com/

Complexities

Time Complexity

Initializing Browser History

The time complexity for initializing Browser History is O(1).

This is because we are making a new node and storing a URL in it.

Visiting a new URL

The time complexity for visiting a new URL is O(size(Doubly linked list)).

We have to clear all of the forward nodes and add the new URL.

The maximum length of the forward nodes can be equal to the size of the Doubly linked list.

If we do not clear the next node, there will be dangling pointers, which may lead to memory leaks.

We can also do this function in O(1)  by simply making the next node the new node(URL).

Going back to “steps” in browser history

The time complexity for going back in history is O(steps).

This is because we will have to go back to the whole Doubly LinkedList in the worst case i.e. from the last node to the first node.

However, going back a few steps, we might get the head in some cases.

Then we can’t go back further and thus return the head node.

Going forward “steps” in browser history

The time complexity for going forward in history is O(steps). 

In the worst case, we will have to go forward with “steps” steps.

It may happen that going forward a few steps, we get a tail node, and thus we can’t go forward and break and return the current_node.url.

Space Complexity

The space complexity of the program is O(length(Doubly linked list)).

Each node of the Doubly linked list takes constant space or O(1) space as we are storing three things in Node, namely URL, a pointer to next and previous nodes. There are length(Doubly linked list) nodes in the DLL. So the space complexity of the program is O(length(Doubly linked list)) * O(1) = O(length(Doubly linked list)) 

Frequently Asked Questions

Why did we use a Doubly linked list and not a single-linked list?

Sometimes we have to go forward, and sometimes we have to go backward. In a Doubly LinkedList, we can get the just forward as well as the just backward node in O(1) time. Had we used LinkedList, going backward would have been then O(n) time as we would have to search from the head node again? Thus using Doubly LinkedList makes our code efficient.

Can we make browser history using vector(i.e. array) or stack?

Yes, we can make browser history using vector. When we visit a new URL, we will clear the forward vector and append the new URL in the vector. Using vectors is beneficial because the forward and backward functions take O(1) time complexity. We can directly jump to x step forward or backward in O(1) because the vector has O(1) access.  The visit in the vector is also O(1), as we can mark it as the last node. Thus using vectors would be highly efficient.

We can also implement browser history using two stacks. When we add a new URL, we will append it to the first stack. When we go backward, we will pop the current_node from the first stack and append it to the second stack.

The space complexity in all of the above methods will be O(size).

Conclusion

The article helps us understand the implementation of browser history in the Doubly linked list in python3. You can also copy the code and run it on your system on multiple inputs to understand the approach better.

We have used the Doubly LinkedList data structure in our implementation. Also, we have used classes to create as many objects as we need.

You can visit the platform Coding Ninjas Studio to practice more problems, read interview experiences and attempt mock tests.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning!!!

Live masterclass