Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

If you were asked to design the backward and forward button operation (as a library) in a browser, how would you do it? What will be your APIs and parameters to them? what data structure will be best suitable for this usecase?

share|improve this question
    
Interview? Assignment? –  Monster Truck Dec 8 '12 at 13:22
    
An interview question, I believe. Found it on the internet only. –  Kevindra Dec 8 '12 at 13:26
    
There are several posts covering this. First, the theory is covered here: stackoverflow.com/questions/1313788/… and implementation suggestions are here:stackoverflow.com/questions/6815797/… –  Emmad Kareem Dec 8 '12 at 13:31
    
Thanks Emmad! This helps! –  Kevindra Dec 8 '12 at 13:46
add comment

2 Answers

up vote 4 down vote accepted

Simplest solution would be to use two stacks (back, forward).

Clicking the back button will pop from the back stack and push the current page on the forward stack (and go to the popped value on the back stack).

Clicking on any link on a page (following a link) will clear the forward stack and push the current page on the back stack.

Clicking on the forward button will pop from the forward stack and push the current page on the back stack (and go to the popped value on the forward stack).

The back and forward buttons are disabled when the appropriate stack is empty.

share|improve this answer
    
I also thought so! how about using a doubly linked list instead? or a XOR linked list? Would a doubly linked list be better option than using two stacks? –  Kevindra Dec 8 '12 at 13:28
    
All navigation is unidirectional, so a double-linked list would not be necessary. XOR lists are a nice optimization when you live in the 80's. Two stacks are simple to understand, debug and communicates the idea of a history API the best. –  Dibbeke Dec 8 '12 at 13:33
    
Do we need to create separate stacks for separate tabs/windows? or can we do it using a pair of stacks only? –  Kevindra Dec 8 '12 at 13:40
add comment

I would use an array containing urls, with a variable storing the length and an index pointing to the current item being displayed.

Back decrements the index, Forward increments the index. New page increments the index, stores the url at that place in the array and sets the length to the index value.

When the array is full, I would either use a realloc() for requesting more memory or implement a ring access to the array, depending on the memory constraints.

share|improve this answer
    
Ok! how will you handle a case when user clicks on any link on a page ? –  Kevindra Dec 8 '12 at 13:32
    
@KevindraSingh - This case belongs to the 'new page' feature of my implementation. –  mouviciel Dec 8 '12 at 13:34
    
Yes I understand, but what if the next indexes are already occupied in your array. You would need to clear the rest of the array. Right? –  Kevindra Dec 8 '12 at 13:36
    
@KevindraSingh - No, the length variable is enough to inform what data is valid in the array. –  mouviciel Dec 8 '12 at 13:57
1  
@Falcon I know stack based solution is universal but I don't find a problem with mouviciel's impl too. Can you shed some more light on "much better suited"? –  Monster Truck Dec 9 '12 at 3:27
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.