2

So I have an array full of nodes called "SNodes" (they are a class of my own creation. They are literally just a basic node that holds a single String and a pointer to the next node).

I have a method called insertValue() that takes in the index you want to put a value in and the String you want the SNode to contain. However, if the index passed already contains an SNode in it, I want the new value to become that SNode's "next" node (essentially creating a linked list of nodes in every index space).

private int insertValue(int arrayPos, String element){//Checks for collisions with another SNode, and inserts the SNode into the appropriate spot in the array
 SNode targetNode = array[arrayPos];//What I want to be a reference to the node at the desired position in the array

 while (targetNode != null){//If an SNode already exists in that position, keeps iterating down until it gets to a non-existant SNode.
  targetNode = targetNode.getNext();//getNext is a method in my SNode that just returns a reference to that SNode's "nextNode" variable.
 }
  targetNode = new SNode(element);
  return arrayPos;
}//end insertValue

My problem is that after I run this method, it does not create a new node in the desired array position, even on the first time running when the array spot is null.

If I change the targetNode = new SNode(element); to array[arrayPos] = new SNode(element); it obviously inserts the SNode into the array just fine, so that leads me to believe that what is happening is the new SNode is being created under the variable targetNode, but that targetNode is not linked to the array position after it is instantiated. I assume it is essentially copying the data from the array position on line 2 into the variable, but then becomes its own separate entity.

So how do I have targetNode actually reference and affect the SNode? (That way way when I iterate down through the linked list of nodes in an already-occupied array space, targetNode is pointing to the correct one.)

NOTE: For the sake of simplicity I have left out the lines that use the setNext() method in SNode to link the previous node in the linked list to its next one.

Improve this question
0

3 Answers 3

Reset to default
1

You have a misconception. Neither variables nor array elements hold objects. They hold references to objects. Furthermore, variables and array positions are not themselves objects, and therefore there is no way in Java to have a reference to one. The closest you can come is to have a copy of the value that your variable or array position contains (a reference to an object).

Thus, this ...

SNode targetNode = array[arrayPos];

... copies the value of array[arrayPos] into variable targetNode. If that value is non-null then the variable afterward refers to the same object that the array element does, but the object itself is not copied. And that's fine and exactly what you want in that case, for when you walk the linked list with

targetNode = targetNode.getNext();

, you don't want to modify array[arrayPos] or any of the nodes' next refernces, for then you would lose elements of your linked list.

But you can't have it both ways. When you ultimately find the position for the new SNode and perform this ...

targetNode = new SNode(element);

... it does not record a reference to the new SNode wherever it was that you most recently copied targetNode's value from. It just puts the reference in targetNode.

What you want to do is find the last current node, if any, and assign to its next reference (or directly to the array element if it is initially null).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Ah-ha! Okay, so the initial time I need an if statement to check if the array index is empty. And if it is I need to directly edit the array index to add the new SNode. But after that I can use targetNode to point at the linked list objects after it, and it will work fine. Thanks, this solved my problem perfectly!
You may also want to initialise the array with dummy SNodes at creation time, so that you don't need to check whether it is the first node all the time. Looking at your other code, that dummy node might actually be a subclass that also has a pointer to the current last element on the list, so that you don't need to walk through the list to find the last one.
1

Here targetNode refers to the object referenced by array[arrayPos].

 SNode targetNode = array[arrayPos];//What I want to be a reference to the node at the desired position in the array

But then when you write :

targetNode = targetNode.getNext();//getNext is a method in my SNode that just

you change the object referenced by the targetNode variable. Now it refers to the next node of it.

Then when you do :

 targetNode = new SNode(element);

You create a new object and assign it to the targetNode variable but finally it is never associated to an existing node.

It doesn't assign to the next node a new node.
To do it you could write :

targetNode.setNext(new SNode(element));
Improve this answer

5 Comments

Yes, but even when the array spot is empty during the first time this program runs (so it skips the while loop because targetNode == null) it doesn't place a new node there. But thank you for pointing that out that that could be confusing, I will edit the question.
You are welcome. It doesn't work for the same reason that I have explained : targetNode = new SNode(element); creates a new object and assigns it to the targetNode variable . But it means that the targetNode variable doesn't reference any longer array[arrayPos]. So it has no effect on array[arrayPos].
Yes, that's exactly my problem. So how do I have targetNode reference array[arrayPos]?
Create the element and add it in the array : array[arrayPos] = new SNode(element) then store it in a variable : targetNode = array[arrayPos]
Okay, that works for the first iteration. But then if later there is another item attempted to be added to that index how do I know how many times to use the .getNext() method on array[arrayPos]? Because for all the program knows, there might be one or two or ten nodes in a linked list after the first one.
1

As the other answers show, with the normal solution to this, you would test whether it is the first element in the array, and do something different in that case. That is, set the element directly in the array if it is the first one, walk the list if it is not.

A valid alternative approach would be to use a dummy element in the array, that is only used for its next field, and initialise the array with dummy elements at creation time. In your case, you could even give the dummy element an additional last field, which would negate the need to walk the list to find the last element. Something like the following:

interface SNodeRef {
    SNode getNext();
    void setNext(SNode node);
}

class FirstNode implements SNodeRef {
    SNodeRef getLast();
    void setLast(SNodeRef);
    ....
    FirstNode() { setLast(this); }
}

class SNode implements SNodeRef { ... }

private int insertValue(int arrayPos, String element) {
    SNode newNode = new SNode(element);
    FirstNodeRef ref = array[arrayPos];
    ref.getLast().setNext(newNode);
    ref.setLast(newNode);
}

FirstNode[] array = new FirstNode[10];
for (int i = 0; i < array.length; i++) {
    array[i] = new FirstNode();
}

Alternatively, as it is a linked list that you are using, you could simply use the predefined LinkedList data structure:

private int insertValue(int arrayPos, String element) {
    array[arrayPos].addLast(element);
}

var array = new LinkedList<String>[10];
for (int i = 0; i < array.length; i++) {
    array[i] = new LinkedList<String>();
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.