在 Java 中实现循环 Link 列表

Question

我正在尝试根据以下内容创建循环 Link 列表：对列表的唯一访问是单个引用，current，它可以指向列表中的任何 link 并且可以根据需要在列表中移动。该列表应处理插入、搜索和删除：这些操作发生在 current 指向的 link 下游一个 link 处。能够显示列表。

1) class循环linked列表的数据成员应该包括参考电流和一个变量来跟踪循环列表中links的大小。

2) class通告中需要定义的方法包括：

• 插入：在当前 link 之后插入 • 删除：删除一个超出当前的 • 查找：使用给定键查找 link • deleteKey：用给定的键删除 link • displayList：显示列表（列表中的所有link） • 步骤：将当前移动到下一个 link • peek: return 当前存储的数据 • isEmpty: 检查列表是否为空

这是我当前的代码（现在它是线性的——还没有变成循环的）：

public class CircularList<T> {
private Link current;            // ref to the current link in the list
private int nLinks;             //Reference to number of links in the list 

//--------------------------------------------------------------
public CircularList()          // constructor
{
    current = null;
    nLinks = 0;

}   //End constructor method - CircularList()

// -------------------------------------------------------------
public void insert(long dd)
{   
    Link newLink = new Link(dd);    // make new link
    if (nLinks == 0) 
    {
        current = newLink;
        nLinks++;
    }

    if(nLinks != 0) 
    {         
        current.next = newLink;            // current --> newLink
        newLink = current; 
        nLinks++;
    }
}   //End insert()
// --------------------------------------------------------------
public Link delete()      // delete link after current
{              
    Link temp = null;
    if(nLinks == 0)     //first check whether the list is empty
        return null;
    if(nLinks != 0)
    {
        temp = current.next;            // save reference to link
        current = current.next;             // delete it: current-->one after current
        nLinks--;

    }
    return temp;                        // return deleted link
}   //End delete()


// -------------------------------------------------------------
public void displayList()
{
    System.out.print("List: ");
    int tempLinks = nLinks;
    while(tempLinks > 0)      // until end of list
    {
        current.displayLink();      // print data
        tempLinks--;                    // decrement nLinks
        current = current.next;     // move to next link
    }
    System.out.println("");
}   //End displayList()
// -------------------------------------------------------------
public boolean isEmpty()       // true if list is empty
    {
    return (current==null);
}   //End isEmpty() 
// -------------------------------------------------------------
public void step() //Move current to next Link
{
    current = current.next;
}   //End step()
}   //End CircularList Class

运行时出现空指针异常。（我认为当我尝试调用显示方法时我的插入方法有问题导致此问题）我很确定它没有正确插入所有 4 link。当我尝试显示它时，它只显示数据 2 和 8，这是插入的第一项和最后一项。

我的linkclass:

public class Link {

   public long dData;                 // data item
   public Link next;                  // next link in list

// -------------------------------------------------------------
   public Link(long d)                // constructor
   {
       dData = d;
       next = null;
   }
// -------------------------------------------------------------
   public void displayLink()          // display this link
   { 
       System.out.print(dData + " "); 
   }
// -------------------------------------------------------------

}   //End Link Class

我的应用class:

public class CircularLinkListApp {
public static void main(String[] args) {
    CircularList theList = new CircularList();  // make new list

    theList.insert(2);      // insert four items
    theList.insert(4);
    theList.insert(6);
    theList.insert(8);

    theList.displayList();              // display list

  while( !theList.isEmpty() )         // until it's empty,
  {
     Link aLink = theList.delete();   // delete link
     System.out.print("Deleted ");         // display it
     aLink.displayLink();
     System.out.println("");
  }
  theList.displayList();              // display list

} // end of main()
}   //End CircularLinkListApp class

Answer 1

看来您面临的所有问题都是因为您没有花时间思考您的代码必须在纸上做什么。我向您保证，如果您开始在纸上绘制您的列表，用 link 的大小写和表示 .next 属性的箭头，它会突然变得更加明显，您需要编码什么行为

1。插入问题

您将面临的第一个也是最明显的问题是您的插入方法。

案例编号 link 已经

这个很好，即使你可以再添加一行使其已经循环，它会更好。

列表中已有 link 个案例

这就是问题开始的地方。练习要求你在当前的后面添加 link。它以 current.next = newLink; 开头，但下一行 newLink = current; 对您没有任何作用，因为它只是将 current 的值分配给 newLink.

要考虑的第二个问题是您从不检查当前是否还没有下一个 link。如果是这样，那么您的代码将有效地分离 link 到 current link 的所有链接。找到一个解决方案来验证 next 是否已经设置，如果是，您需要找到一种方法在两个现有的 link 之间插入新的 link。

圆度

我觉得它是圆形这一事实让你感到害怕。真的不应该。即使只有一件物品，您也可以循环使用。在这种情况下 current.next 将与 current 相同，仅此而已。你已经有了一个变量来知道你有多少元素，所以只依赖它来知道该怎么做。事实上，一旦它被正确编码，你将永远不会有一个等于 null 的 .next。唯一的例外是当列表为空时 current 将等于 null（即使你也可以避免这种情况，但没有必要）

2。显示列表问题

这是您需要循环列表的地方。您的想法是正确的，但是由于您没有循环列表，最终 current.next 之一将指向 null，因此您的原始问题。如果你修复你的循环并插入显示将至少在插入后的第一个工作

3。删除问题

作业是删除列表中的下一项。您可以从将要删除的元素存储在临时变量中开始，但您遗漏了一些要点：

current = current.next; 表示您正在失去实际电流。这不是你想要做的。首先你的“光标”不应该移动。其次 current.next 此时是您要从列表中删除的项目。
为了切掉一个 link，你需要多考虑一下你需要做的所有事情。您需要分离对要删除的项目的 current.next 引用，并将其附加到出现在您要删除的项目之后的项目。

希望我已经说清楚了。有很多我不会提及的小怪癖，主要是因为它们不影响功能，它们只是一段代码，可以以更好、更清晰的方式重写。

在 Java 中实现循环 Link 列表

Implementing a Circular Link List in Java

java

list

hyperlink

circular-list

1。插入问题

案例编号 link 已经

列表中已有 link 个案例

圆度

2。显示列表问题

3。删除问题