理解链表实现的问题-Java 学习之路

更新：非常感谢所有回复的人！这让我觉得我已经足够澄清了关于链接列表和练习应用程序的不足之处 -

首先 - 类定义如何包含自身的对象，好的我知道这是递归，但它对我来说仍然是一个非常奇怪和陌生的概念 .

第二 - 如何将链表对象"link"到另一个节点？

第三 - 如果两个对象被等号分隔，则意味着什么 - 第二个对象消失了，现在指向第一个对象的是什么's left of it is it' "name"，反之亦然？

那么 - 我不会调用构造函数的东西，它给类链接私有链接的对象首先是null的值，即设置它指向什么 . 然后，当创建第一个新节点时，调用方法public void insertFirst，它将对象值赋予其变量，然后发生荒谬的事情 - 首先指向任何内容的对象被分配给新项目，从而使两个对象都指向没有，第一个= newLink;我完全迷失了......

我正在做一个关于算法和数据结构的大学课程，因为教授真的很卑鄙，而且他的解释没用，我试图通过Robert Lafore的一本名为算法和数据结构的书来自学 .

现在我正在学习链接列表，本书中的链表实现有以下代码示例：

Link.java：

class Link
   {
   public int iData;              // data item
   public double dData;           // data item
   public Link next;              // next link in list

   public Link(int id, double dd) { // constructor
      iData = id;                 // initialize data
      dData = dd;                 // ('next' is automatically
      }                           //  set to null)

   public void displayLink() {     // display ourself
      System.out.print("{" + iData + ", " + dData + "} ");
      }
   }

LinkList.java：

class LinkList {
   private Link first;            // ref to first link on list

   public LinkList() {             // constructor
      first = null;               // no links on list yet
      }

   public boolean isEmpty() {      // true if list is empty
      return (first==null);
      }
                                  // insert at start of list
   public void insertFirst(int id, double dd) { // make new link
      Link newLink = new Link(id, dd);
      newLink.next = first;       // newLink --> old first
      first = newLink;            // first --> newLink
      }

   public Link deleteFirst() {     // delete first item
      // (assumes list not empty)
      Link temp = first;          // save reference to link
      first = first.next;         // delete it: first-->old next
      return temp;                // return deleted link
      }

   public void displayList() {
      System.out.print("List (first-->last): ");
      Link current = first;       // start at beginning of list
      while(current != null)      // until end of list,
         {
         current.displayLink();   // print data
         current = current.next;  // move to next link
         }
      System.out.println("");
      }
   }

LinkListApp.java：

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

      theList.insertFirst(22, 2.99);      // insert four items
      theList.insertFirst(44, 4.99);
      theList.insertFirst(66, 6.99);
      theList.insertFirst(88, 8.99);

      theList.displayList();              // display list

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

我只是无法理解在链表类中插入和显示项目的代码 .

创建新对象后，如何 newLink.next = first; and first = newLink; ？

请帮忙！

5 回答

2
每个 Link 都将 .next 引用保存到下一个 Link 元素（除了最后一个元素，具有 .next = null .

LinkList 将引用（ .first ）保存到它包含的第一个 Link 对象 .

为了在 LinkList 的前面插入新的 Link ，我们需要执行以下操作：
- 创建一个新的 Link 对象以插入前面（ newLink ） .
- 让新创建的 Link 指向前一个 Link 对象作为 .next
- 将 LinkList 的 .first 引用重置为 newLink 对象，有效地覆盖先前的引用（在下面用十字标记） .
这是正在发生的事情：
```
public void insertFirst(int id, double dd) {
    Link newLink = new Link(id, dd);
    newLink.next = first;
    first = newLink;
}
```
回复于 2024-05-16T02:01:01+08:00
2

可能让你困惑的是这个列表实现是LIFO（后进先出），所以插入的最后一个元素是遍历时返回的第一个元素 .

newLink.next = first; 将前一个元素作为新元素的下一个（所以第二个）

first = newLink; 将新元素放在列表的顶部

链表有许多可能的行为方式，它取决于您希望它们是什么类型的集合（队列，堆栈）或不同的模式（单链接或双链接，循环）等等 .

回复于 2024-05-16T02:01:01+08:00

假设我们有一个这样的链表：

first                -> Link("monday")
 Link("monday").next  -> Link("tuesday")
 Link("tuesday").next -> Link("wednesday")

现在我们希望以“星期日”开始一周 .

首先，我们为“sunday”创建一个新链接：

Link("sunday")                             # newLink = new Link(id,dd)

告诉它，它的追随者是“星期一”

first                -> Link("monday")
 Link("sunday").next  -> Link("monday")     # newLink.next = first
 Link("monday").next  -> Link("tuesday")
 Link("tuesday").next -> Link("wednesday")

最后我们纠正了本周的开始

first                -> Link("sunday")     # first = newLink
 Link("sunday").next  -> Link("monday")     
 Link("monday").next  -> Link("tuesday")
 Link("tuesday").next -> Link("wednesday")

回复于 2024-05-16T02:01:01+08:00

7

通过设置 head = newLink; 将新的 Link 添加到 LinkList 对象的头部

通过设置 newLink.next = first; 将现有列表追加到新元素的 next

回复于 2024-05-16T02:01:01+08:00
1

当你的新节点被添加时，它被添加到LinkedList的开头，所以由于指针First指向List中的第一个节点，但是当newNode到达同一个列表时，这个指针必须首先必须指向新添加的节点，新添加的节点必须指向先前 Build 的第一个节点，以便它可以成为链接列表的第一个节点 .

希望这个图可以进一步解释：

这就是你必须写 newLink.next = first; and first = newLink; 的原因

回复于 2024-05-16T02:01:01+08:00

理解链表实现的问题

5 回答

相关问题