时间戳

首页 > 解决方案 > 为什么要有链表的父类

java - 为什么要有链表的父类

问题描述

这是一个普遍的问题，可能是关于 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;
        }
    }
}

标签： javadata-structureslinked-list

解决方案

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

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

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

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

推荐阅读