Results 1 to 10 of 10
  1. #1
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default LinearLinkedList

    I recently started reading about Linked Lists and I have a couple of questions. Before I start asking, let me post the ListNode class:

    Java Code:
    package linkedLists;
    
    public class ListNode {
    	private Object value;
    	private ListNode next;
    	
    	public ListNode(Object value, ListNode next) {
    		this.value = value;
    		this.next = next;
    	}
    	
    	public Object getValue() {
    		return value;
    	}
    	
    	public ListNode getNext() {
    		return next;
    	}
    	
    	public void setValue(Object value) {
    		this.value = value;
    	}
    	
    	public void setNext(ListNode next) {
    		this.next = next;
    	}
    }
    Pretty straightforward. Next, there is the LinearLinkedList class:

    Java Code:
    package linkedLists;
    
    public class LinearLinkedList {
    	
    	ListNode firstNode;
    	
    	public LinearLinkedList() {
    		firstNode = null;
    	}
    	
    	public boolean isEmpty() {
    		return firstNode == null;
    	}
    	
    	public ListNode getFirstNode() {
    		return firstNode;
    	}
    	
    	public void setFirstNode(ListNode node) {
    		firstNode = node;
    	}
    	
    	public void addFirst(Object o) {
    		if (isEmpty())
    			firstNode = new ListNode(o, null);
    		else {
    			//[I]implementation shown below[/I]
    		}
    	}
    	
    	public void addLast(Object o) {
    		if (isEmpty())
    			firstNode = new ListNode (o, null);
    		else {
    			//[I]implementation shown below[/I]
    		}
    	}
           
            [I]...other codes will be implemented later. (not in this thread)[/I]
    }
    Question 1: addFirst()
    The book implements the missing code like this:
    Java Code:
    firstNode = new ListNode(o, firstNode);
    When I did it, I did another way:
    Java Code:
    			ListNode first = new ListNode(o, null);
    			first.setNext(firstNode.getNext());
    			firstNode = first;
    The question is, are those two similar?

    Question 2: addLast()
    The book implements the missing code like this:
    Java Code:
    ListNode current = firstNode;
    while (current.getNext() != null)
         current = current.getNext();
    current.setNext(new ListNode(o, null));
    Mine on the other hand, gets a null pointer access (yellow underline in eclipse. The underlined word is "current" in "current.setNext(new ListNode(o, null));"
    Java Code:
    while ((current = current.getNext()) != null);
    [U]current[/U].setNext(new ListNode(o, null));
    firstNode = current;
    Why am I getting the null pointer access? Also, why doesn't the book's code have the following:
    Java Code:
    firstNode = current;
    Don't I need to reference firstNode to current because current is a local variable?

    Thanks in advance!!
    Last edited by Lil_Aziz1; 06-18-2010 at 02:07 AM.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,875
    Rep Power
    25

    Default

    Its better to ALWAYS use {} with loops and if statements.
    On What condition do you fall out of the while loop? What value does current have then?

  3. #3
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    I fall out of the while loop when current.getNext() is equal to null.

    EDIT: OHH. so the book's while loop is one iteration behind me, which is where it's suppose to be. Mine goes one iteration too far; thus, it's value is null!

    Thanks! Rep+! What about the first question?
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,875
    Rep Power
    25

    Default

    while (current.getNext() != null)
    current = current.getNext();
    vs
    while (current.getNext() != null) {
    current = current.getNext();
    }
    Some day you'll add a line after the while and everything will go to s.

  5. #5
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    I don't know if you noticed, but there is a semicolon after the while loop:
    Java Code:
    while ((current = current.getNext()) != null);
    current.setNext(new ListNode(o, null));
    firstNode = current;
    I intentionally put it the semicolon so all it does is iterate through the firstNode and make current get to the last element.

    I learned that the following two snippets are equivalent.
    Java Code:
    while ((current = current.getNext()) != null);
    Java Code:
    while ((current = current.getNext()) != null) {
    }
    Although I tried it with the {} and nothing changed. I'm still getting the null pointer access.
    Last edited by Lil_Aziz1; 06-18-2010 at 01:29 AM.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  6. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,875
    Rep Power
    25

    Default

    The first loop does NOT have a ; after the condition:
    The book implements the missing code like this:
    Code:
    ListNode current = firstNode;
    while (current.getNext() != null)
    current = current.getNext();
    current.setNext(new ListNode(o, null));
    Mine on the other hand, gets a null pointer access (yellow underline in eclipse. The underlined word is "current" in "current.setNext(new ListNode(o, null));"
    Code:
    while ((current = current.getNext()) != null);
    current.setNext(new ListNode(o, null));
    firstNode = current;

  7. #7
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    Right. But aren't the {} implied if there is only one line of code to execute? I double checked the book and this is exactly how they had it so it's not a typo on my part.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  8. #8
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,875
    Rep Power
    25

    Default

    I'm not talking about legal statements.
    I'm talking about safe code.

  9. #9
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    Oh okay.

    Going back on topic, I think I got almost all my questions answered except this part:
    Java Code:
    firstNode = current;
    Don't I need to reference firstNode to current because current is a local variable?
    Why don't we have to do that?
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,763
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Lil_Aziz1 View Post
    Java Code:
    while ((current = current.getNext()) != null);
    [U]current[/U].setNext(new ListNode(o, null));
    firstNode = current;
    With code like that you're taking one step too many and you're falling of your list. The last element of your list is the element which doesn't have a next element (read that again ;-) so you have to change your loop like this:

    Java Code:
    for (current= firstElemt; current != null && current.getNext() != null; current= current.getNext());
    The test current != null is necessary in case the list is empty. While the current element has a next element it 'hops' to the next element, otherwise the loop terminates and current points to the last element in the list.

    kind regards,

    Jos

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •