The drawback in a basic singly linked list implementation using a node class



I’m following the CCI book and it has the following as the most basic Linked List implementation.

class Node { 
    
    Node next = null;
    int data;

    public Node (int data) { this.data = data; }

    void appendToTail(int d){ 

        Node iterHead = this; 
        Node newNode = new Node(d);
        while(iterHead.next != null){ 
            iterHead = iterHead.next;
        }
        iterHead.next = newNode;
    }
}

I understand that we will be accessing the list through a reference to the head node here. The author mentions that this implementation is problematic because -and I paraphrase , “if multiple objects need a reference to the list, and the head changes, some old objects might be pointing to the old head”

I don’t quite get what she means by “changing the head” in this context and how it will effect other objects that uses the list reference. Maybe someone can help me understand this with an example. First time poster here so I would appreciate any help.

Answer

Linked List is a data structure that is easy to add and delete nodes from the list, and these operations should be considered as intended usage.

The main reason it may seem confusing is because the Linked list above lacks implementation to make the structure actually useful, and those are what may cause problems.

When the author says problematic when “changing the head”, she may be considering some of the following scenarios: Add head

Where we add a new node before head and make it the new head. In cases that we need to iterate through the list, having a reference to the old head means that anything before the current head may not be considered.

Changing Heads

Where we add new nodes and discard the old head for whatever reason it is no longer useable. A reference to the old head may read data that shouldn’t exist in the moment.

There may be more scenarios, but the point is you have to be careful what references the linked list. I often maintain a null value head node that always stays in front of everything.

Happy coding!



Source: stackoverflow