Question

JAVA coding

The Sorted List ADT

Implement the SortedList class. The SortedList class extends the AbstractList class. Both can be seen here. Your assignment is to implement (recursively) all of the abstract methods of the AbstractList class.

They are:

• insert (recursive)

• iterator

• remove (recursive)

• retrieve

• search (recursive)

You must also implement an Iterator inner class for the SortedList class. You must submit a modified SortedList.java file with your source code.

Do not submit and do not modify the List.java or the AbstractList.java file.

Answer 1

public class SortedList<E extends Comparable<? super E>>

extends AbstractList<E> {

// Mthod to insert the node in the list.

private void insert(Node<E> previous,

Node<E> current,Node<E> node)

{

// check if the correct place to insert the value

// in the list.

if(current == null ||

node.data.compareTo(current.data) < 0)

{

if(previous == null)

{

node.next = head;

head = node;

}

else

{

node.next = previous.next;

previous.next = node;

}

}

// if the correct place is not found then search

// for the next place with recursion.

else

insert(current, current.next, node);

}

// Method to insert the value in the list/.

@Override

public void insert(E value)

{

// crate a temporary node.

Node<E> temp = new Node<E>(value);

insert(null, head, temp);

}

// method to remove the node from the list.

private void remove(Node<E> previous,

Node<E> current, E value)

{

// check if the current node is not or not.

if(current == null)

return;

if(current.data.compareTo(value) == 0)

{

// check if the previous node is null

// the remove the head node

if(previous == null)

head = current.next;

else

previous.next = current.next;

}

else if(current.data.compareTo(value) > 0)

return;

else

remove(current, current.next, value);

}

// method to remove the value from the list.

@Override

public void remove(E value)

{

remove(null, head, value);

}

@Override

public E retrieve(int index)

{

// create a node and assign it as head node.

Node<E> current = head;

for(int position = 0; current != null &&

position < index; position++)

{

current = current.next;

}

if(current == null)

return null;

else

return current.data;

}

// method to search an element i the list.

private boolean search(Node<E> node, E value)

{

// check if the node is having the same

// value or not.

if(node == null)

return false;

// compare the value.

if(node.data.equals(value))

return true;

else

return search(node.next, value);

}

// method to search the value in the list.

@Override

public boolean search(E value)

{

return search(head, value);

}

@Override

public java.util.Iterator<E> iterator() {

return new Iterator();

}

// inner iterator class to iterarte the list.

class Iterator implements java.util.Iterator<E>

{

Node<E> current = head;

// method to check if te lict has any element.

@Override

public boolean hasNext()

{

return current != null;

}

// method to find the next value of teh list.

@Override

public E next()

{

E value = current.data;

current = current.next;

return value;

}

}

}

DriverClass.java:

import java.util.Iterator;

// Create the class.

public class DriverCLass

{

// Method to display the values of the list.

public static void DispalyList(SortedList<Integer>list)

{

System.out.print("Sorted List:");

// use for loop to iterate the list.

for(Iterator<Integer> iterator = list.iterator();

iterator.hasNext(); )

{

System.out.print(" "+iterator.next());

}

System.out.println("\n");

}

// Start the main method of the program.

public static void main(String[] args)

{

// Craete an object of the SortedList class.

SortedList<Integer> values =

new SortedList<Integer>();

// insert the values in teh list.

values.insert(80);

values.insert(20);

values.insert(10);

// Display the list.

DispalyList(values);

// Remove the value from the list.

System.out.println

("Removing the value 10 from the list.");

values.remove(10);

// Display the list.

DispalyList(values);

// inert the value in the list.

System.out.println

("Inserting the value 50 to the list.");

values.insert(50);

System.out.println

("Inserting the value 30 to the list.");

values.insert(30);

// Display the list.

DispalyList(values);

// Retreive the value from the list.

System.out.println("Value at the index 2 is: " +

values.retrieve(2));

System.out.println("Value at the index 10 is: "

+ values.retrieve(10)+"\n");

// Seach the value in the list.

System.out.println("Searching the value 50: "+

values.search(50)+"\n");

// Display.

DispalyList(values);

}

}