Doubly Linked List

Create an DoublyLinkedList class, a list whose elements are maintained in sorted order (this means that only comparable objects may be placed in an DoublyLinkedList, notice the generic parameter <E extends Comparable<? super E>> tells the compiler just that). Also note that a DoublyLinkedList may contain duplicate elements. The DoublyLinkedList class is implemented as a doubly-linked list whereas the LList class from our text is implemented as a singly-linked list. To accomplish this you will have to redefine the private Node<E> class to have an extra data field to point to the previous node. The data components of an DoublyLinkedList consist of a firstnode, lastNode, and length and a typical list is shown below. public class DoublyLinkedList<E extends Comparable<? super E>> implements SortedListInterface<E>{ public interface SortedListInterface<E>{ /** Task: Adds a new entry to its proper position in the list. * @param newEntry the object to be added as a new entry * @return true if the addition is successful, or false if not * DO NOT USE a sort() method here*/ public boolean add(E newEntry); /** Task: Removes the entry at a given position from the list. * Entries originally at positions higher than the given * position are at the next lower position within the list, * and the list's size is decreased by 1. * @param givenPosition an integer that indicates the position of * the entry to be removed; givenPosition >= 1 * and givenPosition <= getLength() * @return either the entry at position givenPosition, if the removal * was successful, or null */ public E remove(int givenPosition); /** Task: Removes anEntry from the list and returns its position back * to the caller. If anEntry is not found, return -1 indicating * the item is not found. * @param anEntry the entry to be removed; * @return the position of anEntry if the removal * was successful, or -1 */ public int remove(E anEntry); 
 /** Task: Removes all entries from the list. */ public void clear(); /** Task: Retrieves the entry at a given position in the list. * @param givenPosition an integer that indicates the position of * the desired entry; givenPosition >= 1 * and givenPosition <= getLength() * @return a reference to the indicated list entry, if found, * otherwise returns null */ public E getEntry(int givenPosition); /** Task: Determines whether the list contains a given entry. * @param anEntry the object that is the desired entry * @return true if the list contains anEntry, or false if not */ public boolean contains(E anEntry); /** Task: Gets the length of the list. * @return the integer number of entries currently in the list */ public int getLength(); /** Task: Determines whether the list is empty. * @return true if the list is empty, or false if not */ public boolean isEmpty(); /** Task: Determines whether the list is full. * @return true if the list is full, or false if not */ public boolean isFull(); /** Task: Displays all entries in the list, one item at a time * separated by commas in the order in which they occur in the list if
 * smallestToLargest is true, otherwise displays one item at a time in the * reverse order they appear in the list. */ public void display(boolean smallestToLargest); } // end SortedListInterface PART 2 Egyptian Multiplication and DoublyLinkedList class The ancient Egyptians knew how to work with fractions but saw beauty in representing fractions as a sum of distinct unit fractions (fractions whose numerator equals 1). For example, the ancient Egyptians would represent the fraction ¾ as  This can be accomplished by starting with an DoublyLinkedList<BigInteger> consisting of three fours [4, 4, 4] which represents ¼ + ¼ + ¼. Note that it is necessary to store only the denominators. The idea is to remove a duplicate integer x from the DoublyLinkedList and replace it by adding the integers x+1 and x(x+1). [Word of warning: you will have to use the methods add() and multiply() from BigInteger]. Why does this process work? The reason is 1/x = 1/(x+1) + 1/[x(x+1)]. Let’s complete this example. By showing the contents of the DoublyLinkedList after each duplicate is removed. [4, 4, 4] remove 4 add 5 and 20 [4, 4, 5, 20] remove 4 add 5 and 20 [4, 5, 5, 20, 20] remove 5 add 6 and 30 [4, 5, 6, 20, 20, 30] remove 20 add 21 and 420 [4, 5, 6, 20, 21, 30, 420] each entry is distinct The EgyptianFraction class should have instance variables

 private DoublyLinkedList<BigInteger> representation; private BigInteger numerator; private BigInteger denominator; You will need methods to 
 1) detect duplicate items in the DoublyLinkedList
 2) remove a duplicate from the DoublyLinkedList
 3) print the representation of an Egyptian Fraction, as well as, a constructor that initializes the DoublyLinkedList based on the inputted fraction. It should be able to print out horizontally.