Question: Implement the method int count(E fromElement, E toElement) for the class SinglyLinkedList presented in class. The method returns the number of elements in the list
Implement the method int count(E fromElement, E toElement) for the class SinglyLinkedList presented in class. The method returns the number of elements in the list between the first instance of fromElement and the first instance of toElement in the list, including fromElement and toElement. We have the following constraints and specifications for our methods:
The implementation of count must be recursive. No mark will be given for an iterative implementation.
If fromElement cannot be found in the list, the method returns 0.
If toElement cannot be found in the list after fromElement, the method returns the number of elements in the list between the first instance of fromElement and the end of the list, fromElement included.
The method should be efficient and not visit nodes it doesn't need to visit.
---------------------------------------------------------------------------------------------
import java.util.*;
public class SinglyLinkedList implements List, Iterable {
public int count(E fromElement, E toElement) {
//missing code
}
private int count(Node current, E fromElement, E toElement){
//missing code
}
private static class Node {
private T value;
private Node next;
private Node(T value, Node next ) {
this.value = value;
this.next = next;
}
}
private class LinkedListIterator implements Iterator {
private Node currentIterator;
public LinkedListIterator() {
currentIterator = null;
}
public E next() {
if(currentIterator == null) {
currentIterator = head;
} else {
currentIterator = currentIterator.next;
}
if(currentIterator == null)
throw new NoSuchElementException("Iterator at the end or list empty");
return currentIterator.value;
}
public boolean hasNext(){
if(currentIterator == null)
return !isEmpty();
else
return (currentIterator.next != null);
}
public void remove(){
throw new UnsupportedOperationException();
}
}
public Iterator iterator(){
return new LinkedListIterator();
}
private Node head;
private int size;
private Node tail;
public SinglyLinkedList() {
head = tail = null;
size = 0;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void addFirst(E o) {
if(o == null) {
throw new NullPointerException("Can't add null reference to the list");
}
Node newNode = new Node( o, null );
if ( head == null ) {
head = newNode;
tail = head;
} else {
newNode.next = head;
head = newNode;
}
size++;
}
public void add( E o ) {
if(o == null) {
throw new NullPointerException("Can't add null reference to the list");
}
Node newNode = new Node( o, null );
if ( head == null ) {
head = newNode;
tail = head;
} else {
tail.next = newNode;
tail = newNode;
}
size++;
}
public void add( int pos, E o) {
if(o == null) {
throw new NullPointerException("Can't add null reference to the list");
}
if ( pos < 0 || pos > size) {
throw new IndexOutOfBoundsException( Integer.toString( pos ) );
}
if(pos == 0){
addFirst( o );
} else if(pos == size){
add( o );
} else {
Node current = head;
for(int i = 0; i < pos - 1; i++) {
current = current.next;
}
current.next = new Node( o, current.next );
size++;
}
}
public E removeFirst() {
if(isEmpty())
throw new IllegalStateException("Empty list!");
E savedValue = head.value;
size--;
if(size > 0){
head = head.next;
} else {
head = tail = null;
}
return savedValue;
}
public E removeLast() {
if(isEmpty())
throw new IllegalStateException("Empty list!");
E savedValue= tail.value;
if ( head.next == null ) {
head = tail = null;
} else {
Node current = head;
while ( current.next != tail ) {
current = current.next;
}
tail = current;
tail.next = null;
}
size--;
return savedValue;
}
public boolean remove( E o ) {
if ( head == null )
return false;
if ( head.value.equals( o ) ) {
removeFirst();
return true;
} else {
Node current = head;
while ( current.next != null && ! current.next.value.equals( o ) ) {
current = current.next;
}
if ( current.next == null ) {
return false;
} else {
current.next = current.next.next;
if(current.next == null) {
tail = current;
}
size--;
return true;
}
}
}
public E get( int pos ) {
if(isEmpty())
throw new IllegalStateException("Empty list!");
if ( pos < 0 || pos >= size) {
throw new IndexOutOfBoundsException( Integer.toString( pos ) );
}
Node current = head;
for ( int i=0; i
current = current.next;
}
return current.value;
}
public E remove( int pos ) {
if(isEmpty())
throw new IllegalStateException("Empty list!");
if ( pos < 0 || pos >= size ) {
throw new IndexOutOfBoundsException( Integer.toString( pos ) );
}
Node toBeRemoved;
if ( pos == 0 ) {
return removeFirst();
} else if (pos == size-1) {
return removeLast();
}
else {
Node current = head;
for ( int i=0; i<( pos-1); i++ ) {
current = current.next;
}
toBeRemoved = current.next;
current.next = current.next.next;
}
size--;
return toBeRemoved.value;
}
public boolean equals(SinglyLinkedList otherList){
if((otherList == null) || (size != otherList.size()))
return false;
Node thisCursor = head;
Node otherCursor = otherList.head;
for(int i = 0; i < size; i++){
if(!thisCursor.value.equals(otherCursor.value))
return false;
thisCursor = thisCursor.next;
otherCursor = otherCursor.next;
}
return true;
}
public String toString(){
StringBuffer res = new StringBuffer();
res.append("[");
if(!isEmpty()){
Node cursor = head;
res.append(cursor.value);
while(cursor.next != null){
cursor = cursor.next;
res.append(" " + cursor.value);
}
}
res.append("]");
return res.toString();
}
}
Step by Step Solution
There are 3 Steps involved in it
Heres the implementation of the count method in the SinglyLinkedList class using recursion public in... View full answer
Get step-by-step solutions from verified subject matter experts
Study Help