为什么链表需要一个父类

Question

这是一个一般的问题，也许与OOP概念有关。我刚开始在JAVA中实现DS（数据结构）。 我试图实现链表，在所有在线资源上，我看到类似的做法：

1. 制作一个节点类。 2. 制作一个具有节点对象的链表类。

同样，对于堆栈、队列和树，我也看到了这样的情况。我的问题是，如果我仅通过一个类来实现LinkedList，它看起来像下面这样：

 class LinkList {
     int data;
     LinkList next; }

我仍然能够执行所有的操作。那么包含根或头的第二类是仅为OOP目的还是其他原因？ 我编写了以下代码，它可以正常工作，而无需具有头指针。我在所有方法中使用引用变量，并且主类的对象仍然跟踪头部。

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class LinkList {
    int data;
    LinkList next;

    LinkList(){
        data = 0;
        next = null;
    }

    LinkList(int data) {
        this.data = data;
        next = null;
    }
    LinkList insertAtBegin(int data){
        LinkList newBegin = new LinkList(data);
        newBegin.next = this;
        return newBegin;
    }
    void insertAtPlace(int data, int insertData){
        LinkList newNode = new LinkList(insertData);
        LinkList iterator = this;
        while(iterator!=null && iterator.data!=data){
            iterator = iterator.next;
        }
        if(iterator.data == data)
        {
            newNode.next = iterator.next;
            iterator.next = newNode;
        }
    }
    void insertAtLast(int data) {
        if(next == null){
            next = new LinkList(data);
        }
        else{
            next.insertAtLast(data);
        }
    }

}

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        LinkList linkList = new LinkList(6);
        linkList.insertAtLast(5);
        linkList.insertAtLast(3);
        linkList.insertAtLast(2);
        linkList.insertAtLast(1);

        linkList = linkList.insertAtBegin(10);
        LinkList iterator = linkList;
        while(iterator!=null){
            System.out.print(iterator.data);
            iterator = iterator.next;
        }
        System.out.print("\n");
        linkList.insertAtPlace(5,-1);
        iterator = linkList;
        while(iterator!=null){
            System.out.print(iterator.data);
            iterator = iterator.next;
        }
    }
}

- Sonali Gupta

---

这是用于包含根/头节点的。还有哪里可以放它？ - Sharon Ben Asher

在你的例子中，insertAtPlace和insertAtLast也必须返回列表的头部，否则它将无法适用于所有情况。 - Maurice Perry

Java不是通过对象引用传递来工作的吗？那么它不会自动更新吗？ - Sonali Gupta

这个概念中包含一个根或标题的第二类仅用于面向对象编程(OOP)目的，还是其他用途？仅用于面向对象编程(OOP)目的。 - Gaurav Singh

这取决于数据结构。树节点是一棵树，但链表节点不是一个链表。 - user207421

Answer 1

如果不把链表的头部记录下来，你将无法遍历整个列表或搜索其中的元素。

如果你的LinkList本质上是一个节点（包含数据和指向下一个节点的引用），你必须要在某个单独的类中实现所有链表操作（添加、删除等），并记录链表的头节点。

这会让你回到使用节点类的链表类。

至于你添加的代码，LinkList insertAtBegin(int data)只会在列表的开头插入一个节点，如果你在列表的任何节点上调用它，它实际上会返回一个以新元素开头并以原始列表的子列表结尾的新列表。

- Eran

---

但是没有任何阻止您在列表的任何节点上调用它，这是我在思考时错过的非常重要的一点。 - Gaurav Singh

Answer 2

有几个理由需要使用两个类：

• 区分列表和单个节点的概念，
• 避免每个方法都返回头节点的尴尬情况，
• 避免让类的客户端有责任跟踪头节点，
• 隐藏实现细节，以便更轻松地用等效的类替换该类，
• 等等...

- Maurice Perry

Answer 3

在第一个例子中，您的LinkList类只是一个节点类，因为它保存数据和其后继节点。

拥有LinkedList类的一般目的是为列表提供一个“包装器”，它只是一个保存列表头（在链表的情况下，就是列表本身）以及可能需要的一些功能，例如查找函数或其他任何内容的类。

因此，在您的情况下（第二个例子），它只是一个包装器类，实现了一些额外的功能（insertAtBegin()、insertAtPlace() 和 insertAtLast()）。

- ArchyInUse