6

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?

3

2 Answers 2

9

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.

4
  • 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
    Commented Dec 8, 2012 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
    Commented Dec 8, 2012 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
    Commented Dec 8, 2012 at 13:40
  • This architecture is excellent for this task. Took my < 1hr to build this into a project from scratch.
    – Hucker
    Commented Oct 30, 2018 at 16:27
1

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.

6
  • Ok! how will you handle a case when user clicks on any link on a page ?
    – Kevindra
    Commented Dec 8, 2012 at 13:32
  • @KevindraSingh - This case belongs to the 'new page' feature of my implementation.
    – mouviciel
    Commented Dec 8, 2012 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
    Commented Dec 8, 2012 at 13:36
  • @KevindraSingh - No, the length variable is enough to inform what data is valid in the array.
    – mouviciel
    Commented Dec 8, 2012 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"?
    – Apoorv
    Commented Dec 9, 2012 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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