Linked Lists

from the driver/testfile below, I get the output of these four lines:

3
IntNode@19821f
42
IntNode@addbf1


From what I understand the 42 is put at the "head" and then I added 3 nodes and removed one which gives me the 3 seen in the first line. Before it was removed, my guess is the list went like this: 42 --> 4 --> 5 --> 8 ? After the one node is removed, I played around with the listSearch() method to see what was removed and got these type of answers:

IntNode@19821f with: System.out.println(IntNode.listSearch(head, 5));

I then used a 4 instead of the 5 and got:
IntNode@addbf1 with: System.out.println(IntNode.listSearch(head, 4));

I get null with: System.out.println(IntNode.listSearch(head, 8));

The null tells me the 8 got removed. I can only think because it's the last one, but the method says something about removeNodeAfter which doesn't lead me to believe that is just because it is the last one added.

I see the "link=link.link" in the removeNodeAfter() method but I don't understand "link.link".

Code:

---


public class MyIntNode {


        public static void main(String[] args) {
               
                IntNode head;
                head = new IntNode(42, null);
               
                head.addNodeAfter(4);
                head.addNodeAfter(5);
                head.addNodeAfter(8);
               
                head.removeNodeAfter();
               
                System.out.println(IntNode.listLength(head));
                System.out.println(IntNode.listSearch(head, 5));
                System.out.println(head.getData());
                System.out.println(IntNode.listPosition(head, 3));
        }

} //end test file




public class IntNode
{
  // Invariant of the IntNode class:
  //  1. The node's integer data is in the instance variable data.
  //  2. For the final node of a list, the link part is null.
  //      Otherwise, the link part is a reference to the
  //      next node of the list.
       
  private int data; //the element stored in this node
  private IntNode link; //Refers to the next node in the list 


 
  public IntNode(int initialData, IntNode initialLink)
  {
      data = initialData;
      link = initialLink;
  }


  public void addNodeAfter(int item) 
  {
      link = new IntNode(item, link);
  }         
 
 
  /**
  * Accessor method to get the data from this node. 
  * @param - none
  * @return
  *  the data from this node
  **/
  public int getData( ) 
  {
      return data;
  }
 
 
  public IntNode getLink( )
  {
      return link;                                             
  }
   
   
  public static IntNode listCopy(IntNode source)
  {
      IntNode copyHead;
      IntNode copyTail;
     
      // Handle the special case of the empty list.
      if (source == null)
        return null;
       
      // Make the first node for the newly created list.
      copyHead = new IntNode(source.data, null);
      copyTail = copyHead;
     
      // Make the rest of the nodes for the newly created list.
      while (source.link != null)
      {
        source = source.link;
        copyTail.addNodeAfter(source.data);
        copyTail = copyTail.link;
      }
 
      // Return the head reference for the new list.
      return copyHead;
  }
 
 
  public static IntNode[ ] listCopyWithTail(IntNode source)
  {
      IntNode copyHead;
      IntNode copyTail;
      IntNode[ ] answer = new IntNode[2];
   
      // Handle the special case of the empty list. 
      if (source == null)
        return answer; // The answer has two null references .
     
      // Make the first node for the newly created list.
      copyHead = new IntNode(source.data, null);
      copyTail = copyHead;
     
      // Make the rest of the nodes for the newly created list.
      while (source.link != null)
      {
        source = source.link;
        copyTail.addNodeAfter(source.data);
        copyTail = copyTail.link;
      }
     
      // Return the head and tail references.
      answer[0] = copyHead;
      answer[1] = copyTail;
      return answer;
  }
 
 
  public static int listLength(IntNode head)
  {
      IntNode cursor;
      int answer;
     
      answer = 0;
      for (cursor = head; cursor != null; cursor = cursor.link)
        answer++;
       
      return answer;
  }
 

  public static IntNode[ ] listPart(IntNode start, IntNode end)
  {
      IntNode copyHead;
      IntNode copyTail;
      IntNode cursor;
      IntNode[ ] answer = new IntNode[2];
     
      // Make the first node for the newly created list. Notice that this will
      // cause a NullPointerException if start is null.
      copyHead = new IntNode(start.data, null);
      copyTail = copyHead;
      cursor = start;
     
      // Make the rest of the nodes for the newly created list.
      while (cursor != end)
      {
        cursor = cursor.link;
        if (cursor == null)
            throw new IllegalArgumentException
            ("end node was not found on the list");
        copyTail.addNodeAfter(cursor.data);
        copyTail = copyTail.link;
      }
     
      // Return the head and tail references
      answer[0] = copyHead;
      answer[1] = copyTail;
      return answer;
  }       
 
 
 
  public static IntNode listPosition(IntNode head, int position)
  {
      IntNode cursor;
      int i;
     
      if (position <= 0)
          throw new IllegalArgumentException("position is not positive");
     
      cursor = head;
      for (i = 1; (i < position) && (cursor != null); i++)
        cursor = cursor.link;

      return cursor;
  }


  public static IntNode listSearch(IntNode head, int target)
  {
      IntNode cursor;
     
      for (cursor = head; cursor != null; cursor = cursor.link)
        if (target == cursor.data)
            return cursor;
       
      return null;
  }

 
  public void removeNodeAfter( ) 
  {
      link = link.link;
  }         
 
 
  public void setData(int newData) 
  {
      data = newData;
  }                                                             
 
 
  public void setLink(IntNode newLink)
  {                   
      link = newLink;
  }
}

---

I just noticed in the above post, I led up to my question, but didn't really state much of a question. So...I was wondering what these two lines mean:


IntNode@19821f
IntNode@addbf1

Code:

---

        link = link.link;

---

Code:

---

From the class comments:
    //  2. For the final node of a list, the link part is null.
    //      Otherwise, the link part is a reference to the
    //      next node of the list.

---

So link is the next node.
To remove it redefine/reassign link to the value of the next following link, effectively skipping link.
Example, for nodes:

Code:

---

1, 2, 3, 4
head data = 1
link = 2
link.link = 3

---

So

Code:

---

link = link.link

---

gives node values of:

Code:

---

1, 3, 4

---

what these two lines mean:
The hex address of your object in the jvm.
You can get more verbose by refining your inspections:

Code:

---

public class IntNodeTest {
    public static void main(String[] args) {
        IntNode head = new IntNode(42, null);
        printNodes("initialization", head);

        head.addNodeAfter(4);
        head.addNodeAfter(5);
        head.addNodeAfter(8);
        printNodes("after adding 4, 5 and 8", head);

        head.removeNodeAfter();
        printNodes("after removing", head);

        System.out.println("head length: " + IntNode.listLength(head));
        IntNode search5 = IntNode.listSearch(head, 5);
        printNodes("search node search5", search5);
        System.out.println("head data: " + head.getData());
        IntNode pos3 = IntNode.listPosition(head, 3);
        printNodes("list node pos3", pos3);
    }

    private static void printNodes(String s, IntNode node) {
        System.out.println(s + ":");
        System.out.println(node.getData());
        while((node = node.getLink()) != null) {
            System.out.println(node.getData());
        }
        System.out.println("-------------");
    }
}

---

Thanks, your file complied great, but I still can't figure out how a list works. So in order to get a list to look like 1, 2, 3, 4. I add them in the order of 1, to initialize then 4, then 3 and lastly a 2?


in the case of your list of:
1, 2, 3, 4
head data = 1
link = 2
link.link = 3

is 2 a node and a link then? or is 2 just a link? does it go node then link then link.link then back to node?

s 2 a node and a link then? or is 2 just a link? does it go node then link then link.link then back to node
In [1, 2, 3, 4] each number is a node. For any node the next node is node.link, or node.getLink() since 'link' is private in the IntNode class. To get the next node from node 2 you call node.getLink() which returns the node (whose data field is) 3. So each item is a node and 'link' is the way to advance to the next node.

alrighty I'm getting it now, thank you much

I think you got the point, but you get memory addresses in hex format when you attempt to print an object that has no toString() method. When an object DOES have a toString method, printing said object will print whatever is defined in the toString().

For example:

Code:

---

public class Demo{
    int number = 10;
    String name = "bob";
}
...
System.out.println(new Demo());
//will result in something like you found:
//Demo@19821f
//But, add a toString method like so:

public class Demo{
    int number = 10;
    String name = "bob";

    public String toString(){
        return "My name is "+name+" and my number is "+number+".";
    }
}
...
System.out.println(new Demo());
//will result in:
//My name is bob and my number is 10.

---