datastructure behind browsing history

Question

Im writing a QML file browser. Now, I want to implement a back and forward function. This function is similar to browser back and forward functionality. Example :

I start in "/home/text/folder1" and browse to "/home/text/folder1/src". Now I browse to "/home/text/folder1/src/java". If I press back twice, I should be at "/home/text/folder1", and I cannot press back anymore (the button should be grayed out or in some other way indicate that there are no more "previous" items to be shown).

I was thinking of implementing this via a double-linked list. However, I am having troubles understanding where I should insert new items to the list, and when I should do it.

Take the previous example : If instead of pressing back twice, I press back only once (I am now in "/home/text/folder1/src"). If I suddenly go to "/home/text/folder2" , what now? How should my double linked list look now?

This is a datastructure question, and not implementation, so code is not required.

Answer 1

I think your idea using a doubly LinkedList is a good point to start. If you enter a new directory, you add the new item after the current item, discarding the tail of the linked list.

Assume we were in folders 1,2,3 (i.e. we have the list 1->2->[3], square brackets indicating current node). Now we go back twice, resulting in [1]->2->3 if we now go to a new folder 4, we obtain 1->[4], so we have discarded the 2->3 part.

Answer 2

I would have a stack, rather than a list. Every forward navigation puts a link on the stack; every time you go back, you remove the item from the stack.