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

Question

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!

"In my default constructor, I have the head.next node pointing to tail.prev" You don't? — michaelsnowden
– michaelsnowden, Commented Jul 29, 2016 at 1:47
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
– Tim Biegeleisen, Commented Jul 29, 2016 at 1:49
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
– rcgldr, Commented Jul 29, 2016 at 2:02
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, Commented Jul 29, 2016 at 2:25
@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
– rcgldr, Commented Jul 30, 2016 at 23:55

Andreas · Accepted Answer · 2016-07-29 02:25:20Z

4

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.

answered Jul 29, 2016 at 2:25

Andreas

160k13 gold badges164 silver badges262 bronze badges

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

3 Comments

Linuxn00b Over a year ago

I'm aware that head is not involved, however the add method is not working at all without some implementation of head.

Andreas Over a year ago

@Linuxn00b What do you mean that it's not working? If the list is empty and you're adding A, TAIL.prev is HEAD, so the first 2 bullets above (C.prev = TAIL.prev and TAIL.prev.next = C) will have the effect of A.prev = HEAD and HEAD.next = A, so HEAD is updated, even if not mentioned by name in the code. That is the whole point of using sentinel nodes: There is no special handling for first/last value node.

Linuxn00b Over a year ago

I had my order of operations incorrect. Sorry. I had tail.prev = newNode before tail.prev.next = newNode.

rcgldr · Accepted Answer · 2016-07-30 18:39:08Z

1

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.

edited Jul 30, 2016 at 18:39

answered Jul 30, 2016 at 17:51

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Comments

Maybe_Factor · Accepted Answer · 2016-07-29 02:30:13Z

-1

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.

answered Jul 29, 2016 at 2:30

Maybe_Factor

3803 silver badges10 bronze badges

4 Comments

Maybe_Factor Over a year ago

Can I get some comments about my answer from the downvoters? What's the problem?

Andreas Over a year ago

Question code is doing exactly what top 80% of your answer says to do, though I don't understand what you mean by this line: mid.prev = head (previous tail.prev). Question is doing newNode.prev = tail.prev, which is correct, not newNode.prev = head, so the "previous" comment is obscure. You cannot see the mistake in the code until you add a second element, and you answer doesn't in any way help identify that. Sure, you say the right thing in the last paragraph, but all the rest is just meaningless, i.e not useful.

Maybe_Factor Over a year ago

Makes perfect sense to me... is not understanding something really grounds for a downvote?

Andreas Over a year ago

You say "you want your list to look like this", and question code will make the list look like that, so how is that in any way helpful to figure out what is wrong? You also say "You start with a linked list Like this", which is exactly what question is doing, so what is the point of saying that? In short, the top 80% of the answer is just repeating the question, but making it sound like the question is not doing that. Not helpful.

Collectives™ on Stack Overflow

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

3 Answers 3

3 Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related