Я создал односвязный список, и вот как он выглядит после отображения:
19-->85-->50-->20-->33-->9-->1-->7-->null
Я создал метод, который может добавить узел в любую позицию списка.
public void add_node_any(int value , int position) {
ListNode node = new ListNode(value);
if (position == 1) {
node.next = head;
head = node;
}
else {
ListNode previous = head;
int count = 1;
while (count < position - 1) {
previous = previous.next;
count++;
}
previous.next = node;
node.next = previous.next;
}
}
Я пытался добавить узел в третью позицию.
single.add_node_any(2, 3);
И я понял, что:
previous.next = node;
node.next = previous.next;
... создает цикл. Также я знаю, что из-за этого цикла я не могу получить доступ к узлам начиная с 50. Итак, мой вопрос: что происходит с этими узлами? Я видел заявления о том, что эти узлы все еще являются частью списка. Они просто недоступны.
Если это все еще часть, то как это происходит? Я имею в виду, что пока нет связи между повторяющимся узлом (2) и 50 (следующим в цикле), как можно сохранить связь со списком?
class SLL_implementation_Test_09_04 {
private listNode head;
private static class listNode {
private int data;
private listNode next;
public listNode(int data) {
this.data = data;
this.next = null;
}
}
//Display the linked list
public void Display() {
listNode current = head;
while (current != null) {
System.out.print(current.data + "-->");
current = current.next;
}
System.out.print("null");
}
//Display the length of the linked list
public int SLL_length() {
int count = 0;
listNode current = head;
while (current != null) {
count++;
current =current.next;
}
return count;
}
//Add new nodes | create a linked list from the beginning
public void add_node_first(int value) {
listNode newnode = new listNode(value);
newnode.next = head;
head = newnode;
}
//Add new nodes to the end of the linked list
public void add_node_last(int value) {
listNode newnode = new listNode(value);
if (head == null) {
head = newnode;
return;
}
listNode current = head;
while(current.next != null) {
current = current.next;
}
current.next = newnode;
}
//Add a new node to a given possition
public void add_node_any(int value, int position) {
listNode node = new listNode(value);
if (position == 1) {
node.next = head;
head = node;
}
else {
listNode previous = head;
int count = 1;
while (count < position-1) {
previous = previous.next;
count++;
}
previous.next = node;
node.next = previous.next;
}
}
}
public static void main(String args[]) {
SLL_implementation_Test_09_04 single = new SLL_implementation_Test_09_04();
single.add_node_last(20);
single.add_node_first(50);
single.add_node_first(85);
single.add_node_first(19);
single.add_node_last(33);
single.add_node_last(9);
single.add_node_last(1);
single.add_node_last(7);
single.add_node_any(2, 9);
single.Display();
}
Что заставляет вас думать, что это создает цикл (цикл)?
@LouisWasserman node.next = previous.next;
то же самое, что node.next = node
@ElliottFrisch tail->next = head
в списке с одной ссылкой не цикл?
Ребята, мне очень жаль, если вы почувствовали, что я упускаю суть проблемы. Я упомянул слово «цикл», потому что добавленный узел продолжает повторяться. в этом случае... если я показываю список, он показывает 19-->85-->2-->2-->2-- >2-->2.....-->2... это продолжается. И если это не цикл, мы должны иметь доступ к 50-->20-->33-->9-->1-->7-->null. тоже да? Но это невозможно.
«Я не хочу тратить ваше время, показывая весь код». Вам нужно показать достаточно кода, чтобы он был работоспособен и иллюстрировал ваш вопрос. Показ слишком малого количества кода отнимает наше время, поскольку нам приходится догадываться, является ли то, что вы опубликовали, тем, что вы на самом деле используете, как оно вызывается и так далее.
@tgdavies Сэр, я добавил полный код.
Узлы за пределами вашего цикла вы отделили от списка, поэтому они больше не являются частью списка. Предполагая, что у вас нет других ссылок ни на один из них, вы правы, вы не можете получить к ним доступ каким-либо образом. Это также означает, что они «имеют право на сбор мусора». Означает ли это, что сборщик мусора их очистит, мы не можем знать. Если ваша программа представляет собой небольшое или среднее задание, я считаю маловероятным, что сборщик мусора когда-либо заработает до завершения вашей программы. В большой серверной программе, работающей в течение многих дней, она, скорее всего, будет собирать мусор на узлах.
Я видел заявления о том, что эти узлы все еще являются частью списка. Они просто недоступны.
Ссылка на эти утверждения была бы интересна, но она неверна. Узел, который был previous.next
до того, как ваш код присвоил этому атрибуту что-то еще, больше не является частью списка.
как это возможно сохранить связь со списком?
Вы абсолютно правы. Определение «связанного списка» включает в себя то, что узлы связаны в цепочку ссылок один к другому. Если узел «просто недоступен», то он больше не находится в этой цепочке и по определению не является частью списка.
Итак, мой вопрос: что происходит с этими узлами?
Если других ссылок на первый узел отключенной части исходного списка нет, то он становится доступен для сборки мусора. Это будет каскадно передано следующему узлу и т. д. Это не имеет значения для кода, который не может получить доступ к этим узлам, независимо от того, собраны ли они сборщиком мусора или нет.
Исправление заключается в замене этого:
previous.next = node;
node.next = previous.next;
с этим:
listNode temp = previous.next;
previous.next = node;
node.next = temp;
Что вы подразумеваете под
what is happening to those nodes
? Они будут уничтожены при следующем запуске сборщика мусора, поскольку они больше не доступны.