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

you never set next when inserting value. Using a debugger, you would have quickly found that. — jhamon
– jhamon, Commented Dec 6, 2016 at 10:07
you mean like this public void insert(int contents, ListNode next) { — senshi nakamora
– senshi nakamora, Commented Dec 6, 2016 at 10:08
How did you plan this ? Did you write what you had in mind or did you do that on paper first ? — AxelH
– AxelH, Commented Dec 6, 2016 at 10:17
@jhamon thanks .. why when I write System.out.println(l.reverse()); in the main method eclipse says : The method println(boolean) in the type PrintStream is not applicable for the arguments (void) — senshi nakamora
– senshi nakamora, Commented Dec 6, 2016 at 13:15

Eran · Accepted Answer · 2016-12-06 10:08:21Z

4

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;

}

answered Dec 6, 2016 at 10:08

Eran

395k57 gold badges726 silver badges793 bronze badges

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

8 Comments

senshi nakamora Over a year ago

when I wrote current.next = newNode; eclipse said : Null pointer access: The variable current can only be null at this location the code does not work thanks

Eran Over a year ago

@senshinakamora Did you notice that I changed the loop's condition to while (current.next != null)?

senshi nakamora Over a year ago

no I did not sorry.. now when I run it I do not see any thing in the output .. Is there any wrong with my toString method? thanks

Eran Over a year ago

@senshinakamora The problem is in your reverse method, which seems to contain an infinite loop.

Eran Over a year ago

@senshinakamora BTW, your toString already prints the list in reverse order. Perhaps there's no need to call reverse.

|

denvercoder9 · Accepted Answer · 2016-12-06 13:21:01Z

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

edited Dec 6, 2016 at 13:21

answered Dec 6, 2016 at 10:47

denvercoder9

3,0223 gold badges30 silver badges41 bronze badges

3 Comments

senshi nakamora Over a year ago

thanks .. why when I write System.out.println(l.reverse()); in the main method eclipse says : The method println(boolean) in the type PrintStream is not applicable for the arguments (void)

denvercoder9 Over a year ago

@senshinakamora Because the reverse method I have written doesn't send anything back. The type is void. You are passing the void type(which is not a type) to println() and there is no method in PrintStream that takes a void arguement. Eclipse assumes the first kind of println which takes boolean and so it gives that error message

denvercoder9 Over a year ago

I've added a print function. Call l.reverse() and then call l.print().

Collectives™ on Stack Overflow

implementation of a linked list in java

2 Answers 2

8 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related