implementation of a linked list in java

Question

I was reading about linked lists in java , I did program this code , when I run it I get 3 as output , it should print out a reverse order of the inserted numbers as following : 10 7 3 .. what is wrong with my code?

public class List {
    private class ListNode {
        private int contents;
        private ListNode next;

        ListNode(int contents) {
            this.contents = contents;
            this.next = null;
        }
    }

    private ListNode head;

    public List() {
        head = null;
    }

    public void insert(int contents) {

        ListNode newNode = new ListNode(contents);
        if (head == null) {
            head = newNode;
        }

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

        current = newNode;

    }

    public void reverse() {

        ListNode current = head;
        ListNode nodeNext = current.next;

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

        head = current;
    }

    public String toString() {

        String s = "";
        ListNode current = head;
        while (current != null) {
            s = current.contents + s;
            current = current.next;
        }

        return s;
    }

    public static void main(String[] args) {

        List l = new List();
        l.insert(3);
        l.insert(7);
        l.insert(10);
        l.reverse();
        System.out.println(l.toString());

    }
}

Thanks

Answer 1

private ListNode head;
private ListNode tail;
public void insert(int contents) {

    ListNode newNode = new ListNode(contents);
    if (head == null) {
        head = newNode;
        tail = newNode;
        return;
    }
    tail.next = newNode;
    tail = newNode;
}

Keep a tail node reference for O(1) insertion.

Your reverse() method is a bit wrong:

// this loop will run forever if there are more than 1 nodes
while (nodeNext != null) {
    current.next = null;
    nodeNext.next = current; // you lose the reference to the entire list here
    current = nodeNext;
}

Rewrite the function:

public void reverse() {
    ListNode cursor = head;
    ListNode newHead = null;

    while (cursor != null) {
        ListNode next = cursor.next;
        cursor.next = newHead;
        newHead = cursor;
        cursor = next;
    }
    head = newHead;
}

Doing cursor.next = newHead, loses the original reference to cursor.next. And so you need to take the reference of cursor.next in a temporary variable: ListNode next = cursor.next;

A print function

public void print() {
    ListNode cursor = head;
    while (cursor != null) {
        System.out.println(cursor.contents);
        cursor = cursor.next;
    }
}

Answer 2

Your insert method doesn't connect the new node to the last node of the existing list. You have to assign the new node to node.next of the last node of the existing list :

public void insert(int contents) {

    ListNode newNode = new ListNode(contents);
    if (head == null) {
        head = newNode;
        return;
    }

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

    current.next = newNode;

}