Description create a new class called “XLinkedList”. This class defines an inner
ID: 3724534 • Letter: D
Question
Description
create a new class called “XLinkedList”. This class defines an inner (private) class “Node” as the container for the “T obj” data. The main idea is to recode the regular methods of a linked list to recursive ones.
Data and Methods of XLinkedList:
Data: class Node<T>, Node<T> head & int size.
Methods:
Implement ALL methods in List Interface and add the following:
Default constructor: sets all data members to initial values.
Boolean search(T obj): a recursive method that searches the linkedlist for a passed obj and returns a true or a false if the obj was/not found.
double sum(): a recursive method that computes the summation of the linkedlist.
void clear(): a recursive method that clears the entire linkedlist. Do not use the short code: “head = null;”.
void printLeft():a recursive method that prints all objs in the linkedlist left to right.
void printRight():a recursive method that prints all objs in the linkedlist right to left.
Add a new interface “Measurable” with these methods:
public double measure();
Modify the Thing class to implement the Measurable interface in (3) above.
Add a Driver/Demo/Test class to test ALL methods of XLinkedList.
Fill XLinkedList with at least 16 objs.
plese specify each class and each method what does it do with a // and make sure the program works
Explanation / Answer
Please find below the code from JAVA program file XLinkedList.java which consists of the constructors, templates and methods based on the instructions provided.
The code is properly commented to help you better understand what is happening in every part of the code. Hope these will help…
/**
* @Author: Akash Kumar
* @Date: 2018-03-06T21:30:13+05:30
* @Email: contact@akashshivanand.com
* @Filename: XLinkedList.java
* @Last modified by: Akash Kumar
* @Last modified time: 2018-03-06T21:44:01+05:30
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
/**
* XLinkedList.java
*
* @author Akash Kumar
*
* @param <T>
*/
public class XLinkedList<T> implements List<T> {
// size of the list
private int size = 0;
// Node head
private Node<T> head = null;
// Default contructor to set data members to initial values.
public XLinkedList(int size) {
ArrayList<Node<T>> list = new ArrayList<>();
for (int i = 0; i < size; i++) {
list.add(new Node<T>(null, null, null));
}
for (int i = 0; i < size - 1; i++) {
list.get(i).next = list.get(i + 1);
list.get(i + 1).prev = list.get(i);
}
}
// a recursive method that searches the linkedlist for a passed obj and
// returns a true or a false if the obj was/not found
boolean search(T obj) {
if (head == null) {
return false;
}
return search(head, obj);
}
boolean search(Node<T> node, T obj) {
if (node == null) {
return false;
}
if (node.item == obj) {
return true;
} else {
search(node.next, obj);
}
return false;
}
// a recursive method that computes the summation of the linkedlist
double sum() {
return sum(head);
}
double sum(Node<T> node) {
if (node == null) {
return 0;
}
return (double) node.item + sum(node.next);
}
// a recursive method that clears the entire linkedlist - this method comes
// from Interface List
@Override
public void clear() {
clear(head);
}
void clear(Node<T> node) {
if (node != null) {
Node<T> nextNode = node.next;
node = null;
clear(nextNode);
}
}
// a recursive method that prints all objs in the linkedlist left to right
void printLeft() {
Node<T> lastNode = null;
while (head.next != null) {
lastNode = head.next;
}
printLeft(lastNode);
}
void printLeft(Node<T> lastNode) {
if (lastNode == null) {
return;
} else {
printRight(lastNode.prev);
System.out.println(lastNode.item);
}
}
// a recursive method that prints all objs in the linkedlist right to left.
void printRight() {
printRight(head);
}
void printRight(Node<T> firstNode) {
if (firstNode == null) {
return;
} else {
printRight(firstNode.next);
System.out.println(firstNode.item);
}
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
// if head is pointing to null, it means XLinkedList is empty.
return head == null;
}
@SuppressWarnings("unchecked")
@Override
public boolean contains(Object o) {
return search((T) o);
}
@Override
public Iterator<T> iterator() {
// TODO
return new LinkedList<T>().iterator();
}
@Override
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<T> x = head; x != null; x = x.next) {
result[i++] = x.item;
}
return result;
}
@Override
public <T> T[] toArray(T[] a) {
if (a.length < size) {
a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
}
int i = 0;
Object[] result = a;
for (Node<T> x = (Node<T>) head; x != null; x = x.next) {
result[i++] = x.item;
}
if (a.length > size) {
a[size] = null;
}
return a;
}
@Override
public boolean add(T e) {
return this.add(e);
}
@Override
public boolean remove(Object o) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean containsAll(Collection<?> c) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean addAll(Collection<? extends T> c) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean addAll(int index, Collection<? extends T> c) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean removeAll(Collection<?> c) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean retainAll(Collection<?> c) {
// TODO Auto-generated method stub
return false;
}
@Override
public T get(int index) {
// TODO Auto-generated method stub
return null;
}
@Override
public T set(int index, T element) {
return null;
}
@Override
public void add(int index, T element) {
// TODO Auto-generated method stub
}
@Override
public T remove(int index) {
// TODO Auto-generated method stub
return null;
}
@Override
public int indexOf(Object o) {
// TODO Auto-generated method stub
return 0;
}
@Override
public int lastIndexOf(Object o) {
// TODO Auto-generated method stub
return 0;
}
@Override
public ListIterator<T> listIterator() {
// TODO Auto-generated method stub
return null;
}
@Override
public ListIterator<T> listIterator(int index) {
// TODO Auto-generated method stub
return null;
}
@Override
public List<T> subList(int fromIndex, int toIndex) {
// TODO Auto-generated method stub
return null;
}
/**
* Private Inner Class Node
*
* @author Akash Kumar
*
* @param <T>
*/
private static class Node<T> {
T item;
Node<T> next;
Node<T> prev;
Node(Node<T> prev, T element, Node<T> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}Please find below the code from JAVA program file XLinkedList.java which consists of the constructors, templates and methods based on the instructions provided.
The code is properly commented to help you better understand what is happening in every part of the code. Hope these will help…
/**
* @Author: Akash Kumar
* @Date: 2018-03-06T21:30:13+05:30
* @Email: contact@akashshivanand.com
* @Filename: XLinkedList.java
* @Last modified by: Akash Kumar
* @Last modified time: 2018-03-06T21:44:01+05:30
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
/**
* XLinkedList.java
*
* @author Akash Kumar
*
* @param <T>
*/
public class XLinkedList<T> implements List<T> {
// size of the list
private int size = 0;
// Node head
private Node<T> head = null;
// Default contructor to set data members to initial values.
public XLinkedList(int size) {
ArrayList<Node<T>> list = new ArrayList<>();
for (int i = 0; i < size; i++) {
list.add(new Node<T>(null, null, null));
}
for (int i = 0; i < size - 1; i++) {
list.get(i).next = list.get(i + 1);
list.get(i + 1).prev = list.get(i);
}
}
// a recursive method that searches the linkedlist for a passed obj and
// returns a true or a false if the obj was/not found
boolean search(T obj) {
if (head == null) {
return false;
}
return search(head, obj);
}
boolean search(Node<T> node, T obj) {
if (node == null) {
return false;
}
if (node.item == obj) {
return true;
} else {
search(node.next, obj);
}
return false;
}
// a recursive method that computes the summation of the linkedlist
double sum() {
return sum(head);
}
double sum(Node<T> node) {
if (node == null) {
return 0;
}
return (double) node.item + sum(node.next);
}
// a recursive method that clears the entire linkedlist - this method comes
// from Interface List
@Override
public void clear() {
clear(head);
}
void clear(Node<T> node) {
if (node != null) {
Node<T> nextNode = node.next;
node = null;
clear(nextNode);
}
}
// a recursive method that prints all objs in the linkedlist left to right
void printLeft() {
Node<T> lastNode = null;
while (head.next != null) {
lastNode = head.next;
}
printLeft(lastNode);
}
void printLeft(Node<T> lastNode) {
if (lastNode == null) {
return;
} else {
printRight(lastNode.prev);
System.out.println(lastNode.item);
}
}
// a recursive method that prints all objs in the linkedlist right to left.
void printRight() {
printRight(head);
}
void printRight(Node<T> firstNode) {
if (firstNode == null) {
return;
} else {
printRight(firstNode.next);
System.out.println(firstNode.item);
}
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
// if head is pointing to null, it means XLinkedList is empty.
return head == null;
}
@SuppressWarnings("unchecked")
@Override
public boolean contains(Object o) {
return search((T) o);
}
@Override
public Iterator<T> iterator() {
// TODO
return new LinkedList<T>().iterator();
}
@Override
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<T> x = head; x != null; x = x.next) {
result[i++] = x.item;
}
return result;
}
@Override
public <T> T[] toArray(T[] a) {
if (a.length < size) {
a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
}
int i = 0;
Object[] result = a;
for (Node<T> x = (Node<T>) head; x != null; x = x.next) {
result[i++] = x.item;
}
if (a.length > size) {
a[size] = null;
}
return a;
}
@Override
public boolean add(T e) {
return this.add(e);
}
@Override
public boolean remove(Object o) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean containsAll(Collection<?> c) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean addAll(Collection<? extends T> c) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean addAll(int index, Collection<? extends T> c) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean removeAll(Collection<?> c) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean retainAll(Collection<?> c) {
// TODO Auto-generated method stub
return false;
}
@Override
public T get(int index) {
// TODO Auto-generated method stub
return null;
}
@Override
public T set(int index, T element) {
return null;
}
@Override
public void add(int index, T element) {
// TODO Auto-generated method stub
}
@Override
public T remove(int index) {
// TODO Auto-generated method stub
return null;
}
@Override
public int indexOf(Object o) {
// TODO Auto-generated method stub
return 0;
}
@Override
public int lastIndexOf(Object o) {
// TODO Auto-generated method stub
return 0;
}
@Override
public ListIterator<T> listIterator() {
// TODO Auto-generated method stub
return null;
}
@Override
public ListIterator<T> listIterator(int index) {
// TODO Auto-generated method stub
return null;
}
@Override
public List<T> subList(int fromIndex, int toIndex) {
// TODO Auto-generated method stub
return null;
}
/**
* Private Inner Class Node
*
* @author Akash Kumar
*
* @param <T>
*/
private static class Node<T> {
T item;
Node<T> next;
Node<T> prev;
Node(Node<T> prev, T element, Node<T> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}