链表的动态实现

Question

class Nodetype
{
  int info;
  Nodetype next;
  Nodetype(int i)
  {
     info=i;
     next=null;
  }
}

我的教科书有这个代码来动态创建链表。问题是，当程序逐行执行时，它将变量"info"定义为类型"int"，然后将变量"next"定义为Nodetype。

这里到底发生了什么？

这是否意味着变量"next"将包含 -

1. 构造函数"节点类型">
2. 国际信息
节点类型"next"，其中"next"将再次拥有所有1,2,3，
3. 然后3将再次具有1,2,3...依此类推。直到无穷大？

我真的很生气，因为我无法理解它是如何工作的，有人可以轻松解释这一点吗？

Answer 1

你的代码很好地遵循了list的定义：一个列表是null的，或者一个元素后跟一个列表。
在您的情况下，"元素"由int值定义，"后跟"部分是next变量;在 Java 中变量(当它们不是文字时，就像int值一样(实际上是指针，所以虽然它们没有初始化，但它们不存储任何有效值，也不指向任何内存区域(即它们的值是null(，所以虽然next变量保持原样，但你的元素后面没有任何其他元素。要动态地将元素添加到列表中，您需要一个指向您添加的最后一个元素的指针，否则您将无法再次找到它们：

int i = 0;
Nodetype head = new Nodetype(i++);
Nodetype last = new Nodetype(i++);
head.next = last;
while (i<5) {
    Nodetype temp = new Nodetype(i++);
    last.next = temp;
    last = temp;
}
while(head) {
    System.out.println(head.info);
    head = head.next;
}

请注意，在最后几行中，您丢失了head指针，并且无法返回列表的起点。使用列表时请记住这一点;)

Answer 2

起初变量next不指向任何对象(它指向null(。在某些时候，您将使其指向另一个具有next = new NodeType(number)的节点。这个想法是你使用组合 - 你有一个类的实例，它引用了另一个实例。这就像nodeA指向nodeB，nodeB指向nodeC。这里有三个实例，第一个实例引用了第二个实例，第二个实例引用了第三个实例。第三个实例是最后一个实例，它的下一个实例指向 null 。

Answer 3

字段next是对类型为 Nodetype 的对象的引用。 起初它不会指向任何内容 - 因为它被实例化为null . 当您为其赋值时，它将仅指向该值，除非您在列表中创建循环，否则不会无限继续。

Answer 4

您创建了类NodeType，并在类内部定义了该类的对象。因此，该对象(在您的示例中next(将具有int info变量NodeType next对象和构造函数。

Answer 5

它将包含 Null，因为变量未初始化为任何值。

Answer 6

Nodetype是定义节点实例将包含的数据以及对链表中下一个节点的引用的类。对下一个节点的引用将是类型 Nodetype 的对象。这里没有什么太难的，这是链表的经典实现。

你可能想看看斯坦福大学的这个很棒的链表资源。

Answer 7

其工作方式是列表由单个元素组成，每个元素只有一个指向其后面的指针：

Nodetype next;

列表中的每个元素实际包含的信息如下：

int info;

你可以把列表想象成一个"链"：它实际上不是一个单一的对象，而是一个由多个链接组成的复合对象。从每个链接中，您只能看到下一个链接(或者，对于双向引用的链表：下一个和上一个链接(，因此为了使所有元素都可用，您必须保留对"链"中第一个元素的引用。

注意：List对象是引用"链"的第一个链接的单个对象。

Answer 8

next是对另一个Nodetype实例的引用。如果next == null则表示当前元素是列表中的最后一个元素。

让我们看一个例子：

Nodetype node = new Nodetype(0);        // i = 0, next = null
Nodetype anotherNode = new Nodetype(1); // i = 1, next = null
node.next = anotherNode;                // now the first node has a ref to the second

Answer 9

#include<stdio.h>
#include<stdlib.h>
void print_list(int *arr,int *size,int *capacity)
{
     printf("capacity = %d; size = %d; elements = ",*capacity,*size);
     for(int i=0;i<(*size);i++){
        printf("%d ",arr[i]);
    }
     printf("n");
}
int * push_back(int *arr,int data,int *size,int *capacity)
{
    int *b;
    if(*size == *capacity){
        *capacity = 2*(*capacity);
        b = (int *)malloc(sizeof(int)*(*capacity));
        for(int i=0;i<(*size);i++){
        b[i]= arr[i];
        }
        b[*size]=data;
        *size=*size+1;
        print_list(b,size,capacity);
        return b;
    }
     arr[*size]=data;
     *size=*size+1;
     print_list(arr,size,capacity);
     return arr;
}
int main()
{
     int size=0;
     int n;
     int x;
     int *arr;
     arr = (int *) malloc(sizeof(int));
     int capacity=1;
     scanf("%d",&n);
     for(int i=0;i<n;i++){
        scanf("%d",&x);
        arr=push_back(arr,x,&size,&capacity);
     }
}

它的工作。