Results 1 to 2 of 2
  1. #1
    coder94 is offline Member
    Join Date
    Feb 2011
    Posts
    1
    Rep Power
    0

    Default concatenating linked lists

    I am trying to write a method to concatenate linked lists but i am having a bit of trouble. I have a couple classes at my disposal with quite a few methods, how can i go about this problem?

    Here is my method so far:

    Java Code:
    public DList concatenate(DList L, DList M)  // M should be added to the end of L
      {
    	  DNode A, B;
    	  
    	  for (int i = 0; i < M.size(); i++)
    	  {
    		  addAfter();
    	  }
    	  
    	  return L;
      } // end concatenate
    Here are the 2 classes i have to work with:


    Java Code:
    /** Node of a doubly linked list of strings */
    public class DNode
    {
      private String element;	// String element stored by a node
      private DNode next, prev;	// Pointers to next and previous nodes
    
      /** Constructor that creates a node with given fields 
       *  Parameters: 
       *  	e - the initial element of this new node
       * 	p - a reference to the node before this new node
       * 	n - a reference to a node after this new node
       * 	(references may be null)
       *  Postcondition:
       *  	This new node contains the specified data and links to the 
       *  	previous and next nodes
       **/
      public DNode(String e, DNode p, DNode n) 
      {
        element = e;
        prev = p;
        next = n;
      }
      
      /** Accessor method to get the element from this node. 
       *  Returns: 
       *  	the element of this node 
       **/
      public String getElement()
      { 
    	  return element; 
      }
      
      /** Accessor method to get a reference to the previous node.
       *  Returns:
       *	the previous node of this node 
       **/
      public DNode getPrev() 
      { 
    	  return prev; 
      }
      
      /** Accessor method to get a reference to the next node.
       *  Returns:
       *  	the next node of this node 
       * */
      public DNode getNext() 
      { 
    	  return next; 
      }
      
      /** Sets the element of this node
       *  Parameters:
       *  	newElem - the new element to place in this node
       *  Postcondition:
       *  	The element of this node has been set to newElem. 
       **/
      public void setElement(String newElem) 
      { 
    	  element = newElem; 
      }
      
      /** Sets the previous node of this node
       *  Parameters:
       *  	newPrev - a reference to the node that should appear before 
       *  		this node (or the null reference)
       *  Postcondition:
       *  	The link to the node before this node has been set to newPrev. 
       **/
      public void setPrev(DNode newPrev) 
      { 
    	  prev = newPrev; 
      }
      
      /** Sets the next node of this node
       *  Parameters:
       *  	newNext - a reference to the node that should appear after 
       *  		this node (or the null reference)
       *  Postcondition:
       *  	The link to the node after this node has been set to newNext. 
       **/
      public void setNext(DNode newNext) 
      { 
    	  next = newNext; 
      }
      
      
    }
    Java Code:
    /** Doubly linked list with nodes of type DNode storing strings. */
    public class DList 
    {
      private int size;			// number of elements
      private DNode head, tail;	// sentinels
      
      /** Constructor that creates an empty list */
      public DList() 
      { 
        size = 0;
        head = new DNode(null, null, null);	// create dummy head node
        tail = new DNode(null, head, null);	// create dummy tail node
        head.setNext(tail);	// make head and tail point to each other
      }
      
      /** Returns the number of elements in the list */
      public int size() 
      { 
    	  return size; 
      }
      
      /** Returns whether the list is empty */
      public boolean isEmpty() 
      { 
    	  return (size == 0); 
      }
      
      /** Returns the first node of the list
       *  Precondition:
       *  	List is not empty
       *  Throws: IllegalStateException
       *	Indicates that the list is empty
       **/
      public DNode getFirst() throws IllegalStateException 
      {
        if (isEmpty()) throw new IllegalStateException("List is empty");
        return head.getNext();
      }
      
      /** Returns the last node of the list
       *  Precondition:
       *  	List is not empty
       *  Throws: IllegalStateException
       *	Indicates that the list is empty
       **/
      public DNode getLast() throws IllegalStateException 
      {
        if (isEmpty()) throw new IllegalStateException("List is empty");
        return tail.getPrev();
      }
      
      /** Returns the node before the given node v.
       *  Parameters:
       * 	v - reference to a node in the list
       *  Precondition:
       *  	v is not the head and v is not null
       *  Returns:
       *  	the node before the given node v. 
       *  Throws: IllegalArgumentException
       *  	Indicates that v is the head 
       **/
      public DNode getPrev(DNode v) throws IllegalArgumentException 
      {
        if (v == head) throw new IllegalArgumentException
          ("Cannot move back past the head of the list");
        return v.getPrev();
      }
      
      /** Returns the node after the given node v. 
       *  Parameters:
       * 	v - reference to a node in the list
       *  Precondition:
       *  	v is not the tail and v is not null 
       *  Returns:
       *  	the node after the given node v. 
       *  Throws: IllegalArgumentException
       *  	Indicates that v is the tail 
       **/
      public DNode getNext(DNode v) throws IllegalArgumentException 
      {
        if (v == tail) throw new IllegalArgumentException
          ("Cannot move forward past the tail of the list");
       return v.getNext();
      }
    
      /** Inserts the given node z before the given node v.
       *  Parameters:
       * 	v - reference to a node in the list, 
       *    z - reference to the node to be inserted 
       *  Precondition:
       *  	v is not the head and v is not null and z is not null
       *  Postcondition:
       *  	Node z has been inserted before the given node v
       *  Throws: IllegalArgumentException
       *  	Indicates that v is the head 
       **/
      public void addBefore(DNode v, DNode z) throws IllegalArgumentException 
      {
        DNode u = getPrev(v);	// may throw an IllegalArgumentException
    
        z.setPrev(u);
        z.setNext(v);
        v.setPrev(z);
        u.setNext(z);
        size++;
      }
      
      /** Inserts the given node z after the given node v.
       *  Parameters:
       * 	v - reference to a node in the list, 
       *    z - reference to the node to be inserted
       *  Precondition:
       *  	v is not the tail and v is not null and z is not null
       *  Postcondition:
       *  	Node z has been inserted after the given node v
       *  Throws: IllegalArgumentException
       *  	Indicates that v is the tail
       **/
      public void addAfter(DNode v, DNode z) throws IllegalArgumentException 
      {
        DNode w = getNext(v);	// may throw an IllegalArgumentException
    
        z.setPrev(v);
        z.setNext(w);
        w.setPrev(z);
        v.setNext(z);
        size++;
      }
      
      /** Inserts the given node v at the head of the list
       *  Parameters:
       *  	v - reference to the node to be inserted
       *  Precondition: v is not null 
       *  Postcondition:
       *  	Node v has been inserted at the head of the list
       **/
      public void addFirst(DNode v) 
      {
        addAfter(head, v);
      }
      
      /** Inserts the given node v at the tail of the list
       *  Parameters:
       *  	v - reference to the node to be inserted
       *  Precondition: v is not null 
       *  Postcondition:
       *  	Node v has been inserted at the tail of the list
       **/
      public void addLast(DNode v) 
      {
        addBefore(tail, v);
      }
      
      /** Removes the given node v from the list.
       *  Parameters:
       *  	v - reference to the node to be removed 
       *  Precondition:
       *  	v is not the head and v is not the tail
       *  Postcondition:
       *  	Node v has been removed from the linked list
       **/
      public void remove(DNode v) 
      {
        DNode u = getPrev(v);	// may throw an IllegalArgumentException
    
        DNode w = getNext(v);	// may throw an IllegalArgumentException
        // unlink the node from the list 
        w.setPrev(u);
        u.setNext(w);
        v.setPrev(null);
        v.setNext(null);
        size--;
      }
    
      /** Returns whether a given node has a previous node
       *  Parameters:
       * 	v - reference to a node in the list
       *  Returns:
       *    true if v has a previous node; false otherwise
       **/
      public boolean hasPrev(DNode v)
      { 
    	  return v != head;
      }
      
      /** Returns whether a given node has a next node
       *  Parameters:
       * 	v - reference to a node in the list
       *  Returns:
       *    true if v has a next node; false otherwise 
       **/
      public boolean hasNext(DNode v) 
      { 
    	  return v != tail; 
      }
      
      /** Returns a string representation of the list */
      public String toString() 
      {
        String s = "[";
        
        DNode v = head.getNext();
        
        while (v != tail) 
        {
          s += v.getElement();
          v = v.getNext();
          if (v != tail)
        	  s += ",";
        }
        
        s += "]";
        return s;
      }
      
      public DList concatenate(DList L, DList M) 
      {
    	  DNode A, B;
    	  
    	  for (int i = 0; i < M.size(); i++)
    	  {
    		  addAfter();
    	  }
    	  
    	  return L;
      } // end concatenate
      
    }
    Last edited by coder94; 02-28-2011 at 04:16 AM. Reason: left out a few details

  2. #2
    Ravik is offline Member
    Join Date
    Feb 2011
    Posts
    3
    Rep Power
    0

    Default

    The problem with the method:
    public DList concatenate(DList L, DList M)
    {
    DNode A, B;

    for (int i = 0; i < M.size(); i++)
    {
    addAfter();
    }
    return L;
    }
    addAfter() method must contain references to last node of L and first node of M and it voilates the precondition of addAfter() method which says "node of L should not be a tail ". And last node reference of L must be incremented as loop increments
    It is a big code and I require some time to make changes in addAfter() method...
    Better if you can come with another method to concat nodes after tail of L
    Last edited by Ravik; 02-28-2011 at 06:20 AM.

Similar Threads

  1. Linked Lists
    By Dee in forum New To Java
    Replies: 18
    Last Post: 02-02-2011, 03:14 AM
  2. Linked Lists Queue
    By bdario1 in forum New To Java
    Replies: 0
    Last Post: 04-28-2010, 04:40 AM
  3. Concatenate Linked Lists
    By tttestall in forum New To Java
    Replies: 1
    Last Post: 04-20-2010, 07:03 PM
  4. Linked Lists
    By vendetta in forum New To Java
    Replies: 6
    Last Post: 01-26-2010, 08:23 AM
  5. Doubly Linked Lists
    By stevenson15 in forum New To Java
    Replies: 6
    Last Post: 04-21-2009, 12:35 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
  •