Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code in Python
3.2.
Complexities
3.2.1.
Time Complexity
4.
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)

0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## 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"]

Output 1

``````https://web.whatsapp.com/

Explanation

First we create obj=browser_history(google.com)

So our Doubly LinkedList will look like this:

Figure 1: Showing Doubly LinkedList

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

Then our doubly LinkedList will look like this.

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.

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.

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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

function=["visit","visit","visit","back","forward","visit","back","forward","back"]

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)``````

Output

``````https://web.whatsapp.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.