Linked Lists

Linked List sample codebase with reversing the list in place (using Java):

There are two ways to reverse a linked list in place. One is to utilize recursion and the other is the iterative approach. Utilizing recursion is straight forward and intuitive but suffers from the drawback of performance issues et al. We will discuss benefits of recursion vis a vis the iterative approach and vice-versa in another blog entry.

In this blog entry, we will utilize the iterative approach. The logic of reversing a linked list (singly linked list) is simple and let me explain it using this example of a linked list:

A->B->C->D->E

Here node A has a next pointer to node B and so on. Node E has the next pointer set to NULL since it is the end of this list.

What we need to do: We need to pass the head of this list (node A) to the reverse method and it should return us node E with the list reversed as in:

E->D->C->B->A

The logic is to go one node at a time and changing the direction of the arrow. This is done by setting the next pointer of node B to be A and so on. This is demonstrated in the Java program below (please see the reverse operation in bold).

 public class Reverse {

    public static void main(String[] args) throws Exception
    {
        LinkedList l = new LinkedList();

        for (int i = 0; i < 11; i++)
        {
            Node n = new Node(new String("" + i), null);
            l.addToEnd(n);
        }

        Node n = l.getStartingNode();
        while (n != null)
        {
            System.out.println("\t" + n);
            n = n.next;
        }

        n = reverse(l.getStartingNode());
        while (n != null)
        {
            System.out.println("\t" + n);
            n = n.next;
        }

    }

    static Node reverse(Node startingNode) throws Exception
    {
        Node n = startingNode;
        Node n1 = n.next;
        n.next = null;

        while (true)
        {
            if (n1 == null)
            {
                return n;
            }

            Node n2 = n1.next;
            n1.next = n;

            if (n2 == null)
            {

                return n1;
            }
            n = n1;
            n1 = n2;

        }
    }

}

class LinkedList {
    Node begin = null;
    Node last = null;

    boolean addToEnd(Node a)
    {
        if (begin == null)
        {
            begin = a;
            last = a;
        }
        else
        {
            last.next = a;
            last = a;

        }
        return true;
    }

    Node getStartingNode()
    {
        return begin;
    }

    Node getLastNode()
    {
        return last;
    }

}

class Node implements Cloneable {
    Object value;
    Node next;

    Node() {

    }

    Node(Object v, Node n) {
        this.value = v;
        this.next = n;

    }

    @Override
    public String toString()
    {
        return value.toString();
    }

    @Override
    protected Object clone() throws CloneNotSupportedException
    {
        return super.clone();
    }

}

Leave a Reply

Your email address will not be published. Required fields are marked *

     

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">