Java Linked List unable to add item to end

Question

Can't seem to add a last element properly. I hold the last item in a temp node, then create a new node. Then I link both previous and next for each node, then point the last node to a new null node. But that null node doesn't seem to be part of the list when I go to my print() method.

Seems like it should be as easy as my push method, but I just can't seem to get it work like it.

public class LinkedListDeque {

public DoubleNode first = new DoubleNode(null);
public DoubleNode last = new DoubleNode(null);
public DoubleNode temp;
public int N;

LinkedListDeque() {
    first.next = last;
    last.prev = first;

}

public static void main(String[] args) {

    LinkedListDeque link = new LinkedListDeque();

    link.push("banana");
    link.printList();

    link.enqueue("gorilla");
    link.printList();


    link.enqueue("spam");

}


//nested class

private class DoubleNode {

    String item;
    int counter = 0;
    DoubleNode next;
    DoubleNode prev;

    DoubleNode(String i) {
        this.item = i;
    }

}

public void push(String item) {

    System.out.println("\npush()\n******");
    if (first.item == null) {
        first.item = item;
        first.counter++;
    } else {

        System.out.println("last.item = " + last.item);
        DoubleNode node = new DoubleNode(item);
        first.prev = node;
        node.next = first;
        first = node;

    }

}



 public void enqueue(String item) {
    System.out.println("\nenqueue()\n***********");
    System.out.println("adding \"" + item + "\" to the end");

    if (last.item == null) {
        DoubleNode node = new DoubleNode(null);                     //holds null node to end list
        last.item = item;
        last.next = node;
    } else {
        DoubleNode node = new DoubleNode(null);
        System.out.println("node = " + node.item);                  //= correct item

        temp = last;
        last = new DoubleNode(item);                                //creating a new last node

        System.out.println("temp = " + temp.item);                  //corect
        //reconnect the links
        temp.next.item = last.item;

        System.out.println("temp.prev = " + temp.prev.item);        //correct
        System.out.println("temp.next = " + temp.next.item);        //correct
        System.out.println("last = " + last.item);                  //correct
        System.out.println("last.prev = " + last.prev);             //correct

        last.prev = temp;

        System.out.println("last.prev = " + last.prev.item);        //correct

        last.next = node;
        System.out.println("last.next = " + last.next.item);        //= null to end list

        System.out.println("\n\nfirst = " + first.item);                                //correct
        System.out.println("first.next = " + first.next.item);                          //correct
        System.out.println("first.next.next = " + first.next.next.item);                //correct
        System.out.println("first.next.next.next = " + first.next.next.next.item);      //"null pointer exception"
}

public void printList() {
    System.out.println("\nprintList():\n********");
    temp = first;

    int i = 0;
    if (first.item == null) {
        temp = first.next;
    }
    System.out.println("temp = " + temp.item);
    while (temp.item != null) {
        i++;
        System.out.println(i + " " + temp.item);
        temp = temp.next;
    }
    System.out.println();
}

Answer 1

Let's see what is actually happening: the initial state:

• first contains null, first.next is last, last contains null
• push: first does not contain null any more, still points to last,with null
• enque: last.item is null, so the first cae is triggered, now the list is like: banana -> gorilla -> null and last points to gorilla
• enque again: now the else is triggered. If you have a look at the code, you will notice that temp.next is not touched anywhere. This means that the node that was the last node before the enque,and was copied to temp still points to the null node.
• this finally results in a null pointer exception.

What is missing: something like temp.next=last, after the last node is created.

What actually happens looks like this:

---> last ---> closing-null

---> temp ---> closing-null

---> last

It seems you could implement this more cleanly without the null nodes closing the list.

Then you could do something like this:

node=new Node(item);
last.next=node;
node.prev=last;
last=node;

Answer 2

I won't give you the whole code but I will visualize it. You can come up with code easily after this.

Next is ---> and Previous is <--- and last points towards last node and first towards first node

Lets say you have this list.

Banana ---> Orange ---> Gorilla ---> null
       <---        <---         
  ^                       ^
  |                       |
first                    last
// First's previous and last's next is null.

You want to add Mango at the end. You create a new node

DoubleNode node = new DoubleNode("Mango");
<--- Mango --->
// Note: When you create a new node by default both next and previous are null. 
// You don't need to point them to null later

Step 1:

last.next(newNode);
Banana ---> Orange ---> Gorilla ---> Mango 
       <---        <---    
  ^                       ^
  |                       |
first                    last  

Step 2:

newNode.previous(last);
Banana ---> Orange ---> Gorilla ---> Mango 
       <---        <---         <---
  ^                       ^
  |                       |
first                    last

Now we have new last so we will update last

last = newNode
Banana ---> Orange ---> Gorilla ---> Mango 
       <---        <---         <---
  ^                                    ^
  |                                    |
first                                last

From constructor we know Mango's next is already null so newNode.next(null); is unnecessary.

Reasons you could be getting nullpointerexception

After adding first element your list looks like this

null <--- Banana ---> null      null
             ^                   ^
             |                   |
           first                last

Technically you should make both first and last point towards banana since you don't. When you enqueue something it would be let's say gorilla. It would be

null.item = "Gorilla"
null.next = null