I have created a singly linked list, and this is how it looks after displaying it:
19-->85-->50-->20-->33-->9-->1-->7-->null
I have created a method that can add a node to a any position of the list.
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;
}
}
I was trying to add a node to the third position.
single.add_node_any(2, 3);
And I realized that:
previous.next = node;
node.next = previous.next;
...is creating a loop. Also I know that due to this loop I can't access the nodes from 50 onwards. So my question is what is happening to those nodes? I have seen statements saying that still these nodes are a part of the list. They are just not accessible.
If that is still a part, how does that happen? I mean, while there is no connection between the repeating node (2) and the 50 (next in the loop), how is that possible to keep the connection with the list?
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();
}
I have seen statements saying that still these nodes are a part of the list. They are just not accessible.
A reference to these statements would be interesting, but it is wrong. The node that was previous.next
before your code assigned something else to that attribute, is no longer part of the list.
how is that possible to keep the connection with the list?
You are absolutely right. The definition of "linked list" includes that nodes are linked in a chain of references, one to the next. If a node is "just not accessible", then it is no longer in that chain, and by definition not part of the list.
So my question is what is happening to those nodes?
If there are no other references to the first node of the disconnected part of the original list, then it becomes available for garbage collection. This will cascade to the next node, ...etc. This makes no difference for the code, which cannot access these nodes, whether they are already garbage collected or not.
The correction is to replace this:
previous.next = node;
node.next = previous.next;
with this:
listNode temp = previous.next;
previous.next = node;
node.next = temp;