Reverse a single chained List

Question

Hi.

I hope I am using the right terminology. I have made a single-chained list.

class MyStack
{
    public Node Initial { get; set; }

    public MyStack()
    {
        Initial = null;
    }

    public void Push(int data)
    {
        var node = new Node { Data = data, Next = Initial };
        Initial = node;
    }

    public int Pop()
    {
        int res = Initial.Data;
        Initial = Initial.Next;
        return res;
    }

    public int Sum()
    {
        int sum = 0;
        Node currentNode = Initial;
        while (currentNode != null)
        {
            sum += currentNode.Data;
            currentNode = currentNode.Next;
        }
        return sum;
    }
    public int Count()
    {
        int count = 0;
        Node currentNode = Initial;
        while (currentNode != null)
        {
            count++;
            currentNode = currentNode.Next;
        }
        return count;
    }

    public void PrintAll()
    {     
        Node currentNode = Initial;
        while(currentNode != null)
        {
            Console.WriteLine("tmp.Data = " + currentNode.Data);
            currentNode = currentNode.Next;
        }
    }
}
public class Node
{
    public int Data;
    public Node Next;
}

Meaning you can do something like this:

    var s = new MyStack();
    s.Push(5);
    s.Push(3);
    s.Push(7);
    s.PrintAll();
    Console.WriteLine("Sum: " + s.Sum());
    Console.WriteLine("Count: " + s.Count());

Now, I want to try and make a Reverse method. This seems to be working:

public void Reverse()
{
    Node predesesor, location;
    location = Initial;
    predesesor = null;
    while(Initial != null)
    {
        Initial = Initial.Next;
        location.Next = predesesor;
        predesesor = location;
        location = Initial;
    }
    Initial = predesesor;
}

I am hardly able to see how it works, and it will be tough to maintain. It seems more like a hack than anything else.

Can you offer any assistance?

Answer 1

One solution would be to turn it into a doubly-linked list, and then work backwards using the previous node property:

public class Node
{
    public int Data;
    public Node Next;
    public Node Previous;
}

There is already a doubly-linked list in the framework if you want to save yourself some effort.

Answer 2

It doesn't seem like a hack to me and I don't see what's there to maintain (it is either correct or not, what else would you do with it?). If you want to figure out how it works, "execute" each step on paper. Draw a list (e.g 1 -> 3 -> 5 -> 7 -> 9 -> NULL), mark out where all Nodes point at any time and start "single-stepping".

I couldn't think of a cleaner way to reverse a singly linked list. You need a reference to the next node (Initial at the beginning of the loop), before you can reverse the link between current node and previous node. You just won't be able to move on in the original list otherwise.

What you could do is fix the spelling of the variables and perhaps not use Initial in the loop itself (use a third variable, so the role of each variable is clearer) and only set Initial to the first Node in the reversed list at the end.

So, all in all:

public void Reverse() {
    Node current = Initial, previous = null;
    while (current) {
        Node next = current.Next;
        current.Next = previous;
        previous = current;
        current = next;
    }
    Initial = previous;
}

Answer 3

you can do it recursivly:

a->b->c->d

    a->null
     b->null
      c->null
      c<-d
     b<-c
    a<-b

a<-b<-c<-d

public void Reverse()
{
    Reverse(Initial);
}

private void Reverse(Node node)
{
    if(node != null && node.Next != null)
    {
        //go deeper
        Reverse(node.Next);
        //swap
        node.Next.Next = node
        node.Next = null;
    }
}

Answer 4

If you call it "nreverse" or "reverse in place" then any developer worth tuppence would recognise it as a classic algorithm rather than a hack.

It shouldn't require much maintenance, except maybe renaming any incorrectly spelled variables.

Answer 5

Instead of reinventing the wheel you should check, if there is already something you can use something from .Net Framework.

For example i would take here the LinkedList with the LinkedListNode. In other cases you could probably take the Queue or a Stack.

Answer 6

The following code might be a bit more intuitive:

public void Reverse()
{
    MyStack reverse = new MyStack();
    while (Initial != null)
    {
       reverse.Push(this.Pop());
    }
    Initial = reverse.Initial;
}

(Reverse is a member method of the MyStack class).

Of course, it does require twice the space compared with the original code.

Answer 7

stack s1
s1.push_front(...)
...
s1.push_front(...)

////////////////////////////////////////////////////////

void reverse(stack& to,stack_or_list& s )
    while(!s.empty()){
        to.push_front(s.pop_front());
    }
}

now a series of to.pop_fronts gets you what you want

stack_or_list needs: pop_front empty to needs: push_front,pop_front