Java: LinkedList Reverse

Question

I am trying to implement the reverse function of my own LinkedList implementation. Using my implementation of LinkedList:

public class LinkedList<T> {
    public Node head;

    public LinkedList(){
        // Add HEAD
        head = new Node(null);
    }

    public void add(T data){
        getLastNode().next = new Node(data);
    }

    public void insert(int index, T data){
        if(index == 0){
            throw new Error(); // TODO: What is the Error Type?
        }

        Node current = head;

        for (int i = 0; i != index - 1 ; i ++) {
            current = current.next;
            if (current == null){
                throw new IndexOutOfBoundsException();
            }
        }

        Node next = current.next;
        Node newNode = new Node(data);
        current.next = newNode;
        newNode.next = next;
    }

    public T get(int index){
        return getNode(index).data;
    }

    public void delete(int index){
        if (index == 0){
            throw new IndexOutOfBoundsException("Cannot delete HEAD node");
        }

        Node prev = getNode(index - 1);
        Node next = prev.next.next;
        prev.next = null;

        prev.next = next;
    }

    public void reverse(){ // TODO: Last node links to a null node
        Node prev = null;
        Node current = head;
        Node next = null;

        while(current != null){
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        head = new Node(null);
        head.next = prev;
    }

    public void display(){
        Node current = head;

        String diagram = String.format("head->");
        while(current.next != null){
            current = current.next;
            diagram += String.format("%s->", current.data);
        }
        System.out.println(diagram);
    }

    private Node getNode(int index){
        Node node = head;

        for(int i = 0; i != index; i++){
            node = node.next;
            if(node == null){
                throw new IndexOutOfBoundsException();
            }
        }

        return node;
    }

    private Node getLastNode(){
        Node current = head;

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

        return current;
    }

    public class Node {
        private Node next;
        private T data;

        public Node(T data){
            this.data = data;
        }

        public Node getNext(){
            return this.next;
        }
    }
}

And this main function:

    LinkedList list = new LinkedList();
    list.add("e1");
    list.add("e2");
    list.add("e3");
    list.add("e4");

    list.display();
    list.reverse();
    list.display();

The displayed result is:

head->e1->e2->e3->e4->
head->e4->e3->e2->e1->null->

This has happened due to the fact that e1 is still connected to the head. If I use the implementation of reverse available online:

    Node prev = null;
    Node current = head;
    Node next = null;

    while(current != null){
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    head = prev;

Then the result will ditch e4: head->e3->e2->e1->null->

What am I doing here? Why is my implementation different than everybody else's?

Also: Why does everyone use a reverse function that has head as an argument which could be problematic if the developer enters a different node?

Jose Luis · Accepted Answer · 2016-04-02 15:05:29Z

1

You are using a first node as a head of your list. The solution for the reverse function is this:

    head.next = prev;

You have to preserve the 'head' node, but change its 'next' field.

The rest of the function don't change at all:

public void reverse(){ // TODO: Last node links to a null node
    Node prev = null;
    Node current = head.next;
    Node next = null;

    while(current != null){
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    head.next = prev;  // *** The only change ***
}

In your constructor you have:

public LinkedList(){
    // Add HEAD
    head = new Node(null);
}

then, 'head' is a Node that points to nothing initially.

In the reverse function, the 'head' node don't change, you don't need to create another out. But it has to point to the correct first Node.

If the list was empty, this 'head' points to null. If the list has only one Node, this 'head' points to it yet. If the list has more than one Node, this 'head' has to point to the last node.

Because of this, you need to change its 'next' field.

edited Apr 2, 2016 at 15:05

answered Apr 2, 2016 at 14:45

Jose Luis

9941 gold badge8 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

zed Over a year ago

Thanks this has solved it for me! Can you explain it more why this worked? Is my Implementation of LinkedList unusual or incorrect?

Jose Luis Over a year ago

I added a little explication. I'm sorry, my english is not very good. :-) I suggest to try another implementation of your LinkedList class, using 'head' to point to the first node of the list (if the list is empty, 'head' will be null). You have to change some of your funtions. :-)

Jose Luis Over a year ago

I don't looked at the rest of your implementation. In this case, having a 'head' as a Node, for me, is not correct, because it is not a Node, is the Head. If you implement it as another class (Head, for example) then is ok, but not necessary. In the Head you could have another data, for example, the number of elements of the list. But this Head class could be the same LinkedList.

Collectives™ on Stack Overflow

Java: LinkedList Reverse

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related