理解链表实现的问题 [英] Problems with understanding a linked list implementation

问题描述

更新：非常感谢所有回复的人！这让我觉得我在学习Java方面并没有完全孤立。请原谅，但我想我没有足够的澄清我不了解链接列表和运动应用程序 -

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

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

第三 - 如果两个对象由等于符号，这意味着第二个对象消失，剩下的是现在指向第一个对象的名称，反之亦然？

然后 - 我下面引用的程序我不知道的事情如下：在linkList类被实例化之后，它的构造函数被调用，它给出了Link private Link的对象首先是null值，即将其指向无效。然后，当创建第一个新节点时，方法public void insertFirst被调用，它将对象值赋予其变量，然后发生荒谬的事情 - 首先指向无关的对象被分配给新项目，从而使两个对象指向没有和第一个= newLink;我完全失去了...

我正在做一个关于算法和数据结构的大学课程，由于教授真的是意思，他的解释是没有用，我试图从Robert Lafore的一本叫做算法和数据结构的书中自己学习。

现在我正在学习链接列表，并且有一个链接列表实现的代码示例如下：

Link.java：

  class Link 
 {
 public int iData; // data item 
 public double dData; //数据项
 public Link next; //列表中的下一个链接
 
 public Link（int id，double dd）{// constructor 
 iData = id; //初始化数据
 dData = dd; //（'next'自动
} //设置为null）
 
 public void displayLink（）{//显示我们自己
 System.out.print（{ + iData +，+ dData +}）; 
} 
} 
  

LinkList.java：

  class LinkList {
 private Link first; // ref to first link on list 
 
 public LinkList（）{// constructor 
 first = null; //没有列表上的链接
} 
 
 public boolean isEmpty（）{//如果列表为空，则为true 
 return（first == null）; 
} 
 //在列表开头插入
 public void insertFirst（int id，double dd）{// make new link 
链接newLink = new Link（id，dd） ; 
 newLink.next = first; // newLink  - >旧的第一个
 first = newLink; // first  - > newLink 
} 
 
 public Link deleteFirst（）{//删除第一项
 //（假设列表不为空）
链接temp = first; //保存引用链接
 first = first.next; //删除它：first  - > old next 
 return temp; // return deleted link 
} 
 
 public void displayList（）{
 System.out.print（List（first  - > last）：）; 
 Link current = first; //从列表开始
 while（current！= null）//直到列表结尾，
 {
 current.displayLink（）; //打印数据
 current = current.next; //移动到下一个链接
} 
 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）; //插入四个项目
 theList.insertFirst（44，4.99）; 
 theList.insertFirst（66，6.99）; 
 theList.insertFirst（88,8.99）; 
 
 theList.displayList（）; //显示列表
 
 while（！theList.isEmpty（））{//直到它为空，
链接aLink = theList.deleteFirst（）; //删除链接
 System.out.print（Deleted）; //显示它
 aLink.displayLink（）; 
 System.out.println（）; 
} 
 theList.displayList（）; //显示列表
} 
} 
  

我只是不明白代码插入并显示链表中的项目。

如何才能 newLink.next = first;创建新对象后，首先= newLink;

请帮助！

解决方案

每个链接持有 .next 到下一个链接元素（除了最后一个元素，具有 .next = null 。

A LinkList 将第一个链接保存参考（ .first ） code>它包含的对象。





为了在<... code>链接 code> LinkList ，我们需要执行以下操作：

1. 创建一个新的链接对象插入前面（ newLink ）。


2. 让新创建的链接指向前一个链接对象作为其 .next


3. 将 LinkList 的 .first 引用重定向到 newLink 对象，有效地覆盖以前的引用（用cross b标记）



这是非常正确的：

  public void insertFirst（int id，double dd）{
链接newLink = new Link（id，dd）; 
 newLink.next = first; 
 first = newLink; 
} 
  

Update: Thanks a lot to everybody who responded!!! It made me feel that I'm not completely alone in my efforts to learn Java. Please excuse me, but I guess I didn't clarify enough what I don't get about linked lists and the exercise application -

first - how can a class definition contain an object if itself, OK I know that this is recursion but it's still a very strange and alien concept to me.

second - how can exactly a linked list object "link" to another node?

third - if two objects are separated by an equals sign it means what - that the second object disappears and what's left of it is it's "name" that now points to the first object or vice versa?

then - the thing that I don't get about the program I quoted below is the following: after the linkList class is instantiated it's constructor is called and it gives the object of class Link private Link first the value of null, i.e. sets it pointing to nothing. Then, when the first new node is created the method public void insertFirst is called, it gives the object values to its variables and then something absurd happens - the object first that points to nothing is assigned to the new item thus making both objects pointing to nothing and with the first = newLink; I'm completely lost...

I'm doing a college course on Algorithms and Data structures and since the professor is really mean and his explanations are useless I'm trying to learn on my own from a book called Algorithms and data structures by Robert Lafore.

Now I'm learning Linked lists and there is the following code example for a linked list implementation in the book:

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

I just CANNOT understand the code that inserts and displays items in the linked list class.

How can it be that newLink.next = first; and first = newLink; after the new object is created?

Please help!

解决方案

Each Link holds a reference .next to the next Link element (except the last element, having .next = null.

A LinkList holds a reference (.first) to the first Link object it contains.

In order to insert a new Link at the front of the LinkList, we need to do the following:

1. Create a new Link object to insert in front (newLink).
2. Let the newly created Link point to the previous first Link object as its .next
3. Reset the .first reference of the LinkList to the newLinkobject, effectively overwriting the previous reference (marked with a cross below).

This is exacly what's going on:

public void insertFirst(int id, double dd) {
    Link newLink = new Link(id, dd);
    newLink.next = first;
    first = newLink;
}

这篇关于理解链表实现的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！