Question
I am working on a Linked List Set class that needs to adhere to the following regulations. And I need help. Do not change any
I am working on a Linked List Set class that needs to adhere to the following regulations. And I need help.
Do not change any files I provide. These files should remain as is, and you are not to add any extra methods/variables or other things to them.
Create a new class that extends the LinkedList class and overrides the insert method. Make sure your insert method correctly implements the behavior of a set when an item is inserted. Meaning, only allow one of each item in your set.
Add the union, intersect and different methods to this new class. These 3 methods should be static, take 2 LinkedListSets, and return a new LinkedListSet formed according to the method name.
These methods are only considered to be implemented correctly if you either properly use iterators to walk the linked lists, or use your own code to walk the LinkedLists. Changing the LinkedList into other data types, like arrays, performing the operation, and then changing them back into LinkedList doesn't count as being correct.
public class LinkedList
{
/**
* Construct the list
*/
public LinkedList( )
{
header = new ListNode( null );
}
/**
* Test if the list is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return header.next == null;
}
/**
* Make the list logically empty.
*/
public void makeEmpty( )
{
header.next = null;
}
/**
* Return an iterator representing the header node.
*/
public LinkedListIterator zeroth( )
{
return new LinkedListIterator( header );
}
/**
* Return an iterator representing the first node in the list.
* This operation is valid for empty lists.
*/
public LinkedListIterator first( )
{
return new LinkedListIterator( header.next );
}
/**
* Insert after p.
* @param x the item to insert.
* @param p the position prior to the newly inserted item.
*/
public void insert( AnyType x, LinkedListIterator p )
{
if( p != null && p.current != null )
p.current.next = new ListNode( x, p.current.next );
}
/**
* Return iterator corresponding to the first node containing an item.
* @param x the item to search for.
* @return an iterator; iterator is not valid if item is not found.
*/
public LinkedListIterator find( AnyType x )
{
ListNode itr = header.next;
while( itr != null && !itr.element.equals( x ) )
itr = itr.next;
return new LinkedListIterator( itr );
}
/**
* Return iterator prior to the first node containing an item.
* @param x the item to search for.
* @return appropriate iterator if the item is found. Otherwise, the
* iterator corresponding to the last element in the list is returned.
*/
public LinkedListIterator findPrevious( AnyType x )
{
ListNode itr = header;
while( itr.next != null && !itr.next.element.equals( x ) )
itr = itr.next;
return new LinkedListIterator( itr );
}
/**
* Remove the first occurrence of an item.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
LinkedListIterator p = findPrevious( x );
if( p.current.next != null )
p.current.next = p.current.next.next; // Bypass deleted node
}
// Simple print method
public static void printList( LinkedList theList )
{
if( theList.isEmpty( ) )
System.out.print( "Empty list" );
else
{
LinkedListIterator itr = theList.first( );
for( ; itr.isValid( ); itr.advance( ) )
System.out.print( itr.retrieve( ) + " " );
}
System.out.println( );
}
private ListNode header;
// In this routine, LinkedList and LinkedListIterator are the
// classes written in Section 17.2.
public static int listSize( LinkedList theList )
{
LinkedListIterator itr;
int size = 0;
for( itr = theList.first(); itr.isValid(); itr.advance() )
size++;
return size;
}
public static void main( String [ ] args )
{
LinkedList theList = new LinkedList( );
LinkedListIterator theItr;
int i;
theItr = theList.zeroth( );
printList( theList );
for( i = 0; i < 10; i++ )
{
theList.insert( i , theItr );
printList( theList );
theItr.advance( );
}
System.out.println( "Size was: " + listSize( theList ) );
for( i = 0; i < 10; i += 2 )
theList.remove( i );
for( i = 0; i < 10; i++ )
if( ( i % 2 == 0 ) == ( theList.find( i ).isValid( ) ) )
System.out.println( "Find fails!" );
System.out.println( "Finished deletions" );
printList( theList );
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
include include using namespace std void swap int 1 int r int temp 1 1 r r temp This function takes ...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