Linked Lists newbie question

[Taria]

Hello all,

I'm still pretty new to java and I'm having trouble understanding how
to reference a node.

I've written 2 classes, a node class with mutator and accessor methods
and a linked list class. I need to write a method within the linked
list class that will insert a new object into the linked list.

This is where I'm stuck. The stuff below won't compile ....I
understand the logic that I need to do but I'm having understanding
how to reference a node, the compiler is complaining the variable curr
is private in the Node class (but the professor wants us to declare
all variables private for more robust code so I have to do that).

I'm totally confused. I'm stuck as to how to go about solving this
problem or what to do to understand this concept a bit
better....anyone out there have ideas?

ANY help is appreciated,
Marion

public class LinkedList{
/**
* Construct the list
*/
private Node head;
private int length;

public LinkedList() {
this.head = null;
this.length = 0;
}

/**
* Test if the list is empty
* @return true if empty
*/
public boolean isEmpty(){
return head == null;
}

/**
* Get the data at position specified
* @param position is the location queried
* @return data at the position specified in the list
*/
public Object getItemAtPosition(int position) {
if (position<0 || position >= this.length){
return null;
}
Node curr = this.head;
for (int i=0;i<position;i++){
curr = curr.getNext();
}
return curr.getData();
}

public boolean insert (Object data,int position){
if (position<0 || position > this.length ){
return false;
}
// this part I'm confused at too...I don't know what data to
assign
// the getItemAtPosition(position) to, but what I want to do is
advance
// the node pointer to the parameter position that is passed to
this method.
getItemAtPosition(position);

// create the new node
Node temp = new Node(data);
// make the new node's next field to the current next field
temp.next = curr.next;
// make current next field point to the new node
curr.next = temp.next;
return true;
}

}

Then my node class is:
public class Node {
private Object data;
private Node next;

public Node(Object data){
this.data = null;
}
public Node(Object data,Node next){
this.data = data;
this.next = next;
}
public void setNext(Node next){
this.next = next;
}
public void setData(Object data){
this.data = data;
}
public Node getNext(){
return this.next;
}
public Object getData(){
return this.data;

}
}

 

[Chris Uppal]

public Object getItemAtPosition(int position) {
if (position<0 || position >= this.length){
return null;
}
Node curr = this.head;
for (int i=0;i<position;i++){
curr = curr.getNext();
}
return curr.getData();
}

If that code is correct (it looks OK to me) then you also understand how to
find the /Node/ at a given position. Exactly the same code as above, but you
return the Node instead of the data it contains.

But I think you may have confused yourself by calling the variable "curr"
(presumably short for "current"). That variable is local to the method, and
when the method returns the variable vanishes. So calling getItemAtPosition()
doesn't "advance" anything -- it just finds the data in the list and returns
it.

public boolean insert (Object data,int position){
if (position<0 || position > this.length ){
return false;
}
// this part I'm confused at too...I don't know what data to
assign
// the getItemAtPosition(position) to, but what I want to do is
advance
// the node pointer to the parameter position that is passed to
this method.
getItemAtPosition(position);

If you write another method like getItemAtPosition(), but which returns the
Node instead of the data it contains, then you could use that here. Say you
call it getNodeAtPosition(). You call that, and it returns a reference to the
Node you want. Since you want to do something to that node, you'll have to
assign the reference to a local variable; something like:

Node previous = this.getNodeAtPosition(position);

Now you can add your new node after it. You won't be able to use temp.next and
previous.next fields directly, but you can use your getNext() and setNext()
methods to do just the same thing.

Node temp = new Node(data);
temp.setNext(previous.getNext());
previous.setNext(temp);

Actually my code is wrong -- it will always insert the item /after/ the
numbered position. E.g. if you asked to insert an item at position 0, it would
put it after the existing item at that position (so it would end up at position
1). You'll have to make small changes to fix that up, but it's not related to
your problem here, and anyway I think you can do that easily (but expect to
have to handle position 0 specially).


Oh, by the way:

public Node(Object data){
this.data = null;
}

You have a typo there -- you should be assigning
this.data = data;

-- chris

 

[Taria]

If that code is correct (it looks OK to me) then you also understand how to
find the /Node/ at a given position. Exactly the same code as above, but you
return the Node instead of the data it contains.

But I think you may have confused yourself by calling the variable "curr"
(presumably short for "current"). That variable is local to the method, and
when the method returns the variable vanishes. So calling getItemAtPosition()
doesn't "advance" anything -- it just finds the data in the list and returns
it.


If you write another method like getItemAtPosition(), but which returns the
Node instead of the data it contains, then you could use that here. Say you
call it getNodeAtPosition(). You call that, and it returns a reference to the
Node you want. Since you want to do something to that node, you'll have to
assign the reference to a local variable; something like:

Node previous = this.getNodeAtPosition(position);

Now you can add your new node after it. You won't be able to use temp.next and
previous.next fields directly, but you can use your getNext() and setNext()
methods to do just the same thing.

Node temp = new Node(data);
temp.setNext(previous.getNext());
previous.setNext(temp);

Actually my code is wrong -- it will always insert the item /after/ the
numbered position. E.g. if you asked to insert an item at position 0, it would
put it after the existing item at that position (so it would end up at position
1). You'll have to make small changes to fix that up, but it's not related to
your problem here, and anyway I think you can do that easily (but expect to
have to handle position 0 specially).

Oh, by the way:


You have a typo there -- you should be assigning
this.data = data;

-- chris

Great! Thank you Chris, I'm stuck in school for a long time today and
can't work on this code for another 7 hours but I'll be trying it
again after that. Thank you very much for your help.