Circular Doubly Linked List Java - Explanation

Question

at the moment, I am programming a circular doubly linked list and my task is completed, but I have a slight problem in understanding the code 100%.

This is the code:

if (counter == 0) {
        startpoint = newNode;
        startpoint.next = startpoint;
        startpoint.prev = startpoint;
        head = startpoint;
        currentNode = newNode;

    } else {
        newNode.prev = startpoint.prev;
        newNode.next = startpoint;
        startpoint.prev.next = newNode; <- this is, where I have problems
        startpoint.prev = newNode;
        head = startpoint;
        currentNode = newNode;
    }
    counter++;
}

The first part is completeley clear and just describes, that the first node (if there is no other node) is going to point on itself, when the next or first-method is called. After the else-statement, the first line describes that the first node can point to the second and the second to the previous node, right? The second line after else just describes, that the last node points onto the first one. The fourth line than describes, that the first node points onto the last node, if the prev-method is called and so the circle is closed. But what exactly does the third line describes? The code definitely works.

Thank you for your time!

Greets Dominik

Initially startpoint.prev points to the "last node before startpoint" in the circular list. Thus, startpoint.prev.next = newNode says that the successor of that node is newNode — Federico
– Federico, Commented Jun 11, 2018 at 12:52
You're trying to set a value on a reference that doesn't exist yet (startpoint.prev) by doing startpoint.prev.next = newNode; before startpoint.prev = newNode;. — user1205577
– user1205577, Commented Jun 11, 2018 at 12:54

jhamon · Accepted Answer · 2018-06-11 12:59:00Z

1

Your list is circular.

startpoint.previs the element before the startpoint, so it's the last element of the list.

Let's take an example, this is your list: A>B>C, you try to add D.

This line: startpoint.prev.next = newNode; will link the current last element (C as A.prev == C) to your new element. (C.next = D)

this line startpoint.prev = newNode; will set the new element as the last element of the list (A.prev = D).

answered Jun 11, 2018 at 12:59

jhamon

3,7014 gold badges29 silver badges39 bronze badges

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

1 Comment

dbljn Over a year ago

Aah okay, I got it now! Thanks to you all! :)

david a. · Accepted Answer · 2018-06-11 13:03:41Z

1

The code inserts newNode just before startpoint. The 3rd line of the else statement simply updates the node before the startpoint so that it's next field references the new node.

To make it more clear, one can rewrite the line like this:

    Node nodeBeforeStarpoint = startpoint.prev;
    nodeBeforeStartpoint.next = newNode;

answered Jun 11, 2018 at 13:03

david a.

5,28924 silver badges25 bronze badges

Collectives™ on Stack Overflow

Circular Doubly Linked List Java - Explanation

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related