CS 1332 JAVA HW 2 CIRCULAR SINGLY LINKED LIST. PLEASE HELP!!!!! CORRECT ANSWER G
ID: 3879074 • Letter: C
Question
CS 1332 JAVA HW 2 CIRCULAR SINGLY LINKED LIST. PLEASE HELP!!!!! CORRECT ANSWER GETS A THUMBS UP AND GRATITUDE! ---------------------------------------------------------------------- Circular Singly-Linked List You are to code a circular singly-linked list with a head reference. A linked list is a collection of nodes, each having a data item and a reference pointing to the next node. Since it must be circular, the next reference for the last node in this list will point to the head node. Do not use a phantom node to represent the start or end of your list. A phantom or sentinel node is a node that does not store data held by the list and is used solely to indicate the start or end of a linked list. If your list contains n elements, then it should contain exactly n nodes. Your linked list implementation will implement the LinkedListInterface provided. It will use the default constructor (the one with no parameter) which is automatically provided by Java. Do not write your own constructor. Nodes The linked list consists of nodes. A class LinkedListNode is provided to you. LinkedListNode has setter and getter methods to access and mutate the structure of the nodes. Adding You will implement three add() methods. One will add to the front, one will add to the back, and one will add anywhere in the list. See the interface for more details. Removing Removing, just like adding, can be done from the front, the back, or anywhere in your linked list. In addition, you will also be coding a method to remove the last instance of a piece of data. When removing from the front, the rst node should be removed in such a way that the last node points to the new front of the list (mind the eciency!). When removing from the back, the last node should be removed and have the new last node point to the head. When removing from the middle, the previous node of the removed node should point to the next node of the removed node. Make sure that you set any remaining pointers to the deleted nodes to null since in order for the node to be garbage collected, there cannot be any way to access the node. See the interface for more details. ------------------------------------------------------------------------- /** * This interface describes the expected behavior of the public methods * needed for a circular singly linked list with a head pointer. The required * efficiencies have also been provided. * * DO NOT ALTER THIS FILE!! * * @author CS 1332 TAs * @version 1.0 */ public interface LinkedListInterface<T> { /** * Adds the element to the index specified. * * Adding to indices 0 and {@code size} should be O(1), all other cases are * O(n). * * @param index the requested index for the new element * @param data the data for the new element * @throws java.lang.IndexOutOfBoundsException if index is negative or * index > size * @throws java.lang.IllegalArgumentException if data is null */ void addAtIndex(T data, int index); /** * Adds the element to the front of the list. * * Must be O(1) for all cases. * * @param data the data for the new element * @throws java.lang.IllegalArgumentException if data is null. */ void addToFront(T data); /** * Adds the element to the back of the list. * * Must be O(1) for all cases. * * @param data the data for the new element * @throws java.lang.IllegalArgumentException if data is null. */ void addToBack(T data); /** * Removes and returns the element from the index specified. * * Removing from index 0 should be O(1), all other cases are * O(n). * * @param index the requested index to be removed * @return the data formerly located at index * @throws java.lang.IndexOutOfBoundsException if index is negative or * index >= size */ T removeAtIndex(int index); /** * Removes and returns the element at the front of the list. If the list is * empty, return {@code null}. * * Must be O(1) for all cases. * * @return the data formerly located at the front, null if empty list */ T removeFromFront(); /** * Removes and returns the element at the back of the list. If the list is * empty, return {@code null}. * * Must be O(n) for all cases. * * @return the data formerly located at the back, null if empty list */ T removeFromBack(); /** * Removes the last copy of the given data from the list. * * Must be O(n) for all cases. * * @param data the data to be removed from the list * @return the removed data occurrence from the list itself (not the data * passed in), null if no occurrence * @throws java.lang.IllegalArgumentException if data is null */ T removeLastOccurrence(T data); /** * Returns the element at the specified index. * * Getting index 0 should be O(1), all other cases are O(n). * * @param index the index of the requested element * @return the object stored at index * @throws java.lang.IndexOutOfBoundsException if index < 0 or * index >= size */ T get(int index); /** * Returns an array representation of the linked list. * * Must be O(n) for all cases. * * @return an array of length {@code size} holding all of the objects in * this list in the same order */ Object[] toArray(); /** * Returns a boolean value indicating if the list is empty. * * Must be O(1) for all cases. * * @return true if empty; false otherwise */ boolean isEmpty(); /** * Clears the list of all data. * * Must be O(1) for all cases. */ void clear(); /** * Returns the number of elements in the list. * * Runs in O(1) for all cases. * * @return the size of the list */ int size(); /** * Returns the head node of the linked list. * Normally, you would not do this, but it's necessary for testing purposes. * * DO NOT USE THIS METHOD IN YOUR CODE. * * @return node at the head of the linked list */ LinkedListNode<T> getHead(); }
Explanation / Answer
public class LinkedListNode< T >
{
T data; // data for this node
LinkedListNode< T > nextNode; // reference to the next node in the list
LinkedListNode( T object )
{
this( object, null );
} // end ListNode one-argument constructor
LinkedListNode( T object, LinkedListNode< T > node )
{
data = object;
nextNode = node;
} // end ListNode two-argument constructor
T getData()
{
return data; // return item in this node
} // end method getData
LinkedListNode< T > getNext()
{
return nextNode; // get next node
} // end method getNext
} // end class ListNode< T >
==============================================================
public class CircularLinkedList<T> implements LinkedListInterface<T>{
private LinkedListNode< T > firstNode;
private LinkedListNode< T > lastNode;
private String name; // string like "list" used in printing
public CircularLinkedList()
{
this( "list" );
} // end List no-argument constructor
public CircularLinkedList( String listName )
{
name = listName;
firstNode = lastNode = null;
} // end List one-argument constructor
@Override
public void addAtIndex(T data, int index) {
// TODO Auto-generated method stub
}
@Override
public void addToFront(T data) {
// TODO Auto-generated method stub
if ( isEmpty() ) // firstNode and lastNode refer to same object
firstNode = lastNode = new LinkedListNode< T >( data );
else // firstNode refers to new node
firstNode = new LinkedListNode< T >( data, firstNode );
}
@Override
public void addToBack(T data) {
// TODO Auto-generated method stub
if ( isEmpty() ) // firstNode and lastNode refer to same object
firstNode = lastNode = new LinkedListNode< T >( data );
else // lastNode's nextNode refers to new node
lastNode = lastNode.nextNode = new LinkedListNode< T >( data );
}
@Override
public T removeAtIndex(int index) {
// TODO Auto-generated method stub
LinkedListNode< T > current = firstNode, prev = null;
int i = 0;
while ( current != null && i < index){
prev = current;
current = current.nextNode;
i = i + 1;
}
if(current==null)
return null;
if(prev!=null)
prev.nextNode = current.nextNode;
return current.data;
}
@Override
public T removeFromFront() {
// TODO Auto-generated method stub
if ( isEmpty() ) // throw exception if List is empty
return null;
T removedItem = firstNode.data; // retrieve data being removed
if ( firstNode == lastNode )
firstNode = lastNode = null;
else
firstNode = firstNode.nextNode;
return removedItem; // return removed node data
}
@Override
public T removeFromBack() {
// TODO Auto-generated method stub
if ( isEmpty() ) // throw exception if List is empty
return null;
T removedItem = lastNode.data; // retrieve data being removed
if ( firstNode == lastNode )
firstNode = lastNode = null;
else // locate new last node
{
LinkedListNode< T > current = firstNode;
while ( current.nextNode != lastNode )
current = current.nextNode;
lastNode = current; // current is new lastNode
current.nextNode = null;
} // end else
return removedItem; // return removed node data
}
@Override
public T removeLastOccurrence(T data) {
// TODO Auto-generated method stub
LinkedListNode< T > current = firstNode, prev = null;
int i = 0;
while ( current != null && !current.getData().equals(data)){
prev = current;
current = current.nextNode;
}
if(current==null)
return null;
if(prev!=null)
prev.nextNode = current.nextNode;
return data;
}
@Override
public T get(int index) {
// TODO Auto-generated method stub
LinkedListNode< T > current = firstNode;
int i = 0;
while ( i < index && current != null )
current = current.nextNode;
return current.getData();
}
@Override
public Object[] toArray() {
// TODO Auto-generated method stub
Object obj[] = new Object[size()];
LinkedListNode< T > current = firstNode;
int i = 0;
while ( current != null ){
obj[i] = current.getData();
current = current.nextNode;
i = i + 1;
}
return obj;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return firstNode==null;
}
@Override
public void clear() {
// TODO Auto-generated method stub
firstNode = null;
}
@Override
public int size() {
LinkedListNode< T > current = firstNode;
int i = 0;
while ( current != null ){
current = current.nextNode;
i = i + 1;
}
return i;
}
@Override
public LinkedListNode<T> getHead() {
// TODO Auto-generated method stub
return firstNode;
}
}
==============================================================
Thanks, let me know if there is any concern.
======================TAKE-2 , As per comments =================================
public class CircularLinkedList<T> implements LinkedListInterface<T>{
private LinkedListNode< T > firstNode;
private String name; // string like "list" used in printing
public CircularLinkedList()
{
this( "list" );
} // end List no-argument constructor
public CircularLinkedList( String listName )
{
name = listName;
firstNode = null;
} // end List one-argument constructor
@Override
public void addAtIndex(T data, int index) {
// TODO Auto-generated method stub
}
@Override
public void addToFront(T data) {
// TODO Auto-generated method stub
if ( isEmpty() ) // firstNode and lastNode refer to same object
firstNode = new LinkedListNode< T >( data );
else // firstNode refers to new node
firstNode = new LinkedListNode< T >( data, firstNode );
}
@Override
public void addToBack(T data) {
// TODO Auto-generated method stub
if ( isEmpty() ) // firstNode and lastNode refer to same object
firstNode = new LinkedListNode< T >( data );
else // lastNode's nextNode refers to new node
{
LinkedListNode< T > current = firstNode;
int i = 0;
while ( current.nextNode != null){
current = current.nextNode ;
}
current.nextNode = new LinkedListNode< T >( data );
}
}
@Override
public T removeAtIndex(int index) {
// TODO Auto-generated method stub
LinkedListNode< T > current = firstNode, prev = null;
int i = 0;
while ( current != null && i < index){
prev = current;
current = current.nextNode;
i = i + 1;
}
if(current==null)
return null;
if(prev!=null)
prev.nextNode = current.nextNode;
return current.data;
}
@Override
public T removeFromFront() {
// TODO Auto-generated method stub
if ( isEmpty() ) // throw exception if List is empty
return null;
T removedItem = firstNode.data; // retrieve data being removed
if ( firstNode.nextNode ==null )
firstNode = null;
else
firstNode = firstNode.nextNode;
return removedItem; // return removed node data
}
@Override
public T removeFromBack() {
// TODO Auto-generated method stub
if ( isEmpty() ) // throw exception if List is empty
return null;
LinkedListNode< T > current = firstNode;
if ( firstNode.nextNode == null )
firstNode = null;
else // locate new last node
{
while ( current.nextNode != null )
current = current.nextNode;
current.nextNode = null;
} // end else
return current.getData(); // return removed node data
}
@Override
public T removeLastOccurrence(T data) {
// TODO Auto-generated method stub
LinkedListNode< T > current = firstNode, prev = null;
int i = 0;
while ( current != null && !current.getData().equals(data)){
prev = current;
current = current.nextNode;
}
if(current==null)
return null;
if(prev!=null)
prev.nextNode = current.nextNode;
return data;
}
@Override
public T get(int index) {
// TODO Auto-generated method stub
LinkedListNode< T > current = firstNode;
int i = 0;
while ( i < index && current != null )
current = current.nextNode;
return current.getData();
}
@Override
public Object[] toArray() {
// TODO Auto-generated method stub
Object obj[] = new Object[size()];
LinkedListNode< T > current = firstNode;
int i = 0;
while ( current != null ){
obj[i] = current.getData();
current = current.nextNode;
i = i + 1;
}
return obj;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return firstNode==null;
}
@Override
public void clear() {
// TODO Auto-generated method stub
firstNode = null;
}
@Override
public int size() {
LinkedListNode< T > current = firstNode;
int i = 0;
while ( current != null ){
current = current.nextNode;
i = i + 1;
}
return i;
}
@Override
public LinkedListNode<T> getHead() {
// TODO Auto-generated method stub
return firstNode;
}
}