Results 1 to 7 of 7

Thread: Linked Lists

  1. #1
    vendetta is offline Member
    Join Date
    Jan 2010
    Posts
    31
    Rep Power
    0

    Default 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".

    Java 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;
       }
    }

  2. #2
    vendetta is offline Member
    Join Date
    Jan 2010
    Posts
    31
    Rep Power
    0

    Default

    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

  3. #3
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    Java Code:
            link = link.link;
    Java 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:
    Java Code:
    1, 2, 3, 4
    head data = 1
    link = 2
    link.link = 3
    So
    Java Code:
    link = link.link
    gives node values of:
    Java 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:
    Java 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("-------------");
        }
    }

  4. #4
    vendetta is offline Member
    Join Date
    Jan 2010
    Posts
    31
    Rep Power
    0

    Default

    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?

  5. #5
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    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.

  6. #6
    vendetta is offline Member
    Join Date
    Jan 2010
    Posts
    31
    Rep Power
    0

    Default

    alrighty I'm getting it now, thank you much

  7. #7
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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:
    Java 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.

Similar Threads

  1. Single linked lists - help
    By Srcee in forum New To Java
    Replies: 10
    Last Post: 10-29-2009, 06:35 PM
  2. Problem sending linked lists
    By deepthought015 in forum Networking
    Replies: 1
    Last Post: 04-26-2009, 01:47 PM
  3. Sending linked lists via sockets
    By deepthought015 in forum Networking
    Replies: 1
    Last Post: 04-26-2009, 03:33 AM
  4. Doubly Linked Lists
    By stevenson15 in forum New To Java
    Replies: 6
    Last Post: 04-21-2009, 01:35 PM
  5. question about linked lists
    By jkurth in forum Advanced Java
    Replies: 1
    Last Post: 11-11-2007, 09:33 AM

Posting Permissions

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