Reversing a linked list (Java)

Question

Triggered by an interview question (I didn't answer during the interview) I wrote a Java program to reverse a linked list. I went with a loop-based approach instead of recursion. I would like to know the following:

• Is the reverse() method efficient as it is, or can it be improved?
• Are the inline comments inside the reverse() method clear or are they confusing and/or superfluous?

The following is the code for the entire LinkedList class I wrote, containing a public reverse() method:

public class LinkedList<T> {
    /**
     * A Node represents a single item inside the linked list. Each node contains
     * the value of the item and a pointer to the next node.
     */
    class Node {
        T value;
        Node next;
    }

    /**
     * The 'head' is the beginning of the linked list.
     */
    Node head;

    /**
     * Add an item to the end of the linked list.
     * 
     * @param value - The value of the item to be added
     */
    public void add(T value) {
        // Create the new node to be added
        Node newNode = new Node();
        newNode.value = value;

        // If list is empty, add it at the head
        if (head == null) {
            head = newNode;
            return;
        }

        // If the list is not empty, find the end of the list and add it there
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    /**
     * Perform an in-place reversal of the elements in the linked list.
     * 
     * After this method is called, the order of the elements in the linked list
     * will be reversed.
     */
    public void reverse() {
        Node current = head;        // Start at the beginning
        Node previous = null;       // In each iteration, points to the current node's previous node
        Node next;                  // In each iteration, we use this to backup the current node's next node
        while (current != null) {
            next = current.next;        // Backup current node's next node
            current.next = previous;    // Point current node backwards - to the previous node
            previous = current;         // Set new previous to current node, for next iteration
            head = current;             // Point head to current, so by end of loop, it will point to the original tail
            current = next;             // Point current to the original next node, for next iteration
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("");
        Node current = head;
        while (current != null) {
            sb.append(current.value + " ");
            current = current.next;
        }
        return sb.toString();
    }
}

The following is the code I used to test the above method, just in case it is required:

public class LinkedListReversal {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        System.out.println(list);

        list.reverse();

        System.out.println(list);
    }
}

Answer 1

Questions

Is the reverse() method efficient as it is, or can it be improved?

You cannot reverse a standard linked list without touching all its nodes, which has a lower-bound asymptotic complexity of o(N) operations. Your reverse() method has O(N) complexity and uses O(1) extra space, so you cannot improve its asymptotic complexity in either of those dimensions. Note that the usual recursive solution consumes o(N) overhead, all on the stack, so an iterative implementation is clearly a superior choice.

You could, however, make it slightly more efficient by updating head just once, at the end, instead of at every iteration. In particular, instead of head = current; inside the loop, you could use head = previous; immediately after the loop. No other changes would be required.

Consider, however, that if speed of the reverse() method were of paramount importance, such that it was reasonable to sacrifice a bit of list-traversal performance, then you could create a List class for which reverse() is O(1). I would do that with an internal circular, doubly-linked list of Nodes, with node traversal performed via a Node method that relies on an instance variable of the host List to determine which direction to consider as forward. With such a structure, (logically) reversing the list would be achieved simply by changing the value of the single variable that controls list direction. Example:

int direction = 0;

class Node {
    T value;
    Node[] links = new Node[2];
    public Node next() {
        assert ((direction >= 0) && (direction < links.length));
        return links[direction];
    }
}

public void reverse() {
    direction = 1 - direction;
}

Are the inline comments inside the reverse() method clear or are they confusing and/or superfluous?

They are both clear and largely superfluous. You've chosen reasonably good names for your variables, so the meaning of the code is fairly well readable from the code itself. More generally, I rarely think it appropriate to comment every single one of a series of simple statements. It is more effective to document at a somewhat higher level: if each statement reads well in and of itself then document the purpose of groups of lines.

Also, I prefer trailing comments to be very short. If you have something longer to say then put it on its own line or lines.

Additional comments

Clearly your LinkedList class is constructed for the express purpose of demonstrating reverse(), as it is missing methods that one would expect a general-purpose list class to provide. That might or might not be an issue if you were to present such an answer in an interview. Note that you could provide a full-featured implementation of java.util.List by extending AbstractSequentialList and implementing its listIterator() method.

On general principles, the inner Node class should have a constructor with which its value field and maybe its next field can be initialized. It may be appropriate to make the value final, too, as @forsvarir also suggested -- this is possible only if you provide a constructor.

Answer 2

The reverse() method looks to be fine as per me. As a general comment for a linked list implementation, insertions at the end of list should be taking O(1) time complexity.

So the add() method can be improved by keeping a pointer to the last node in the list and using it to add the elements to the list.

private Node last;

Add method can be simplified as

public void add(T value) {
    if (last == null) {
        head = new Node(value);
        last = head;
        return;
    }

    last = last.next = new Node(value);
}

Answer 3

Comments

I found some of the comments to be a bit superfluous, for example:

// Create the new node to be added

The inline comments in the reverse method also seemed unnecessary. If you need to, then explain your algorithm in a single block, but you shouldn't need to comment what every line of your algorithm does. I'd consider renaming next to nextNodeToProcess to be more explicit about what the variable is being used for.

Node

Once constructed, you don't change the value member of your Node class. I'd consider adding a constructor to initialise it and make the member final.

Answer 4

Node

You definitely should declare Node as

1. static - which removes an implicit reference to enclosing LinkedList from all the nodes;
2. private - which hides the node type implementation from all the classes that reside in the same package as your LinkedList.

Head

The head node should be declared private.

Constructor

Also, it would make sense to define a constructor that takes the value and assigns to the relevant field.

add()

With a new funky node constructor, you can write add() a little bit more succintly (see Summa summarum below).

reverse() and toString()

The same comment applies to reverse and toString.

Summa summarum

All in all, I had this in mind:

import java.util.Scanner;

public class LinkedList<T> {

    /**
     * A Node represents a single item inside the linked list. Each node contains
     * the value of the item and a pointer to the next node.
     */
    private static final class Node<T> {
        final T value;
        Node next;

        Node(final T datum) {
            this.value = datum;
        }
    }

    /**
     * The 'head' is the beginning of the linked list.
     */
    private Node head;

    /**
     * Add an item to the end of the linked list.
     * 
     * @param value - The value of the item to be added
     */
    public void add(T value) {
        if (head == null) {
            head = new Node(value);
            return;
        }

        Node node = head;

        while (node.next != null) {
            node = node.next;
        }

        node.next = new Node(value);
    }

    /**
     * Perform an in-place reversal of the elements in the linked list.
     * 
     * After this method is called, the order of the elements in the linked list
     * will be reversed.
     */
    public void reverse() {
        // The algorithm is basically popping a stack into another one which
        // "reverses" the list.
        Node head2 = null;

        while (head != null) {
            final Node<T> tmp = head; 
            head = head.next;
            tmp.next = head2;
            head2 = tmp;
        }

        head = head2;
    }

    @Override
    public String toString() {
        if (head == null) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder("[").append(head.value);
        Node node = head.next;

        while (node != null) {
            sb.append(", ").append(node.value);
            node = node.next;
        }

        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        final LinkedList<Integer> list = new LinkedList<>();
        final Scanner scanner = new Scanner(System.in);

        while (true) {
            final String command = scanner.next().toLowerCase().trim();

            switch (command) {
                case "add":
                    int number = scanner.nextInt();
                    list.add(number);
                    break;

                case "reverse":
                    list.reverse();
                    break;

                case "print":
                    System.out.println(list);
                    break;

                case "quit":
                    System.exit(0);
            }
        }
    }
}

Hope that helps.