concatenating linked lists

[coder94]

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:

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:

/** 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; 
  }
  
  
}

/** 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
  
}

[Ravik]

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