为什么链表要有父类

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;

        }

    }

}

Answer 1

您必须在某处跟踪链表的头部。否则，您将如何遍历整个列表，或在列表中搜索元素？如果您LinkList本质上是一个节点（具有数据和对下一个节点的引用），则必须在某个单独的类中实现所有链表操作（添加、删除等...），以跟踪节点的头节点列表。这会将您带回到使用节点类的链表类。至于您添加的代码，LinkList insertAtBegin(int data)如果您在列表的第一个节点上调用它，只会在列表的开头插入一个节点。但是没有什么可以阻止您在列表的任何节点上调用它，在这种情况下，它实际上会返回一个以新元素开头并以原始列表的子列表结尾的新列表。

Answer 2

有两个班级有几个原因：区分列表和单个节点的概念，为了避免从每个方法中笨拙地返回头节点，为了避免让类的客户端有责任跟踪头节点，隐藏实现细节，以便可以更轻松地用等效类替换该类，ETC...

Answer 3

在第一个示例中，您的 LinkList 类只是一个节点类，因为它包含数据和它后面的节点拥有 LinkedList 类的一般目的是为列表提供一个“包装器”，它只是一个包含列表头部的类（在链表的情况下，它是列表）和一些功能，例如查找功能或您需要的任何其他功能。所以在你的情况下（第二个例子）它只是一个实现一些额外功能的包装类（insertAtBegin()，insertAtPlace()和insertAtLast()）