Implementation of linked list using single class?

Question

I am new to data structures. While learning it, I am at a point where I am not able to understand the difference between these two implementations of linked lists.

Wherever I have seen mostly, everyone is using the first implementation of linked list which is mentioned below.

By two classes:

 class Node{
    int data;
    int value;
    Node next;
    Node(int data){
        this.data = data;
        this.next = null;
    }

    Node(int data, Node next){
        this.next = next;
        this.data = data;
    }
}

class LinkedList{
    Node head;
    LinkedList(Node head){
        this.head = head;
    }
    LinkedList(){
        this.head = null;
    }

    void insert(int data){
        //it will insert at the end
        //logic
     }
    //Other methods.

}

But here is my question, why do we need two classes to implement it. Let's say if I use below implementation:

class Node{
    int data;
    int value;
    Node next;
    Node(int data){
        this.data = data;
        this.next = null;
    }

    Node(int data, Node next){
        this.next = next;
        this.data = data;
    }

    void appendToTail(int d){
        Node node = new Node(4);
        Node traversal = this;

        while(traversal.next!=null){
            traversal = traversal.next;
        }
        traversal.next = n; 
    }
}

Now I can do all the things with it in single class isn't it? Please tell me what's the problem with this approach because its making very confused.

Answer 1

The one-class method looks rather limiting, does it not? The benefits of using a Linked List is for an easy way to access the head and tail of it. Having a Linked List improves runtime significantly, rather than going through each Node to find the tail. When it comes to deletion, which is definitely a crucial topic in a data structures course, the two-class method is much much more practical than the one-class method. In the two-class method, you can iterate through and reassign heads or tails as you please. In the one-class method, whichever node you create first means everything, and because you can't have a defined head or tail, keeping track of all the Nodes after deletions occur becomes significantly challenging. TLDR: two-class method allows for much easier access and in turn, faster runtimes.

Answer 2

In the second version, the Node class is also serving as a the head of a list. But the problem is that if you have a Node instance, you cannot tell if it is currently the head of the list or not.

Why does it matter?

Well consider what happens when you add a new element at the start of the list; e.g.

Node list1 = new Node(1, null);
Node list2 = new Node(2, list1);

Now, list1 could be either a list, or part of another list ... or both. There is no way of knowing which of these is the case simply by looking at the representation of the Node object itself.

Indeed, it is not difficult to come up with examples where mistakes can lead to the lists getting into states that are no longer "list like".

list2.next = list1;  // creates a cycle!

By contrast, in the version with distinct LinkedList and Node types, there is a clear distinction between the roles. And if you then make the Node class a private inner class of LinkedList, then the latter can manage the data structure to prevent undesirable structures (e.g. cycles) from being formed.

---

Now I can do all the things with it in single class isn't it?

It is true.

But the real point is that with two classes (and appropriate use of other Java language features) you can create an abstraction that will behave like a proper list at all times.

Please tell me what's the problem with this approach because its making very confused.

Indeed. Judicious use of abstraction reduces the confusion. By hiding the list data structures and the methods that manipulate them behind the abstraction boundary of your LinkedList class, you make it easier to write code that can safely use the lists.