CODEWITHSUNDEEP
c#linked-list
CasperT
CasperT

Reputation: 3475

Reverse a single chained List

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?

Upvotes: 0

Views: 1036

Answers (7)

pgast
pgast

Reputation: 1677

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

Upvotes: 0

Chris S
Chris S

Reputation: 65426

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.

Upvotes: 4

manji
manji

Reputation: 47978

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;
    }
}

Upvotes: 3

Eric Minkes
Eric Minkes

Reputation: 1431

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.

Upvotes: 0

Oliver
Oliver

Reputation: 45081

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.

Upvotes: 1

UncleBens
UncleBens

Reputation: 41331

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;
}

Upvotes: 5

Pete Kirkham
Pete Kirkham

Reputation: 49311

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.

Upvotes: 0

Related Questions