0

我是数据结构的新手。在学习它时，我无法理解这两种链表实现之间的区别。

无论我在哪里看到最多，每个人都在使用下面提到的链表的第一个实现。

通过两个类：

 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.

}

但这是我的问题，为什么我们需要两个类来实现它。假设我使用以下实现：

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; 
    }
}

现在我可以在一个班级里用它做所有的事情，不是吗？请告诉我这种方法有什么问题，因为它非常混乱。

4

2 回答 2

1

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.

于 2021-03-01T09:58:46.783 回答
0

一类方法看起来相当有限，不是吗？使用链接列表的好处是可以轻松访问它的头部和尾部。拥有一个链表可以显着提高运行时间，而不是遍历每个节点来寻找尾部。说到删除，这绝对是数据结构课程中的一个关键话题，二分类方法比一分类方法实用得多。在二分类方法中，您可以随意迭代和重新分配头或尾。在 one-class 方法中，首先创建的节点意味着一切，并且由于您无法定义头部或尾部，因此在删除发生后跟踪所有节点变得非常具有挑战性。TLDR：二类方法允许更轻松的访问，反过来，更快的运行时。

于 2021-03-01T09:44:52.007 回答