Results 1 to 5 of 5

Thread: Linked List

  1. #1
    Dozo23 is offline Member
    Join Date
    Feb 2013
    Posts
    11
    Rep Power
    0

    Default Linked List

    I have a program i need to write using a linked list. I need to just write the append and prepend methods. i am having trouble getting it to work. so far this is what i have.

    Java Code:
    // LinkedList.java
    // 
    // This version uses three instance variables,
    // a pointer to the first node, a pointer to
    // the last node, and length, to make our
    // append and getLength methods more efficient
    // than the would be if our only instance
    // variable were a pointer to the first node.
    //
    // This version uses a dummy first node.  Hence
    // it needs less decision-making than it would
    // need if a dummy first node were not used.
    //
    
    /**
     * Encapsulates a linked list of <code>String</code>.
     */
    public class LinkedList {
    
    /**  First node in linked list - dummy node  */
       private ListNode first = new ListNode(null);
    
    /**  Last node in linked list  */
       private ListNode last = first;
    
    /**  Number of data items in the list.  */
       private int length = 0;
    
      /**
        * Gets the number of data values currently
        * stored in this LinkedList.
        *
        * @return the number of elements in the list.
        */
    
       public int getLength()  { 
          return length; 
       }
    
    
       /**
        * Appends a String data element to this
        * LinkedList.
        *
        * @param data the data element to be appended.
        */
       public void append(String d)
       {
    	   ListNode n = new ListNode(d);
    	   last.next = n;
    	   last = n;
    	   length++;
    
         //  write the code here for append
    
       }  // method append(String)
    
    
       /**
        * Prepends (adds to the beginning) a String data element to this
        * LinkedList.
        *
        * @param data the data element to be prepended.
        */
       public void prepend(String d)
       {
    	   
    	   ListNode m = new ListNode(d);
    	   first.next = m;
    	   first = m;
    	   length++;
    
         //  write the code here for prepend
    
       }  // method append(String)
    
    
      /**
       *  Prints the contents of the Linked List
       *
       */
       public String toString() {
          ListNode p = first.next;
          String returnString = "";
          while (p != null) {
             returnString += p.data+" ";
          }
          return returnString;
       }
      
       /**
        * Determines whether this LinkedList is
        * equal in value to the parameter object.
        * They are equal if the parameter is of
        * class LinkedList and the two objects
        * contain the same short integer values at
        * each index.
        *
        * @param other the object to be compared
        *          to this LinkedList
        *
        * @return <code>true</code> if the parameter
        *        object is a LinkedList containing
        *        the same numbers at each index as
        *        this LinkedList, <code>false</code>
        *        otherwise.
        */
       public boolean equals(Object other)
       {
          if ( other == null 
                  || getClass() != other.getClass()
                  || length != ((LinkedList) other).length )
              return false;
    
          ListNode nodeThis = first;
          ListNode nodeOther = ((LinkedList) other).first;
          while ( nodeThis != null )
          {
              // Since the two linked lists are the same length,
              // they should reach null on the same iteration.
    
              if ( nodeThis.data != nodeOther.data )
                 return false;
    
              nodeThis = nodeThis.next;
              nodeOther = nodeOther.next;
          }  // while
    
          return true;
       }  // method equals
    
      
    
    }  // class LinkedList

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default Re: Linked List

    Java Code:
    public void prepend(String d) {
        ListNode m = new ListNode(d);
        first.next = m; //***********//
        first = m;
        length++;
    }
    This makes the new node the second item in the list not the first. You need to make first refer to the new node not first.next. But you must get things in the correct order or you will lose a reference to the rest of the List.

  3. #3
    Dozo23 is offline Member
    Join Date
    Feb 2013
    Posts
    11
    Rep Power
    0

    Default Re: Linked List

    here is the rest of the code.


    Java Code:
    public class Lab16Main {
    
    	public static void main(String[] args) {
    		
    		String [] dataSource = {"cat","bat","rat","sat","hat","fat"};
    		//generate empty lists
    		LinkedList myList1= new LinkedList();
    		LinkedList myList2= new LinkedList();
    		
    		//print out the empty lists
    		System.out.println("Here is myList1: "+myList1);
    		System.out.println("Here is myList2: "+myList2);
    		
    		// fill list 1 using append and print it.
    		for (int i=0; i<dataSource.length;i++)
    			myList1.append(dataSource[i]);
    		System.out.println("Here is myList1: "+myList1);
    		
    		//fill list 2 using prepend and print it.
    		for (int i=0; i<dataSource.length;i++)
    			myList1.prepend(dataSource[i]);
    		System.out.println("Here is myList2: "+myList2);
    	}
    }
    Java Code:
    // ListNode.java
    
    class ListNode
    {
       String data;
       ListNode next;
    
       ListNode(String d)
       {
          data = d;
          next = null;
       }  // constructor
    }  // class ListNode

  4. #4
    Dozo23 is offline Member
    Join Date
    Feb 2013
    Posts
    11
    Rep Power
    0

    Default Re: Linked List

    so append is correct?

    as for prepend i need to change it but i dont know how.
    this is what i got so far.

    Java Code:
     public void prepend(String d)
       {
    	   
    	   ListNode m = new ListNode(d);
    	   first = m;
    	   length++;
    
         //  write the code here for prepend
    
       }  // method append(String)
    but to tell you the truth i am completely lost.

  5. #5
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default Re: Linked List

    Having first refer to the new node is correct but as I said in previous post you have lost the reference to the rest of the List. You also have to have the new node refer to the previous first node BUT you must get it in the correct order.

    As for append it looks correct but you can answer that yourself with rigourous testing.

    Also, for both append and prepend you have a special case to consider: what happens when the List is empty? I disagree with how you are currently creating a new node with a null value and assigning it to first. I would just have first and last refer to null directly.
    Java Code:
    ListNode first = null;

Similar Threads

  1. Replies: 0
    Last Post: 09-25-2012, 04:07 AM
  2. Linked List, Array List time complexity
    By Rick99771977 in forum New To Java
    Replies: 4
    Last Post: 08-18-2011, 05:37 AM
  3. Replies: 4
    Last Post: 02-21-2011, 09:34 AM
  4. Linked list inside a linked list
    By viperlasson in forum New To Java
    Replies: 5
    Last Post: 07-26-2010, 11:15 PM
  5. Linked List integer list
    By igniteflow in forum Advanced Java
    Replies: 1
    Last Post: 12-10-2008, 08:53 PM

Posting Permissions

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