3.1. The textbooks code for a doubly-linked list class is included with the lab files. You will not change the DoublyLinkedList.java file. You will create another .java file with your own main program that uses the classes from DoubleLinkedList.java.

Use this to create an Integer doubly-linked list DLL1:

5 <-> 2 <-> 3 <-> 8 <-> 1 <-> 7 <-> 2 <-> 7 <-> 9 <-> 2 <-> 1.

3.2. Output all the values from the DLL1 to the console.

3.3. Using DLL1.removeFirst(), make a copy of the list to a new doubly-linked list, DLL2.

3.4. Output all the values from DLL2 to the console.

3.5. Using DLL2.removeLast(), make a copy of the list to a new doubly-linked list, DLL3. 3.5.1. While copying, change all nodes with value 2 to value 5. You should not insert any nodes with value 2 into DLL3. 3.5.2 While copying, change all nodes with value 7 to value 6. You should not insert any nodes with value 7 into DLL3.

3.6. Output all the values from DLL3 to the console.

Sample program output:

I am not picky about output formatting, but the values displayed must come from the nodes of the doubly-linked list, and not from the main program.

Rubric: Student name and date is in a comment on the first line of the programs: -5 points if fails Students program is a separate .java file from doublylinkedlist.java: -10 points if fails Create DLL1 with correct values: 2 points Create DLL2 using DLL1.removeFirst: 4 points Create DLL3 using DLL2.removeLast: 4 points Change node values before adding to DLL3: 3 points Output from DLL1, DLL2, DLL3: 2 points

Please paste a screenshot of a successful program run, and copy-and-paste the source code from your main program's .java file, here. You do not need to include the code from the textbook's DoublyLinkedLists.java file.

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 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 predecessor, Node successor) { // create and link a new node Node newest = new Node<>(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 node) { Node predecessor = node.getPrev(); Node 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("("); Node walk = header.getNext(); while (walk != trailer) { sb.append(walk.getElement()); walk = walk.getNext(); if (walk != trailer) sb.append(", "); } sb.append(")"); return sb.toString(); } } //----------- end of DoublyLinkedList class -----------