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 }