LinkedList下一个的概念

Question

我正在学习数据结构（链接列表） 为链接类创建的引用如下一个，首先分别存储下一个链接和第一个链接？在实现类中，我们只是创建引用而不是定义任何东西？ first.next如何移动？如何创建一个引用作为第一个引用列表中的第一个元素？

class Link 
{ 
public int iData; // data item (key) 
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 + "} "); 
} 
} 
class LinkList 
{ 
private Link first; // ref to first link on list 
public LinkList() // constructor 
{ 
first = null; // no items 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(""); 
} 
} 

Answer 1

在一个链表，各元件具有保持到下一个元素的参考的字段，并且在另外有保持在列表中的第一个元素的引用的变量 - 列表的“头” 。 这样，当使用Link newLink = new Link(id, dd);构造一个新的Link元素时，它的next字段被分配了对当前第一个元素的引用，这使得它成为新的第一个元素。 然后，在您的代码中名为first的列表“头”被分配了对新创建的元素的引用。

Answer 2

我认为可能会让您困惑的部分是该班级名为Link，而Node将是一个更好的名字。本质上，你的LinkList类将一堆节点链接在一起。

您创建的第一个节点包含两件事：一些数据和一个参考（这是将节点链接在一起）到下一个Node。存储在next中的引用初始设置为您制作的每个节点均为空。每当您拨打insertFirst(int id, double dd)方法时，您的LinkList类正在更新此值。它使用一些数据创建一个新的Node，并使用对第一个位置的节点的引用更新此节点的next属性。想象一下，你正在创建一个数字链表，并且你在第一个数字中插入'10'。这份名单将是这样的：

'10'

然后调用insertFirst('9')，它看起来就像这样：'9' ----> '10'，所以第一个节点包含数据的9号，其next被设置为“10”由此行：newLink.next = first; // newLink --> old first。包含9的节点将其next属性设置为包含10的节点，然后将first设置为刚创建的新节点，即包含9的节点。随着您继续添加节点，此过程重复进行，因此它将最终看起来像1 ----> 2 ----> 3 ----> ... ----> 8 ----> 9 ----> 10，因此每个Node都有一个对列表中下一个节点的引用。