public class DoublyLinkedList {

private static class Node {

/** 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 prev; // reference to the previous node in the list

/** A reference to the subsequent 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 E getElement() { return element; }

public Node getPrev() { return prev; }

public Node getNext() { return next; }

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

public void setNext(Node n) { next = n; } } //----------- end of nested Node class -----------

// instance variables of the DoublyLinkedList /** Sentinel node at the beginning of the list */ private Node header; // header sentinel

/** Sentinel node at the end of the list */ private Node 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<>(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 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 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 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(); }

public String toString() { StringBuilder sb = new StringBuilder("("); Node walk = header.getNext(); while (walk != trailer) { sb.append(walk.getElement()); walk = walk.getNext(); if (walk != trailer) sb.append(", "); } sb.append(")"); return sb.toString(); } //main method public static void main(String[] args) { //create and populate a doubly linked list DoublyLinkedList list = new DoublyLinkedList(); list.addFirst("MSP"); list.addLast("ATL"); list.addLast("BOS"); // list.addFirst("LAX"); System.out.println(list); System.out.println(list.first()); // } } //----------- end of DoublyLinkedList class -----------

In this exercise, you will use the DoublyLinkedList implementation of above example. Write a method for concatenating two doubly linked lists , 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.