为什么要有链表的父类

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

Answer 1

您必须在某处跟踪链表的头部。否则，您将如何迭代整个列表或搜索列表中的元素？

如果您LinkList本质上是一个节点（具有数据和对下一个节点的引用），则必须在某个单独的类中实现所有链表操作（添加、删除等...），该类跟踪该节点的头节点列表。

这将带您回到使用节点类的链表类。

至于您添加的代码，LinkList insertAtBegin(int data)如果您在列表的第一个节点上调用它，则只会在列表的开头插入一个节点。但是没有什么可以阻止您在列表的任何节点上调用它，在这种情况下，它实际上会返回一个以新元素开头并以原始列表的子列表结尾的新列表。