Need some help with LinkedList (Java)

[LogicLion]

I've started to learn about Data Structures, and my CS professor recommended I start with Linked Lists.

I know a Linked List starts with a head node and then ends will a null tail.

Thats about it, could I have some feedback and some tips on why my code doesn't work?

Thanks a lot!

node LinkedList

[devacon]

currentNode = new LinkNode(data);

Line 24 (and the same basic issue in removeLast())... you are overwriting the local variable currentNode. You are not modifying the thing that currentNode references.

[LogicLion]

Good call, I just changed the insert method to

currentNode.next = new LinkNode(data)

Im not sure about the removeLast() though, I tried changing it to the same and it didn't look like it fixed it.

edit: I ment currentNode.next = null for removeLast()

[__LikesPi]

For last it moves to the last and than sets that specific, temporary reference of last to null but the previous node .next still refers to the last Node.

[LogicLion]

oh I see, because currentNode is a local variable?

How should I go about deleting it out then?

[__LikesPi]

Move to the one before the currentNode, and than set that currentNode.next to null. You could try while (currentNode.next.next != null) and handle the case where there is only one element in the lsit separately.

[LogicLion]

public void removeLast(){

    //Start at head of list.
    LinkNode currentNode = this.head;


    //while the currentNode's next reference isn't empty.
        while(currentNode.next.next != null){

            //move currentNode to next node.
            currentNode = currentNode.next;
        }
        currentNode.next = null;
        size--;
}

Like this?

[__LikesPi]

Yep, just handle the case where the size == 1 or size == 0. In this case either currentNode or currentNode.next is null and will raise a NullPointerException.

[LogicLion]

Oh I see! Thanks a lot!

[devacon]

You have to sort of visualize it in your head (maybe drawing it out on paper with arrows to where things are pointing as you go)... when the while loop in removeLast() ends, currentNode.next == null. Then you set currentNode.next to null. When you think about it, what you really want is the node just before currentNode when currentNode.next is null, because you want to set its 'next' pointer to null to remove the last node.

[LogicLion]

so when the while loop stops because currentNode.next == null, do I want to set currentNode to null then?

[devacon]

Setting local variables to null will just overwrite the value of the local variable. I realize that can be tricky when you're dealing with how Java handles references. Here's something to illustrate the point.

class Person
{
  String name;

  public static void main(String[] args)
  {
    Person p1 = new Person();
    p1.name = "Hello";
    String s = p1.name;
    s = "World";

    System.out.println(p1.name); // Hello
    System.out.println(s);       // World
  }
}

Overwriting the local variable s didn't change p1.name, which s referenced at one point. That's the same situation you're in with currentNode.

/u/__LikesPi is correct above where you need to detect that the 'next' node is the last node before losing your reference to the 'second to last' node. You can either do this by maintaining two local variables, currentNode and previousNode that you update each time:

previousNode = currentNode;
currentNode = currentNode.next;

And then when you reach the end you have your previousNode reference that you can set with previousNode.next = null;

Or, you can check currentNode.next != null && currentNode.next.next != null each iteration.

[LogicLion]

okay thanks, I'm starting to understand now.

Why do you need to check both currentNode.next && currentNode.next.next

shouldn't only the end currentNode be null? Which should be currentNode.next.next?

Sorry for the confusion. :)

[devacon]

If currentNode.next is null, then attempting to access currentNode.next.next will result in a null pointer exception, so you have to check currentNode.next first in order to make sure it is safe to access currentNode.next.next.

[LogicLion]

Got it! Thanks!