title: Write a method for concatenating two doubly linked lists L and M
body: <pre><code>package linkedlists;
  
  import linkedlists.DoublyLinkedList.Node;
  
  
  public class DoublyLinkedList&lt;E&gt; {
  
    //---------------- nested Node class ----------------
    /**
     * Node of a doubly linked list, which stores a reference to its
     * element and to both the previous and next node in the list.
     */
    public static class Node&lt;E&gt; {
  
      /** The element stored at this node */
      private E element;               // reference to the element stored at this node
  
      /** A reference to the preceding node in the list */
      private Node&lt;E&gt; prev;            // reference to the previous node in the list
  
      /** A reference to the subsequent node in the list */
      private Node&lt;E&gt; next;            // reference to the subsequent node in the list
  
      /**
       * Creates a node with the given element and next node.
       *
       * @param e  the element to be stored
       * @param p  reference to a node that should precede the new node
       * @param n  reference to a node that should follow the new node
       */
      public Node(E e, Node&lt;E&gt; p, Node&lt;E&gt; n) {
        element = e;
        prev = p;
        next = n;
      }
  
      // public accessor methods
      /**
       * Returns the element stored at the node.
       * @return the element stored at the node
       */
      public E getElement() { return element; }
  
      /**
       * Returns the node that precedes this one (or null if no such node).
       * @return the preceding node
       */
      public Node&lt;E&gt; getPrev() { return prev; }
  
      /**
       * Returns the node that follows this one (or null if no such node).
       * @return the following node
       */
      public Node&lt;E&gt; getNext() { return next; }
  
      // Update methods
      /**
       * Sets the node's previous reference to point to Node n.
       * @param p    the node that should precede this one
       */
      public void setPrev(Node&lt;E&gt; p) { prev = p; }
  
      /**
       * Sets the node's next reference to point to Node n.
       * @param n    the node that should follow this one
       */
      public void setNext(Node&lt;E&gt; n) { next = n; }
      
    } //----------- end of nested Node class -----------
  
    // instance variables of the DoublyLinkedList
    /** Sentinel node at the beginning of the list */
    private Node&lt;E&gt; header;                    // header sentinel
  
    /** Sentinel node at the end of the list */
    private Node&lt;E&gt; trailer;                   // trailer sentinel
  
    /** Number of elements in the list (not including sentinels) */
    private int size = 0;                      // number of elements in the list
  
    /** Constructs a new empty list. */
    public DoublyLinkedList() {
      header = new Node&lt;&gt;(null, null, null);      // create header
      trailer = new Node&lt;&gt;(null, header, null);   // trailer is preceded by header
      header.setNext(trailer);                    // header is followed by trailer
    }
  
    // public accessor methods
    /**
     * Returns the number of elements in the linked list.
     * @return number of elements in the linked list
     */
    public int size() { return size; }
  
    /**
     * Tests whether the linked list is empty.
     * @return true if the linked list is empty, false otherwise
     */
    public boolean isEmpty() { return size == 0; }
  
    /**
     * Returns (but does not remove) the first element of the list.
     * @return element at the front of the list (or null if empty)
     */
    public E first() {
      if (isEmpty()) return null;
      return header.getNext().getElement();   // first element is beyond header
    }
  
    /**
     * Returns (but does not remove) the last element of the list.
     * @return element at the end of the list (or null if empty)
     */
    public E last() {
      if (isEmpty()) return null;
      return trailer.getPrev().getElement();    // last element is before trailer
    }
  
    // public update methods
    /**
     * Adds an element to the front of the list.
     * @param e   the new element to add
     */
    public void addFirst(E e) {
      addBetween(e, header, header.getNext());    // place just after the header
    }
  
    /**
     * Adds an element to the end of the list.
     * @param e   the new element to add
     */
    public void addLast(E e) {
      addBetween(e, trailer.getPrev(), trailer);  // place just before the trailer
    }
  
    /**
     * Removes and returns the first element of the list.
     * @return the removed element (or null if empty)
     */
    public E removeFirst() {
      if (isEmpty()) return null;                  // nothing to remove
      return remove(header.getNext());             // first element is beyond header
    }
  
    /**
     * Removes and returns the last element of the list.
     * @return the removed element (or null if empty)
     */
    public E removeLast() {
      if (isEmpty()) return null;                  // nothing to remove
      return remove(trailer.getPrev());            // last element is before trailer
    }
  
    // private update methods
    /**
     * Adds an element to the linked list in between the given nodes.
     * The given predecessor and successor should be neighboring each
     * other prior to the call.
     *
     * @param predecessor   node just before the location where the new element is inserted
     * @param successor     node just after the location where the new element is inserted
     */
    private void addBetween(E e, Node&lt;E&gt; predecessor, Node&lt;E&gt; successor) {
      // create and link a new node
      Node&lt;E&gt; newest = new Node&lt;&gt;(e, predecessor, successor);
      predecessor.setNext(newest);
      successor.setPrev(newest);
      size++;
    }
  
    /**
     * Removes the given node from the list and returns its element.
     * @param node    the node to be removed (must not be a sentinel)
     */
    private E remove(Node&lt;E&gt; node) {
      Node&lt;E&gt; predecessor = node.getPrev();
      Node&lt;E&gt; successor = node.getNext();
      predecessor.setNext(successor);
      successor.setPrev(predecessor);
      size--;
      return node.getElement();
    }
  
    /**
     * Produces a string representation of the contents of the list.
     * This exists for debugging purposes only.
     */
    public String toString() {
      StringBuilder sb = new StringBuilder(&quot;(&quot;);
      Node&lt;E&gt; walk = header.getNext();
      while (walk != trailer) {
        sb.append(walk.getElement());
        walk = walk.getNext();
        if (walk != trailer)
          sb.append(&quot;, &quot;);
      }
      sb.append(&quot;)&quot;);
      return sb.toString();
    }
    
    public DoublyLinkedList&lt;E&gt; concatenate(DoublyLinkedList&lt;E&gt; L, DoublyLinkedList&lt;E&gt; M) {
        
        M.header = L.trailer;
        M.trailer = L.header;
        
        return L;
    }
    
  //main method
    public static void main(String[] args)
    {
        //create and populate a doubly linked list
        DoublyLinkedList&lt;String&gt; list = new DoublyLinkedList&lt;String&gt;();
        list.addFirst(&quot;MSP&quot;);
        list.addLast(&quot;ATL&quot;);
        list.addLast(&quot;BOS&quot;);
        //
        list.addFirst(&quot;LAX&quot;);
        
       System.out.println(list);
       System.out.println(list.first());
        //
  
        
       
    }
  } 
  </code></pre>
  <p>Task:
  In this exercise, you will use the DoublyLinkedList implementation of the textbook (week 2 lecture examples. Write a method for concatenating two doubly linked lists L and M, with header and trailer sentinel nodes, into a single list L′. Write a main method to test the new method. Hint: Connect the end of L into the beginning of M.</p>
  <p>I am having difficulties solving this problem, I wrote this code</p>
  <pre><code>public DoublyLinkedList&lt;E&gt; concatenate(DoublyLinkedList&lt;E&gt; L, DoublyLinkedList&lt;E&gt; M) {
        
        M.header = L.trailer;
        M.trailer = L.header;
        
        return L;
    }
  </code></pre>
  <p>and modify it a lot for a couple of hours, but still cannot get what is it. Can anyone help?</p>
  <p>Main</p>
  <pre><code>DoublyLinkedList&lt;String&gt; list1 = new DoublyLinkedList&lt;String&gt;();
       list1.addFirst(&quot;A&quot;);
       list1.addLast(&quot;B&quot;);
       list1.addLast(&quot;C&quot;);
       list1.addLast(&quot;D&quot;);
  
       
  DoublyLinkedList&lt;String&gt; list2 = new DoublyLinkedList&lt;String&gt;();
       list2.addFirst(&quot;1&quot;);
       list2.addLast(&quot;2&quot;);
       list2.addLast(&quot;3&quot;);
       list2.addLast(&quot;4&quot;);
  
       
       list1.concatenate(list2);
       
       System.out.println(list1);
  </code></pre>