Adding to the end of a Doubly-Linked List Data Structure in Java

0
votes

I am working on my Computer Science studies and I am having some difficulty with adding a Node to the end of a doubly linked-list data structure. I understand that the new node points to the tail and the tail points to it, thus I have this:

public boolean add(E element) 
    {
        // TODO: Implement this method
        LLNode<E> newNode = new LLNode<E> (element);
        if (element == null) {
            throw new NullPointerException("Element can not store a null reference!");

        } else {
            newNode.next = tail;
            newNode.prev = tail.prev;

            tail.prev = newNode;
            head.next = newNode;

        }
        size++;
        return true;
    }

The issue I'm having is trying to connect the head node (via head.next to the correct node).

In my default constructor, I have the head.next node pointing to tail.prev. However in the add method, I could not figure out where head.next would point since each time you add a new node, head has to point to the first node in the LinkedList Data Structure. Here is the default constructor:

public MyLinkedList() {
        // TODO: Implement this method
        size = 0;
        /*create two empty nodes at the head and the tail of the linked list*/
        head = new LLNode<E> (null);
        tail = new LLNode<E> (null);
        head.next = tail;
        tail.prev = head;
        head.prev = null; //Head is a sentinel node with no node prior to it
        tail.next = null; //tail is a sentinel node with no node after it
}

Please point me (no pun intended) to the right direction. Thanks!

3
javadata-structureslinked-list
"In my default constructor, I have the head.next node pointing to tail.prev" You don't? – michaelsnowden
Element can not store a null reference! ... says who? The marker for the end of a list is not that the element being stored is null, it is that the next pointer is null. – Tim Biegeleisen
You don't need two dummy nodes for a linked list. One dummy node is enough, where dummy.prev = first node or null, and dummy.next = last node or null. The first nodes prev pointer and the last nodes next pointer should be null. You could also use two references to node instead of a dummy node: head and tail. – rcgldr
The purpose of this exercise isn't about whether or not one needs two sentinel nodes to formulate a linked list. That's certainly not the case. The case in hand here is to HAVE two sentinel nodes and to implement a Doubly linked list as per UCSDs MOOC. – Linuxn00b
@Linuxn00b - the only ordering requirement is using tail.prev (or a copy of it) before updating it: newNode.prev = tail.prev; tail.prev.next = newNode; tail.prev = newNode; or newNode.prev = tail.prev; newNode.prev.next = newNode; tail.prev = newNode; or newNode.prev = tail.prev; tail.prev = newNode; newNode.prev.next = newNode; . – rcgldr

3 Answers

4
votes

Draw on paper what you have to do.

E.g. if you list current has two elements (A and B), you chain will be:

HEAD <-> A <-> B <-> TAIL

To add a new element (C), your end result should be:

HEAD <-> A <-> B <-> C <-> TAIL

which means the following updates:

  • C.prev = B or more precisely: C.prev = TAIL.prev
  • B.next = C or more precisely: TAIL.prev.next = C
  • C.next = TAIL
  • TAIL.prev = C

As you can see, HEAD is not involved in this, so your line head.next = newNode is wrong.

1
votes

This should work.

public boolean add(E element) 
    {
        LLNode<E> newNode = new LLNode<E> (element);
        if (element == null) {
            throw new NullPointerException("Element can not store a null reference!");
        } else {
            newNode.next = tail;       // set new.next to tail
            newNode.prev = tail.prev;  // set new.prev to prior last
            tail.prev.next = newNode;  // set prior last.next to new last
            tail.prev = newNode;       // set tail.prev to new last
            size++;
        }
        return true;
    }

I'm not sure if the check for null element is needed in an add function, although a null check may be needed elsewhere.

-1
votes

I think you need to rethink how you handle the linked list... You start with a linked list Like this:

head.next = tail
head.prev = null
tail.next = null
tail.prev = head

and when you add something to the end of the list, lets call it mid, you want your list to look like this:

head.next = mid (set by using tail.prev.next = mid)
head.prev = null
mid.next = tail (the new node is the end of the list)
mid.prev = head (previous tail.prev)
tail.next = null
tail.prev = mid (setting the new node to be the new end of the list)

So your mistake is that when you are adding a node, you shouldn't be using the head node explicitly, like you are doing. All operations should be done in terms of the tail of the list. I've it leave it up to you to turn this into code.