How to link the a circular linked list tail to the head of the list in Java?

Question

I'm trying to insert at the front and insert at the back of the list. However, I've got those methods to work to a certain extent in the Circular Linked List class.

My problem is, I can't seem to figure out how to link the tail with the head of the list. I have got the head to point to the tail though.

So after executing the below lines of code:

list.InsertAtFront(0);

list.InsertAfter(0, 4); // Inserting the 4 after 0 which was inserted above...

The result I got was

[Data: ID = 0 |{Previous: 4}, {Next: 4}] -> [Data: ID = 4 |{Previous: 0}, {Next: null}]

What should be here for the second insert, Where next is pointing to null {Next: null} it should be pointing the the head of the list {Next: 0}.

I would really appreciate the help guys!

I'll show what I have so far below...

THE NODE CLASS

package circular_linked_list;

public class Node {
    private int id;
    private Node next_node;
    private Node previous_node;

    public Node(){
        this.id = 0;
        this.next_node = null;
        this.previous_node = null;
    }

    public Node(int id, Node next_node, Node previous_node){
        this.id = id;
        this.next_node = next_node;
        this.previous_node = previous_node;
    }

    public Node(int id){
        this.id = id;
        this.next_node = null;
        this.previous_node = null;
    }

    public Node(Node node){
        this.id = node.GetId();
        this.next_node = node.GetNextNode();
        this.previous_node = node.GetPreviousNode();
    }

    public void SetId(int id) {
        this.id = id;
    }

    public void SetNextNode(Node next_node) {
        this.next_node = next_node;
    }

    public void SetPreviousNode(Node previous_node) {
        this.previous_node = previous_node;
    }

    public int GetId() {
        return this.id;
    }

    public Node GetNextNode() {
        return this.next_node;
    }

    public Node GetPreviousNode() {
        return this.previous_node;
    }

    public void NodeDetails(){
        if(this.previous_node != null && this.next_node != null){
            System.out.print("[Data: __ID = " + this.id + "__ |{Previous: " + this.previous_node.GetId() + "}, {Next: "+ this.next_node.GetId() + "}] -> ");
        }
        else if(this.previous_node != null){
            System.out.print("[Data: __ID = " + this.id + "__ |{Previous: " + this.previous_node.GetId() + "}, {Next: null}] -> ");
        }
        else if(this.next_node != null){
            System.out.print("[Data: __ID = " + this.id + "__ |{Previous: null}, {Next: "+ this.next_node.GetId() + "}] -> ");
        }
        else{
            System.out.print("[Data: __ID = " + this.id + "__ |{Previous: null}, {Next: null}] -> ");
        }
    }
}

THE CIRCULAR LINKED LIST CLASS

package circular_linked_list;


public class CircularLinkedList{
    private Node head;
    private Node tail;

    public CircularLinkedList(){
        this.head = null;
        this.tail = null;
    }

    public CircularLinkedList(Node head, Node tail){
        this.head = head;
        this.tail = tail;
    }

    public void SetHead(Node head){
        this.head = head;
    }

    public void SetTail(Node tail){
        this.tail = tail;
    }

    public Node GetHead(){
        return this.head;
    }

    public Node GetTail(){
        return this.tail;
    }

    public void InsertAtFront(int data){
        Node new_node = new Node(data);

        if( new_node != null){
            // If the list is not empty then...
            if(this.head != null){
                this.head.SetPreviousNode(new_node); // Set the list head's previous node to point to the new node.
                new_node.SetNextNode(this.head); // Set the new node's next node to point to the current list head.
                new_node.SetPreviousNode(this.tail); // Set the previous node of the head of the list to point to the tail of the list
            }

            this.head = new_node; // Set the list head to point to the new node
            this.FindTail(); // Set the tail of the list.
        }
        else{
            System.out.print("Sorry, the list is full!");
        }
    }

    public void InsertAfter(int target, int data){
        Node new_node = new Node(data);

        if(new_node != null){
            Node target_node = this.head;
            boolean found = false;

            // This while loop will loop to find if a node is equal to the value passed as target.
            while(target_node != null){
                if(target_node.GetId() == target){
                    // If the target is found then break the loop to keep this current node as the target node.
                    found = true;
                    break;
                }

                // Assigning the target node next node to the target node.
                target_node = target_node.GetNextNode();
            }
     
            // If the target was found then...
            if(found){
                new_node.SetPreviousNode(target_node); // Set the previous node of the new node to point to the target node.

                // Set the next node of the new node with the target node's next node to continue to link.
                new_node.SetNextNode(target_node.GetNextNode());

                // If the target node's next node is not null, then set the target node's next node->previous node to point to the new node.
                if(target_node.GetNextNode() != null){
                    target_node.GetNextNode().SetPreviousNode(new_node);
                }

                target_node.SetNextNode(new_node); // Set the target node's next node to point to the new node.

                // Setting the tail of the list...
                this.FindTail();
            }
            else{
                System.out.println("Sorry, but the integer " + target + " was not found in the list!\n");
            }
        }
        else{
            System.out.println("Sorry, the list is full!\n");
        }
   }

   public void DisplayList(){
       Node current_node = this.head;

        while(current_node != null){
            current_node.NodeDetails();

            current_node = current_node.GetNextNode();
        }
   }

   private void FindTail(){
       Node current_node = this.head;

        // Traversing from the start of the list to the end to get the tail.
        while(current_node.GetNextNode() != null){
            current_node = current_node.GetNextNode();
        }

        this.head.SetPreviousNode(current_node); // Updating the head of the list previous node.

        this.SetTail(current_node); // Set the tail of the list with the last node.
    }
}

THE MAIN CLASS

package circular_linked_list;


public class Main {
    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();

        // Inserting at the front of the list
        list.InsertAtFront(0);
        
        // Inserting 4 right after the 0
        list.InsertAfter(0, 4);

        // To display the nodes/elements in the list
        list.DisplayList();
    }
}

Answer 1

The main issue in your code is that you assume there will be a next reference that is null, but that is in contradiction with the principle of a circular linked list. In a circular linked list, you can always go from one node to the next and run endlessly in circles. So the principle is: none of the next references should be null!

This means you'll have to adapt your code at several places where you either set a null, or check against a null value.

Some other remarks:

• Let the Node constructor make the new node refer to itself via its next and previous members. This way you avoid storing null there from the very start. It is like making a one-node circular linked list on its own.

• The loops should not check for null, but instead detect that you have cycled around and got back to the head node.

• There is some code repetition for the two flavours of insertion-methods you have. This linking of the new node with the existing nodes should be done at one place only. I suggest making a separate method for that.

• There really is no need to have a tail member in your class, because that tail is always going to be this.head.GetPreviousNode() (unless of course your list is empty). So I would just drop that tail member and work with that expression instead. This will save you from keeping that tail reference up to date.

• The insertAfter method currently performs a find for the target value in the list. It would be nicer, if you placed this logic in a separate find method, so it could be re-used elsewhere (if needed).

Here is the corrected Node class:

public class Node {
    private int id;
    private Node next_node;
    private Node previous_node;

    public Node(){
        this.id = 0;
        // Make a node refer to itself by default -- this is practical in a circular list
        this.next_node = this;
        this.previous_node = this;
    }

    public Node(int id, Node next_node, Node previous_node){
        this.id = id;
        this.next_node = next_node;
        this.previous_node = previous_node;
    }

    public Node(int id){
        this.id = id;
        // Make a node refer to itself by default -- this is practical in a circular list
        this.next_node = this;
        this.previous_node = this;
    }

    public Node(Node node){
        this.id = node.GetId();
        this.next_node = node.GetNextNode();
        this.previous_node = node.GetPreviousNode();
    }

    public void SetId(int id) {
        this.id = id;
    }

    public void SetNextNode(Node next_node) {
        this.next_node = next_node;
    }

    public void SetPreviousNode(Node previous_node) {
        this.previous_node = previous_node;
    }

    public int GetId() {
        return this.id;
    }

    public Node GetNextNode() {
        return this.next_node;
    }

    public Node GetPreviousNode() {
        return this.previous_node;
    }

    public void NodeDetails(){
        System.out.print("[Data: __ID = " + this.id + "__ |{Previous: " + this.previous_node.GetId() + "}, {Next: "+ this.next_node.GetId() + "}] -> ");
    }
}

And the corrected CircularLinkedList class:

public class CircularLinkedList{
    private Node head; // No need for a tail

    public CircularLinkedList(){
        this.head = null;
    }

    public CircularLinkedList(Node head){
        this.head = head;
    }

    public void SetHead(Node head){
        this.head = head;
    }

    public Node GetHead(){
        return this.head;
    }

    public void InsertAtFront(int data){
        if (this.head == null) {
            this.head = new Node(data);
        } else {
            insertAfter(this.head.GetPreviousNode(), data);
            this.head = this.head.GetPreviousNode();
        }
    }

    public Node find(int target) {
        Node target_node = this.head;
        while (target_node != null) {
            if(target_node.GetId() == target) {
                return target_node;
            }
            target_node = target_node.GetNextNode();
            if (target_node == this.head) break; // running in circles
        }
        return null;
    }

    // Add this method to avoid code repetition
    public void insertAfter(Node target_node, int data) {
        Node new_node = new Node(data, target_node.GetNextNode(), target_node);
        target_node.SetNextNode(new_node);
        new_node.GetNextNode().SetPreviousNode(target_node);
    }

    public void InsertAfter(int target, int data){
        Node target_node = find(target);
        if (target_node != null) {
            insertAfter(target_node, data);
        } else{
            System.out.println("Sorry, but the integer " + target + " was not found in the list!\n");
        }
   }

   public void DisplayList(){
        Node current_node = this.head;

        while (current_node != null) {
            current_node.NodeDetails();
            current_node = current_node.GetNextNode();
            if (current_node == this.head) break; // running in circles
        }
   }
}