Java. Write a method to concatenate 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

public class DoublyLinkedList {

private static class Node {

private E element; // reference to the element stored at this node

private Node prev; // reference to the previous node in the list

private Node next; // reference to the subsequent node in the list

public Node(E e, Node p, Node n) {

element = e;

prev = p;

next = n;

}

// public accessor methods

public E getElement() { return element; }

public Node getPrev() { return prev; }

public Node getNext() { return next; }

// Update methods

public void setPrev(Node p) { prev = p; }

public void setNext(Node n) { next = n; }

} //----------- end of nested Node class -----------

// instance variables of the DoublyLinkedList

private Node header; // header sentinel

private Node trailer; // trailer sentinel

private int size = 0; // number of elements in the list

public DoublyLinkedList() {

header = new Node<>(null, null, null); // create header

trailer = new Node<>(null, header, null); // trailer is preceded by header

header.setNext(trailer); // header is followed by trailer

}

// public accessor methods

public int size() { return size; }

public boolean isEmpty() { return size == 0; }

public E first() {

if (isEmpty()) return null;

return header.getNext().getElement(); // first element is beyond header

}

public E last() {

if (isEmpty()) return null;

return trailer.getPrev().getElement(); // last element is before trailer

}

// public update methods

public void addFirst(E e) {

addBetween(e, header, header.getNext()); // place just after the header

}

public void addLast(E e) {

addBetween(e, trailer.getPrev(), trailer); // place just before the trailer

}

public E removeFirst() {

if (isEmpty()) return null; // nothing to remove

return remove(header.getNext()); // first element is beyond header

}

public E removeLast() {

if (isEmpty()) return null; // nothing to remove

return remove(trailer.getPrev()); // last element is before trailer

}

// private update methods

private void addBetween(E e, Node predecessor, Node successor) {

// create and link a new node

Node newest = new Node<>(e, predecessor, successor);

predecessor.setNext(newest);

successor.setPrev(newest);

size++;

}

private E remove(Node node) {

Node predecessor = node.getPrev();

Node successor = node.getNext();

predecessor.setNext(successor);

successor.setPrev(predecessor);

size--;

return node.getElement();

}

}