[eikkaj]

I know this would be a lot easier in a doubly linked list but I have to do this in a singly linked. Looking for some advice.
I want to Walk through the list until reaching the the next pointing to the node we want to get the previous node from.

This is what I have so far.. I think I'm on the right track, but right now, the output is funky. It's printing the index up to the "previous" node and then printing the data in those indices.
I know printing i is calling to print the index, how is the node printing too? And how to I get only the previous node to print rather than all previous nodes?

public SingleNode findPrev(int data) {
		for (int i = 0; i < length(); i++) {
			if ( i != data) {
				System.out.println(i);
			}
		}
		return null;
	}

Output:

0
1
2
480-> 253-> <null>
253-> <null>
<null>

[GregBrannon]

There's code you didn't show us that's responsible for the rest of the output. Show us more - especially the code after the call to finfPrev() - but any other parts you think will be useful.

Since findPrev() always returns null, I don't think it's doing anything but printing the i indices that don't equal the parameter data. All of them?

This post has been edited by GregBrannon: 04 February 2012 - 09:17 AM

[eikkaj]

You're right, it isn't doing anything..
Should this method be returning SingleNode? What if it returns int instead? I'm really having trouble visualizing what this should be looking like..

This is my linkedlist class:

public class SingleList {

	private SingleNode head;
	
	public SingleList() {
		head = null;
	}
	 public int length(){
		 SingleNode temp = head;
		 int counter = 0;
		 while(temp!=null){
			 temp = temp.getNext();
			 counter++;
		 }
		 return counter;
   }
	 
	public void addHead(int data) {
		SingleNode n = new SingleNode();
		
		n.setData(data);
		n.setNext(head);
		head = n;
	}
	
	public void addTail(int data) {
		SingleNode n = head;
		
		while (n != null) {
			if (n.getNext() == null)
				break;
			n = n.getNext();
		}
		
		if (n == null) {
			// The list is empty, we are adding to the head
			addHead(data);
		} else {
			//Standard add, we have a reference to the last node in the list
			
			// Make a new node, and set up the data
			SingleNode nn = new SingleNode();
			nn.setData(data);
			
			// set the new node's next to be the old last node
			nn.setNext(n.getNext());
			
			// set the old last node's next to refer to the new node
			n.setNext(nn);
		}
	}
	
	public int removeHead() {
		assert (head != null);
		
		int d = head.getData();
		head = head.getNext();
			
		return d;

		
	}
	
	public boolean isEmpty() {
		return (head == null);
	}
	
	public int removeNextNode(SingleNode n) {
		int x = 0;
		// Empty list
		assert (n != null);
		assert (n.getNext() != null);

		if (n.getNext() != null) {
			x = n.getNext().getData();
			n.setNext(n.getNext().getNext());
		}
		return x;
	}
	
//this is the method in question
	public int findPrev(int data) {
		for (int i = 0; i < length(); i++) {
			if ( i != data) {
				System.out.println(i);

		System.out.println("this!!!!");
		return data;
			}
		}
	}
	
	public void printList() {
		SingleNode n = head;
		
		while (n != null) {
			System.out.print(n.getData() + "-> ");
			n = n.getNext();
		}
		System.out.println("<null>");
	}
}

[GregBrannon]

I would think findPrev() would do something like:

SingleNode tempNode = head;
for ( int i = 0 ; i < length() ; i++ )
{
    if ( tempNode.next.getData() == data )
    {
        return tempNode;
    }
}

return null;

[eikkaj]

Doesn't that just print out data when the tempnode equals data, when in reality we want the data BEFORE the data entered?

[GregBrannon]

Oh, I see I left something out. Here's the revised code:

SingleNode tempNode = head;
for ( int i = 0 ; i < length() ; i++ )
{
    if ( tempNode.getNext().getData() == data )
    {
        return tempNode;
    }
    else
    {
        tempNode = tempNode.getNext();
    }

}

return null;

Even so, my suggestion doesn't print out anything. What it does do:

Starting with the head, it 'peeks' at the value of the next node, and if the next node's data equals the data we're looking for, then the current node, the head, is returned as the previous node to the node with the desired data.

If the value of the data next in the next node is not equal to the data being searched for, then the current node, tempNode, moves to the nextNode and repeats. This occurs until all nodes are searched. If a node with the desired value is not found, null is returned.

This is untested, and I'm sure requires tuning for your node class, but it's a concept that should work.

[eikkaj]

You're right, thanks a lot. I should've thought of creating a temp node from the start.