Question
This assignment requires you to implement a set collection using a doubly-linked list as the underlying data structure. You are provided with the Set interface
This assignment requires you to implement a set collection using a doubly-linked list as the underlying data structure. You are provided with the Set interface and a shell of the LinkedSet implementing class. You must not change anything in the Set interface, but you must create correct implementations of the methods in the LinkedSet class. In doing so you are allowed to add any number of private methods and nested classes that you need, but you may not create or use any other top-level class and you may not create any public method. You must also use without modification the existing fields of the LinkedSet class. The Set interface is generic and makes no restrictions on the type that it can contain. The LinkedSet class is also generic, but it does make a restriction on the type variableany type bound by a client to T must be a class that implements the Comparable interface for that type. Thus, there is a natural order on the values stored in an LinkedSet, but not (necessarily) on those stored in a Set. This is an important distinction, so pause here long enough to make sure you understand this point. The following sections describe each method to be implemented, organized according to the methods appearing in the Set interface and those specific to the LinkedSet class. Methods of the Set Interface Each method from the Set interface that you must implement in the LinkedSet class is described below and in comments in the provided source code. You must read both. Note that in addition to correctness, your code will also be graded on the stated performance requirements.
add(T element) The add method ensures that this set contains the specified element. Neither duplicates1 nor null values are allowed. The method returns true if this set was modified (i.e., the element was added) and false otherwise. Note that the constraint on the generic type parameter T of the LinkedSet class ensures that there is a natural order on the values stored in an LinkedSet. You must maintain the internal doubly-linked list in ascending natural order at all times. The time complexity of the add method must be O(N), where N is the number of elements in the set.
public boolean add(T element) {
if(element==null)
throw new NullPointerException();
//CHECK FOR DUPLICATES
if(contains(element))
return false;
//ADD AS FIRST NODE IF LINKEDSET IS EMPTY
if(size==0)
{
front=new Node(element);
rear=front;
}
//ADD TO TEND OF THE LINKEDSET
else
{
rear.next=new Node(element);
rear.next.prev=rear;
rear=rear.next;
}
size++;
return true;
}
When you execute it does not compile in the correct natural oder.
How would modify the code to have the correct (ascending) natural order
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started