Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Complete the coding assignment, in Java language. To construct two circular linked lists that UnsortedList and SortedList. Please make sure to do it in 2

Complete the coding assignment, in Java language.

To construct two circular linked lists that UnsortedList and SortedList. Please make sure to do it in 2 separated codes.

To understand how node references work in the linked lists.

To perform basic operations in the linked list.

I attached all the files as well as the information needed in the assignment below

Please make sure to follow the instruction to finish the code.

** List.java **

import java.util.Iterator; /** * Represents List interface. * * @author * @version * @param  is of any object type. */ public interface List { /** * The method returns the current number of elements in the list. * * @return the current number of elements in the list greater than or equal 0 */ public int getSize(); /** * The method returns whether the list is empty. * * @return true if list is empty, false otherwise. */ public boolean isEmpty(); /** * The method returns whether value is in the list. * * @param value the value is assigned * @return true if value in the list, false otherwise. */ public boolean contains(Type value); /** * The method inserts an element into the list. * * @param value the value is assigned */ public void insert(Type value); /** * The method clears the list. */ public void clear(); /** * The method returns a string representation of list contents. * * @return a string representation of list contents. * @see Object#toString() */ @Override public String toString(); /** * /** * The method removes first element occurrence from the list. * * @param value the value is assigned * @return the removed value */ public Type remove(Type value); /** * The method returns the index of value. * * @param value the value is assigned. * @return the index of value if in the list, -1 otherwise. */ public int getIndex(Type value); /** * The method removes value at the given index. * * @param index the index must be in range of 0 and size * @return the removed value * @throws IndexOutOfBoundsException if index less than 0 or index greater than * or equal size */ public Type removeAtIndex(int index); /** * The method replaces the value at the given index with the given value. * * @param index the index must be in range of 0 and size * @param value the value is assigned * @throws IndexOutOfBoundsException if index less 0 or index greater than size */ public void set(int index, Type value); /** * Returns the value at the given index in the list. * * @param index the index must be in range of 0 and size * @throws IndexOutOfBoundsException if index less than 0 or greater size * @return the value at the given index in the list. */ public Type get(int index); /** * The method returns an iterator for this list. * * @return an iterator for the list. */ public Iterator iterator(); }

** AbstractList.java **

import java.util.Iterator; import java.util.NoSuchElementException; /** * The abstract class provides basic structure of the circular * linked list with the tail and size references * * @author Varik Hoang  * * @param  is any object type */ public abstract class AbstractList implements List { /** * The reference to the last element */ protected ListNode tail; /** * The size of the list */ protected int size; /** * The constructor that initiate the tail and size references */ public AbstractList() { tail = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public int getIndex(final Type value) { if (value == null) throw new NullPointerException("The value could not be null"); if (tail == null) return -1; ListNode current = tail.next; // point to head for (int index = 0; index  current = tail.next; // head node while (current != tail) { builder.append(current.data).append(",").append(" "); current = current.next; } builder.append(tail.data); builder.append("]"); return builder.toString(); } /** * Returns an iterator for this list. * * @return an iterator for the list. */ public Iterator iterator() { return new LinkedIterator(); } /** * Represents a list node. * * @author Building Java Programs 3rd ed. * @param  is of any object type */ protected static class ListNode { /** * Data stored in this node. */ public final Type data; /** * Link to next node in the list. */ public ListNode next; /** * Constructs a node with given data and a null link. * * @param data assigned */ public ListNode(Type data) { this(data, null); } /** * Constructs a node with given data and given link. * * @param data assigned * @param next assigned */ public ListNode(Type data, ListNode next) { this.data = data; this.next = next; } /** * The method returns the generic data type as string */ public String toString() { return this.data.toString(); } } /** * The iterator class for the list. * * @author modified from BuildingJavaPrograms 3rd Edition */ public class LinkedIterator implements Iterator { /** * Location of current value to return. */ private ListNode current; /** * The flag that tells if the first node has been visited. */ private boolean visited; /** * Constructs an iterator for the given list. */ public LinkedIterator() { reset(); } /** * Returns whether there are more list elements. * * @return true if there are more elements left, false otherwise * @see java.util.Iterator#hasNext() */ public boolean hasNext() { if (tail != null) return !(current == tail.next && visited); else return false; } /** * Returns the next element in the iteration. * * @throws NoSuchElementException if no more elements. * @return the next element in the iteration. * @see java.util.Iterator#next() */ public Type next() { if (!hasNext()) { throw new NoSuchElementException(); } Type result = current.data; current = current.next; visited = true; return result; } /** * This method is not supported */ public void remove() { throw new IllegalStateException("This iterator does not support remove operation"); } /** * The method resets back to the beginning. */ public final void reset() { if (tail != null) current = tail.next; visited = false; } } }

** UnsortedList.java **

/** * The class represents for the circular unsorted linked list * @author * @author FIRST_NAME LAST_NAME * @param  the generic data type */ public class UnsortedList extends AbstractList implements List { /** * The constructor for the circular unsorted linked list. */ public UnsortedList() { super(); } @Override public boolean contains(Type value) { return getIndex(value) >= 0; } @Override public void insert(Type value) { // TODO Auto-generated method stub } @Override public void clear() { // TODO Auto-generated method stub } @Override public Type remove(Type value) { // TODO Auto-generated method stub return null; } @Override public Type removeAtIndex(int index) { // TODO Auto-generated method stub return null; } @Override public void set(int index, Type value) { // TODO Auto-generated method stub } @Override public Type get(int index) { // TODO Auto-generated method stub return null; } }

** SortedList.java **

/** * The class represents for the circular sorted linked list * @author * @author FIRST_NAME LAST_NAME * @param  the generic data type */ public class SortedList> extends AbstractList implements List { /** * The constructor for the circular sorted linked list. */ public SortedList() { super(); } @Override public boolean contains(Type value) { return getIndex(value) >= 0; } @Override public void insert(Type value) { // TODO Auto-generated method stub } @Override public void clear() { // TODO Auto-generated method stub } @Override public Type remove(Type value) { // TODO Auto-generated method stub return null; } @Override public Type removeAtIndex(int index) { // TODO Auto-generated method stub return null; } @Override public void set(int index, Type value) { throw new UnsupportedOperationException("The SortedList does not support set method"); } @Override public Type get(int index) { // TODO Auto-generated method stub return null; } }

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

Thank you.

Linked List is a sequence of links which contains items. Each node consists of its own data and the address of the next node and forms a chain. The purpose of this assignment is to get familiar with the linked list structure along with generic data type. In this assignment, you will involve constructing Java functions that use linked nodes and list references to operate the elements in the list. Objectives: This assignment will assess your mastery of the following objectives: - To construct two circular linked lists that are unsorted and sort. - To understand how node references work in the linked lists. - To perform basic operations in the linked list. Rules and Explanations: The original linked list has a reference to the first element (head) of the list. In this assignment, you are ask to construct a circular linked list that has a reference to the last element (tail) of the list. To maintain the concept of circular, we do not want the last element points to nowhere, and because of that reason, we will have the last element (tail) points back to the first element (head). The list structure must maintain the reference to the last element of the list after every single operation called. The only case we have a list node null when the list is empty, the tail reference is pointing to null. The last element (tail) must be linked to the first element (head) of the list. There is an interface called List that has a single generic data type "Type". The List provides prototypes as following: \begin{tabular}{|l|l|} \hline Method & Description \\ \hline public int getSize() & The method returns the number of elements in the list. \\ \hline public boolean isEmpty() & The method returns true if the list is empty. otherwise false. \\ \hline public boolean contains(Type value) & The method returns true if the list contains the given value otherwise false. \\ \hline public void insert(Type value) & The method insert the given value into the list. \\ \hline public void clear() & The method removes all elements from the list. \\ \hline public String tostring() & The method returns the list in string format. For example: "[1, 2, 3, 4]" \\ \hline public Type value remove(Type value) & The method removes and returns the given value from the list. \\ \hline public int getindex(Type value) & The method returns the index of the given value. (return -1 if the value is not found) \\ \hline public Type removeAtlndex(int index) & The method removes and returns the value at the given index.. \\ \hline public void set(int index, Type value) & The method assigns the given value to the list at the given index. \\ \hline public Type get(int index) & The method returns the value of the element at the given index. \\ \hline public Iterator iterator () & The method returns the iterator of the list. \\ \hline \end{tabular} Note: the program should throw java.lang.IndexOutOfBoundsException if the given index is invalid. The AbstractList is also provided with some methods already implemented from the List: getSize, isEmpty, getlndex, toString, and iterator. That means the List.java and AbstractList.java files should remain unmodified. You will need to implement two different circular linked lists: 1. UnsortedList: the circular unsorted linked list, we extends this concrete class from the AbstractList class and implement all prototypes from the interface List 2. SortedList: the circular sorted linked list, we extends this concrete class from the AbstractList class and implement all prototypes from the interface List. We must find the right spot to place the new element in the list. That means the list always remains sorted in ascending order. The generic data type for this list must be comparable. Note: some IDEs (Eclipse, IntelliJ, Netbeans, etc.) automatically import the built-in Java List interface and AbstractList class which refer to wrong required implementations for both UnsortedList and SortedList The program does not compile will receive grade of zero. Place your code in a class named UnsortedList, SortedList, and optionally AbstractShape, Triangle, Rectangle, Square, and Circle. - There is no need for a main method in this assignment but feel free to create another Test class to test your UnsortedList and SortedList. Please DO NOT add any extra method or field for those two classes. 1. For the class UnsortedList: a. Implement the method insert to add an item and always put it in the back of the list. If the item's value is null then the program should throw NullPointerException. b. Implement the method remove to find the item in the list. If the item is found, we remove it from the list and return that item (we do not want to lose the connection of the item removed). If the item is not found, simply return null. If the item's value is null then the program should throw NullPointerException. c. Implement the method removeAtindex to remove the item at the given index. We remove the item from the list and return that item (we do not want to lose the connection of the item removed). If the index is negative or out of bound then the program should throw IndexOutOfBoundsException. d. Implement the method get to get the item at the given index by returning the value. If the index is negative or out of bound then the program should throw IndexOutOfBoundsException. e. Implement the method set to set the item at the given index. If the index is negative or out of bound then the program should throw IndexOutOfBoundsException. If the value of the item is null then the program should throw NullPointerException. f. Implement the method contains to check if the item is in the list. The method returns true if the item is in the list otherwise false. If the value of the item is null then the program should throw NullPointerException. g. Implement the method clear to clear/empty the list. 2. For the class SortedList. We implement all methods insert, remove, removeAtindex, get, contains, and clear same as UnsortedList but except the set method. We do not want to mess up the order of the list. - Be sure your code follows the naming and coding conventions for the class: 1. Instance fields of a class should be named starting with 'my' 2. Parameters to methods should be named starting with 'the' 3. Parameters to methods should be specified as final 4. Javadoc comments should be used for the class as well as the methods of the class 5. You will lose points for each of these things on every assignment if you do not adhere to the rules. 6. See this document for specifics (as well as an example): https://www.oracle.com/java/technologies/javase/codeconventionsintroduction.html Download: - List.java (do not modify the content of this file) - AbstractList.java (do not modify the content of this file) - UnsortedList.java (follow the TODO tags to implement methods) - SortedList.java (follow the TODO tags to implement methods) - readme.txt (example) Rubric: \begin{tabular}{|l|l|l|} \hline Points & Categories & Comments \\ \hline & Functionality & Compiled source code with error(s) will receive a grade of zero \\ \hline & Functionality & Compiled source code with no error and no infinite run. \\ \hline 10 & Functionality & The class UnsortedList had method insert worked correctly. \\ \hline 12 & Functionality & The class UnsortedList had method remove and removeAtlndex worked correctly. \\ \hline 10 & Functionality & The class UnsortedList had method get and set worked correctly. \\ \hline 5 & Functionality & The class UnsortedList had method contains worked correctly. \\ \hline 3 & Functionality & The class UnsortedList had method clear worked correctly. \\ \hline 20 & Functionality & The class SortedList had method insert worked correctly. \\ \hline 20 & Functionality & The class SortedList had method remove and removeAtindex worked correctly. \\ \hline 5 & Functionality & The class SortedList had method get worked correctly. \\ \hline 5 & Functionality & The class SortedList had method contains worked correctly. \\ \hline 3 & Functionality & The class SortedList had method clear worked correctly. \\ \hline 5 & Miscellaneous & Compressed files as expected \\ \hline 2 & Miscellaneous & Used spacing, indentation appropriately and consistently \\ \hline 100 & & \\ \hline \end{tabular} Note: must pass all criterias if using LGS

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Students also viewed these Databases questions

Question

=+7. How have the media helped you in the last three years?

Answered: 1 week ago

Question

6. Explain the power of labels.

Answered: 1 week ago

Question

10. Discuss the complexities of language policies.

Answered: 1 week ago