Динамическая реализация связанного списка

Question

class Nodetype
{
  int info;
  Nodetype next;

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

В моем учебнике есть этот код для динамического создания связанного списка. Вопрос в том, что когда программы выполняются построчно, переменная 'info' определяется как тип 'int', а переменная 'next' - как Nodetype.

Что на самом деле здесь происходит?

означает ли это, что переменная 'next' будет содержать -

1. Конструктор 'Nodetype'
2. int info
3. Тип узла "следующий", где "следующий" снова будет иметь все 1,2,3, а затем 3 снова будет иметь 1,2,3 ... и так далее ... до бесконечности?

Я действительно раздражен, потому что не могу понять, как это работает, может кто-нибудь легко объяснить это?

Answer 1

Ваш код очень хорошо соответствует определению списка: список 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

Это работает так, что список состоит из отдельных элементов, каждый из которых имеет только указатель на тот, который идет после него:

Nodetype next;

Информация, которую фактически содержит каждый элемент в списке, такова:

int info;

Вы можете думать о списке как о «цепочке»: на самом деле это не отдельный объект, а составной объект из нескольких ссылок. Из каждой ссылки вы можете видеть только следующую ссылку (или, в случае связанных списков, которые имеют ссылки в обоих направлениях: следующая и предыдущая ссылка), поэтому для того, чтобы все элементы были доступны, вам нужно будет сохранить ссылку к первому элементу в «цепочке».

Примечание: List объекты - это отдельные объекты, которые имеют ссылку на первую ссылку "цепочки".

Answer 3

Nodetype - это ваш класс, который определяет данные, которые будет содержать экземпляр узла, а также ссылку на следующий узел в связанном списке. Эта ссылка на следующий узел будет объектом типа Nodetype. Здесь нет ничего сложного, это классическая реализация связанного списка.

Возможно, вы захотите проверить этот отличный список связанных ресурсов e из Стэнфорда.

Answer 4

Он будет содержать значение Null, поскольку переменная не инициализирована ни для какого значения.

Answer 5

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 6

Вы создали класс NodeType, и внутри класса вы определили объект этого класса.Таким образом, этот объект (в вашем примере next) будет иметь int info переменную NodeType next объект и конструктор.

Answer 7

поле next является ссылкой на объект типа Nodetype. сначала он ни к чему не приведет - поскольку он создается null. когда вы присваиваете ему значение, оно будет указывать только на это значение, ничто не будет продолжаться бесконечно, если вы не создадите цикл в списке.

Answer 8

Сначала переменная next не указывает ни на какой объект (она указывает на null). Через некоторое время вы будете указывать на другой узел с next = new NodeType(number). Идея состоит в том, что вы используете композицию - у вас есть один экземпляр класса, который имеет ссылку на другой экземпляр. Это как nodeA указывает на nodeB, nodeB указывает на nodeC. Здесь у вас есть три экземпляра, и первый экземпляр имеет ссылку на второй экземпляр, а второй экземпляр имеет ссылку на третий экземпляр. Третий экземпляр - это last one, а его следующий экземпляр указывает на null.