[<3DIC]

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
  
}

[macosxnerd101]

Just get the last Node from L, and set its next Node to M.

[<3DIC]

Will this work?

public DList concatenate(DList L, DList M) 
  {
	  M.head = L.tail;
	  
	  return L;
  } // end concatenate

[macosxnerd101]

No- the Nodes are private. See your classes for appropriate getter and setter methods.

[pbl]

<3DIC, on 27 February 2011 - 11:50 PM, said:

Will this work?

public DList concatenate(DList L, DList M) 
  {
	  M.head = L.tail;
	  
	  return L;
  } // end concatenate

more
M.tail = L.head;

and the method can be void the list will be merge
L won't be accessible anymore

[<3DIC]

How about this?

public DList concatenate(DList L, DList M) 
  {	  
	  L.addLast(M.getFirst());
	  
	  return L;
  } // end concatenate

Out of curiosity how did you know my last one wouldn't work? I am using eclipse and it gave no errors when i typed the last method in. (or this one )

This post has been edited by <3DIC: 27 February 2011 - 10:03 PM

[macosxnerd101]

Scratch that. I thought you were defining the method outside of the List and Node classes. As long as you are defining the concatenate() method in the DList class, you can access DList private variables. That being said, you would want to set the next Node for tail to M.head, not tail = M.head, as that would overwrite your current Tail Node.

[<3DIC]

Oh i see, yes i am writing the concatenate method with in DList,, sorry for leaving that bit out!

So just to be clear then, this would work then?

public DList concatenate(DList L, DList M) 
  {	  
          M.head = L.tail;
	  
	  return L;
  } // end concatenate 

[macosxnerd101]

As I explained earlier, no. That overwrites the second List. You have to set the L.tail next Node to M.head. See the DNode class for the setNext() method.

[<3DIC]

Hmmm if this is what you mean eclipse says "setNext() DNode is undefined for type DList"

public DList concatenate(DList L, DList M) 
  {	  
	  
	  M.head = setNext(L.tail);
	  
	  return L;
  } // end concatenate 

Also you never said if this approach would work: (i doesnt give errors but i dont know if one of the lists is getting overwritten)

public DList concatenate(DList L, DList M) 
  {	  
	  L.addLast(M.getFirst());
	  
	  return L;
  } // end concatenate 

[macosxnerd101]

As for your first attempt, remember in your previous threads when I mentioned looking through your classes carefully for a setNext() method. This is one of those instances. Look at the Node class.

As for your second approach, that's the same concept as what I've been suggesting. Just a different set of methods.

[<3DIC]

Okay this gives no errors, but does it accomplish the task?

public DList concatenate(DList L, DList M) 
  {	  
	    
	  M.head.setNext(L.tail);
	  
	  return L;
  } // end concatenate

[macosxnerd101]

macosxnerd101, on 28 February 2011 - 12:13 AM, said:

As I explained earlier, no. That overwrites the second List. You have to set the L.tail next Node to M.head.

Re-read this post. In your code, you are setting M.Head to point to L.Tail. You need to do the opposite. Otherwise, you will be overwriting most of the M list.

[<3DIC]

Seems counter-intuitive to me:

 public DList concatenate(DList L, DList M) 
  {	  
	  //L.addLast(M.getFirst()); does this work, you never gave me strait answer
	  
	  L.tail.setNext(M.head);
	  
	  return L;
  } // end concatenate

This post has been edited by <3DIC: 27 February 2011 - 11:09 PM

[macosxnerd101]

Both would work. Also, the best way to determine if something works is to run it and compare the output from what you get to what you would expect.