javalistalgorithmdata-structuressingly-linked-list

What happens to the lost part of a singly Linked list when I am introducing a loop at the middle?


I have created a singly linked list, and this is how it looks after displaying it:

19-->85-->50-->20-->33-->9-->1-->7-->null

I have created a method that can add a node to a any position of the list.

public void add_node_any(int value , int position) {
    ListNode node = new ListNode(value);
    if (position == 1) {
        node.next = head;
        head = node;
    }
    else {
        ListNode previous = head;
        int count = 1;
        while (count < position - 1) {
            previous = previous.next;
            count++;
        }
        previous.next = node;
        node.next = previous.next;
    }
}

I was trying to add a node to the third position.

single.add_node_any(2, 3);

And I realized that:

previous.next = node;
node.next = previous.next;

...is creating a loop. Also I know that due to this loop I can't access the nodes from 50 onwards. So my question is what is happening to those nodes? I have seen statements saying that still these nodes are a part of the list. They are just not accessible.

If that is still a part, how does that happen? I mean, while there is no connection between the repeating node (2) and the 50 (next in the loop), how is that possible to keep the connection with the list?

Full code

class SLL_implementation_Test_09_04 {
    private  listNode head;

    private  static class listNode {
        private int data;
        private listNode next;

        public listNode(int data) {
            this.data = data;
            this.next = null;
        }
    }   

    //Display the linked list
    public void Display() {
        listNode current = head;
        while (current != null) {
            System.out.print(current.data + "-->");
            current = current.next;      
        }   
        System.out.print("null"); 
    }

    //Display the length of the linked list
    public int SLL_length() {
        int count = 0;
        listNode current = head;
        while (current != null) {
            count++;
            current =current.next; 
        }   
        return count;
    }

    //Add new nodes | create a linked list from the beginning
    public void add_node_first(int value) {
        listNode newnode = new listNode(value);
        newnode.next = head;
        head = newnode;
    }

    //Add new nodes to the end of the linked list
    public void add_node_last(int value) {
        listNode newnode = new listNode(value);
        if (head == null) {
            head = newnode;
            return;
        }
        listNode current = head;
        while(current.next != null) {
            current = current.next;
        }
        current.next = newnode;
    }

    //Add a new node to a given possition
    public void add_node_any(int value, int position) {
        listNode node = new listNode(value);
        if (position == 1) {
            node.next = head;
            head = node;
        }
        else {
            listNode previous = head;
            int count = 1;
            while (count < position-1) {
                previous = previous.next;
                count++;
            }
            previous.next = node;
            node.next = previous.next;
        }
    }
}

In the main method

    public static void main(String args[]) {
        SLL_implementation_Test_09_04 single = new SLL_implementation_Test_09_04();
        single.add_node_last(20);
        single.add_node_first(50);
        single.add_node_first(85);
        single.add_node_first(19); 
        single.add_node_last(33);
        single.add_node_last(9);
        single.add_node_last(1);
        single.add_node_last(7);
        single.add_node_any(2, 9);
        single.Display();
    }

Solution

  • I have seen statements saying that still these nodes are a part of the list. They are just not accessible.

    A reference to these statements would be interesting, but it is wrong. The node that was previous.next before your code assigned something else to that attribute, is no longer part of the list.

    how is that possible to keep the connection with the list?

    You are absolutely right. The definition of "linked list" includes that nodes are linked in a chain of references, one to the next. If a node is "just not accessible", then it is no longer in that chain, and by definition not part of the list.

    So my question is what is happening to those nodes?

    If there are no other references to the first node of the disconnected part of the original list, then it becomes available for garbage collection. This will cascade to the next node, ...etc. This makes no difference for the code, which cannot access these nodes, whether they are already garbage collected or not.

    Correction

    The correction is to replace this:

            previous.next = node;
            node.next = previous.next;
    

    with this:

            listNode temp = previous.next;
            previous.next = node;
            node.next = temp;