Java Doubly Linked List last node won't point to list properly

Question

I want to add a node to the end of my list, but I can't seem to connect the link between my first node and where it ends.

I know my logic can't be right because the only way I can sort of get it to work requires that I overwrite last and assign that to null. If I don't do this, the program goes into an infinite loop because my guess is that there isn't a node that = null to stop a loop from ending. I figured line 20 would create that new object to hold null, and then line 21 would link temp back to it.

public class LinkedListDeque {

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


private class DoubleNode {

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

    DoubleNode() {
    }

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

}


public void enqueue(String item) {

    temp = getNode(null); //returns pointer to last node in "first"

    System.out.println("\nenqueue\n***********");

    DoubleNode oldlast;        

    oldlast = temp;
    temp.item = item;

    last = temp;

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

line 20     temp = new DoubleNode();    
line 21     temp = oldlast;    

    DoubleNode last;              //will go into infinite loop w/out 
    last = temp;                  //these two lines

    System.out.println("last = " + last.item);   // = null
    System.out.println("temp = " + temp.item);   // = null

    if (isEmpty()) {            //returns true if first == null
        first = last;
    } else {
        oldlast.next = last;

    }
    N++;
 }

}

Answer 1

In theory,
get the last node by looping through the list
assign last = that last node
make new object()
assign new object = last.next, which links the new object to the original list and make it = null

but this doesn't actually work. It's weird how simple the idea is, yet so hard to apply

Answer 2

I think your implementation could look like this:

public final class LinkedListDeque {

    private Node root;
    private int size;

    public void enqueue(String val) {
        Node node = new Node(val);

        if (size == 0) {
            node.next = node;
            node.prev = node;
            root = node;
        } else {
            Node last = root.prev;

            last.next = node;
            node.prev = last;
            node.next = root;
            root.prev = node;
        }

        size++;
    }

    public String dequeue() {
        if (size == 0)
            throw new NoSuchElementException();

        String val = root.val;

        if (size == 1) {
            root.next = null;
            root.prev = null;
            root = null;
        } else {
            Node head = root.next;

            root.prev.next = head;
            head.prev = root.prev;
            root.next = null;
            root.prev = null;
            root = head;
        }

        size--;
        return val;
    }

    private static class Node {

        private final String val;
        private Node next;
        private Node prev;

        public Node(String val) {
            this.val = val;
        }
    }

}

Answer 3

If your LinkedList maintains the first and last properly, you shouldn't need to do any traversing in order to put the new node at the end. You just need to set the current last next to the new node, and the new node previous to the current last, then replace current last with the new node.

When you dequeue, just make sure that you clear both first and last if last.getNext() == null so the next enqueue correctly sets first and last.

public class LinkedListDequeue<T> {
    private DoubleNode first;   // First node
    private DoubleNode last;    // Last node
    private size = 0;

    public static class DoubleNode<T> {
       private T value;
       private DoubleNode prev;
       private DoubleNode next;

       ...
    }

    public DoubleNode enqueue(DoubleNode<T> node) {
        if (first == null) {
            // If empty set node to the first and last node
            first = last = node;
        } else {
            // Set the current last node next -> new node and then the
            // new node previous to the last and then set the new node
            // as last.
            last.setNext(node);
            node.setPrev(last);             
            last = node;    
        }

        size++;
        return node;
    }

    public DoubleNode enqueue(T value) {
        return enqueue(new DoubleNode(value));
    }
}