Creating a rudimentary browser history with a linked list

Question

So I am working on an assignment where we make a rudimentary browser history with c#. The requirement is that we need to use a singly linked list to do this. The issue that I am having is that when I want to go backwards in the history and print it takes from the beginning of the list and not the front. (Example is if I had a list with 1, 2, 3, 4 in it and went back It would be 2, 3, 4 and 1 gets moved to the future category).

public class UnderflowException : Exception
{
    public UnderflowException(string s) : base(s) { }
}

public class OverflowException : Exception
{
    public OverflowException(string s) : base(s) { }
}

class History
{
    protected class IntListNode
    {
        public string Data;
        public IntListNode Next;

        public IntListNode(string data)
        {
            Data = data;
        }

        public IntListNode(string data, IntListNode next)
        {
            Next = next;
        }
    }

    protected IntListNode first;

    private int i;

    public void PrintAll()
    {
        int j = 0;
        IntListNode node = first;
        Console.WriteLine("Privious things that you have viewed.");

        while (node != null)
        {
            if (counter <= j)
            {
                break;
            }

            Console.WriteLine(node.Data);
            node = node.Next;
            j++;
        }

        Console.WriteLine("Things to go forward to.");

        while (node != null)
        {
            Console.WriteLine(node.Data);
            node = node.Next;
        }
    }

    private int counter;

    public void MoveBackwards()
    {
        if (counter >= 0)
        {
            counter = counter - 1;
        }
        else
        {
            throw new UnderflowException("underflow");
        }
    }

    public void MoveForwards()
    {
        if (counter > i)
        {
            throw new OverflowException("overflow");
        }        
        else
        {
            counter++;
        }
    }

    public void VisitPage(string desc)
    {
        IntListNode n = new IntListNode(desc);
        n.Next = this.first;
        this.first = n;
        counter++;
        i = counter;
    }
}

When I already have items in the list and ask it to move one backwards it takes the first node not the last in the list. from earlier example wanting it to go from 1, 2, 3, 4 use the go backwards command and have the history display 1, 2, 3 and the forward display 4.

Answer 1

Here's an example based on your code, though changed slightly.

Instead of tracking counter and i for our state, I just keep track of two nodes: head (the first one) and current (the one the user is on right now). I'm also inserting new pages at the current.Next node instead of at the head node because that's how I'm used to using a linked list.

By doing this, it makes navigation easy. To go forward, we just set current = current.Next, and to go backward we start at the head and move forward until we find the node whose Next is pointing to current. Then we set current to that node.

To print out the history, we just start at the head and keep moving Next. When we see that Next == current, we know we're at the current page (and I print that in a different color). Then we can keep printing the Next nodes to show the future nodes, until Next is null.

Note that this is really navigation history, not a complete record of browsing history, because if you go back and then visit a new page, you lose the page you went back from.

Hope this helps:

class History
{
    private class Node
    {
        public string Data { get; set; }
        public Node Next { get; set; }
        public Node(string data) { Data = data; }
    }

    private Node head;
    private Node current;

    public void VisitNewPage(string desc)
    {
        // Create a node for this page
        var node = new Node(desc);

        // If it's our first page, set the head
        if (head == null) head = node;

        // Update our current.Next pointer
        if (current != null) current.Next = node; 

        // Set this page as our current page
        current = node;
    }

    public void MoveBackwards()
    {
        // Can't move backwards from the head
        if (current == head) return;

        var previous = head;

        // Find the node that's behind (pointing to) the current node
        while (previous.Next != current)
        {
            previous = previous.Next;
        }

        // Make that node our new current
        current = previous;
    }

    public void MoveForwards()
    {
        // Just move to the next node
        if (current.Next != null) current = current.Next;
    }

    public void PrintCurrent()
    {
        Console.WriteLine($"You are on page: {current.Data}");
    }

    public void PrintHistory()
    {
        Console.WriteLine("\nBrowsing History");

        if (head == null)
        {
            Console.WriteLine("[Empty]");
            return;
        }

        var node = head;

        // Print previous pages
        while (node != current)
        {
            Console.WriteLine($" - {node.Data}");
            node = node.Next;
        }

        // Print current page in green
        Console.ForegroundColor = ConsoleColor.Green;
        Console.WriteLine($" - {node.Data}");
        Console.ResetColor();
        node = node.Next;

        // Print next pages
        while (node != null)
        {
            Console.WriteLine($" - {node.Data}");
            node = node.Next;
        }

        Console.WriteLine();
    }
}

Sample Usage

Here's a simple infinite loop that lets you visit new sites, move forwards, backwards, and print the history:

private static void Main()
{
    var history = new History();

    while (true)
    {
        Console.Write("Enter new page to visit, [b]ack, [f]orward, or [p]rint: ");
        var input = Console.ReadLine();
        if (string.IsNullOrWhiteSpace(input)) continue;

        switch (input.ToLower())
        {
            case "b":
            case "back":
                history.MoveBackwards();
                break;
            case "f":
            case "forward":
                history.MoveForwards();
                break;
            case "p":
            case "print":
                history.PrintHistory();
                break;
            default:
                history.VisitNewPage(input);
                break;
        }
    }
}

Output