I'm trying to add a node in a circular list in Java. The problem is that my list has only a head (without a tail). Here is my code:

import java.io.PrintStream;
import java.util.EmptyStackException;

public class CircularList {
    private Node head = null;

    private class Node {
        public Node(String payload, Node prev, Node next) {
            super();
            this.payload = payload;
            this.prev = prev;
            this.next = next;
        }

        private Node prev;
        private Node next;
        String payload = "";
    }
    public void push(String payload) {
        Node n = new Node(payload, null, null);
        if (isEmpty()) {
            head = n;
            n.next = n;
        } else {
            n.prev = head;
            n.next = head;
        }
    }

CodePudding user response：

Lets take some nodes.

< H - < A - < B -

This describes the connections of the nodes. A.next == H and A.prev == B.

H and B are special cases, where H is the head and B is the tail. Since the list is circular. Then H.next == B and B.prev == H.

When we push a node.

< N - < H - < A - < B -

Then we can see all of the assignments that need to change.

H = head;
B = H.next; // get the tail since you only have the head.
H.next = N;
N.prev = H;
N.next = B;
B.prev = N;
head = N;

CodePudding user response：

You're almost there. When the list is empty, that part works fine. But when the list is not empty, think through what needs to happen, which is 4 things:

• The 'head's previous node needs to become the new node.
• The new node's 'next' needs to point at head.
• The new node's 'previous' needs to point at what used to be head.prev.
• What used to be head.prev's next pointer needs to point at the new node.

You'll need some temp variables to take care of all of that.

CodePudding user response：

This article will help you I believe