Question: Please use the doubly linked list you developed (DLList.java). Let me know if you do not have one and I will provide one for you.
Please use the doubly linked list you developed (DLList.java). Let me know if you do not have one and I will provide one for you. As you conceptualize the program, you will see why a doubly linked list is used.
The Program:
Write a new class called InfiniteInt. We can (theoretically) store an infinite integer by linking together nodes that hold actual complete integers. So it will look like this:
head tail
For this program, just store 3 digits in each node (concept is the same, but we wont have to generate hundreds of digits to test it). For example, the integer 487,021,639 will be stored like this:
head tail
have to have a compareTo (see requirements below), your InfiniteInt should be defined as:
public class InfiniteInt extends DLList
Since your InfiniteInt is a subclass of DLList, it will inherit DLLists methods, but you will also have to implement the following methods/constructors:
A default constructor that takes no arguments and just builds a null linked list (it could call its super() which just sets head and tail to null).
A constructor that receives a String as an argument and builds the linked list. If an InfiniteInt is created as follows:
InfiniteInt myList = new InfiniteInt(487,021,639); then the list should be built as shown above.
This constructor should also check for illegal Strings (containing a non-digit). If encountered, throw an IllegalArgumentException(
Note that you can build the list by using the methods already available from the superclass.
An equals method that receives another Object and returns true if it is equal to this InfiniteInt. It is considered equal if the numbers themselves are exactly the same. You will have to start with the same exact logic that we have used in previous implementations of .equals. The actual part to determine equality will be very easy (think about it and what you have to work with).
A toString() method that will override the one in the superclass. If the InfiniteInt is empty, your toString() method should
throw new IllegalStateException(
Otherwise, it returns the String representation of the InfiniteInt with commas and leading 0s inserted correctly. You cannot count on the original String representation being available (the InfiniteInt could have been generated using the add method below) so you have to go through the nodes and determine what to print. Note that the following InfiniteInts toString() should return 600,050,004.
head tail
A method called isEven() which returns true if the InfiniteInt is an even number. First check to see if it is empty; if so, the isEven() method should:
throw new IllegalStateException(
A method called isDivisibleBy10() which returns true if the InfiniteInt is evenly divisible by 10. First check to see if it is empty; if so, the isDivisibleBy10() method should:
throw new IllegalStateException(
A method called isDivisibleBy1000() which returns true if the InfiniteInt is evenly divisible by 1000. First check to see if it is empty; if so, the isEven() method should:
throw new IllegalStateException(
A compareTo(InfiniteInt o) that will implement the Comparable interface (please actually put
implements Comparable
InfiniteInt int1 = new InfiniteInt("24"); InfiniteInt int2 = new InfiniteInt("6"); InfiniteInt int3 = new InfiniteInt(24);
System.out.println(int1.compareTo(int2)); //should print a positive (Java) int
System.out.println(int2.compareTo(int1)); //should print a negative (Java) int
System.out.println(int1.compareTo(int1)); //should print 0
System.out.println(int1.compareTo(int3)); //should print 0
A static add method which will receive 2 InfiniteInts as arguments, add them up, and return a new InfiniteInt with the total in it. If you think about this and try a few examples on paper, you will see how to do it you must traverse each number backwards (using the prev link in the doubly linked list) and add each digit, carrying to the next place when necessary. Make sure that you carry correctly and handle the case when one list is longer than the other. This code should work in a driver program:
InfiniteInt int1 = new InfiniteInt("646,746,734");
InfiniteInt int2 = new InfiniteInt("543,534");
InfiniteInt int3;
int3 = InfiniteInt.add(int1, int2);
System.out.println(int3); //should print 647,290,268
-----------------------------------------------------------------------------------------------------------------------
import java.util.*;
public class DLList
{
//-------- data
private DLLNode
private DLLNode
//-------- constructors
public DLList()
{
head = null;
tail = null;
}
//-------- methods
public String toString()
{
DLLNode
String str = "";
while(cursor != null)
{
if (str.isEmpty())
str = str + cursor.data;
else
str = str + ", " + cursor.data;
cursor = cursor.next;
}
return "[" + str + "]";
}
//backwards - this will traverse the list like toString, only "backwards".
public String backwards()
{
DLLNode
String str = "";
while(cursor != null)
{
if (str.isEmpty())
str = str + cursor.data;
else
str = str + ", " + cursor.data;
cursor = cursor.prev; //traveres backward by using prev
}
return "[" + str + "]";
}
//addLast - adds a new DLLNode to the end of the list
public void addLast(E theData)
{
//create the new DLLNode
DLLNode
//Case1: the list was empty (head was null). Change links
if (head == null)
{
head = tail = aNode;
}
//Case2 and 3: list has 1 or more elements. Change links
else
{
tail.next = aNode;
aNode.prev = tail;
tail = aNode;
}
}
//isEmpty - returns true if the list is empty
public boolean isEmpty()
{
return head == null;
}
//------------------------------------------------------
//addFirst - adds to the front of the list
public void addFirst(E someData)
{
//create a new DLLNode
DLLNode
//Case1: is list empty?
if (head== null)
head = tail = aNode;
//Case2,3: is has >=1 element already
else
{
aNode.next = head;
head.prev = aNode;
head = aNode;
}
}
//getFirst - returns the element at the front of the list, without deleting
public E getFirst()
{
//case1: empty list
if (head == null)
throw new NoSuchElementException("can't getFirst from empty list");
//case 2,3: list has 1 or more elements - return data that head points at
return head.data;
}
//getLast - returns the element at the end of the list, without deleting
public E getLast()
{
//case1: empty list
if (head == null)
throw new NoSuchElementException("can't getLast from empty list");
//case 2,3: list has 1 or more elements - return data that tail points at
return tail.data;
}
//removeFirst - returns the element at the front of the list and deletes it
public E removeFirst()
{
//case1: list is empty
if (head == null)
throw new NoSuchElementException("can't removeFirst from empty list");
//case2: 1 element on the list
else if (head == tail)
{
E savedData = head.data; //save the data
head = tail = null;
return savedData;
}
//case3: many elements on list
else
{
E savedData = head.data;
head = head.next;
head.prev = null;
return savedData;
}
}
//removeLast - returns the element at the end of the list and deletes it
public E removeLast()
{
//case1: list is empty
if (head == null)
throw new NoSuchElementException("can't removeLast from empty list");
//case2: list has 1 element
else if (head == tail)
{
return removeFirst(); //or could have same 3 statements as removeFirst does
}
//case3: list has many elements
else
{
//we need a cursor to traverse the list, stopping at the node IN FRONT of the tail
DLLNode
//traverse
while (cursor.next != tail)
cursor = cursor.next;
//save the last data so we can return it
E savedData = tail.data;
/ow that cursor points at the second to last node, change the links
//cursor.next = null;
//tail = cursor;
tail = tail.prev;
tail.next = null;
//return it
return savedData;
}
}
//size - returns the number of elements in the list
public int size()
{
/eeds a counter
int count = 0;
//declare a cursor that will "walk" through the list
DLLNode
//as long as ("while") cursor is not null, count it
while(cursor != null)
{
count++;
cursor = cursor.next; //move to the next node...
}
return count;
}
//contains - returns true if the list contains what is received, false otherwise
public boolean contains(E elt)
{
//create a cursor so we can "walk" through the list
DLLNode
//walk through the whole list (maybe)
while (cursor != null)
{
if (cursor.data.equals(elt)) //found it!
return true;
cursor = cursor.next;
}
//if we get all the way through the list, we did not find it
return false;
}
//add - adds a new element at the given index.
// throws IllegalArgumentException if the index is out of bounds
public void add(int index, E elt)
{
//check to see if the index is out of bounds
if (index size())
throw new IllegalArgumentException("index " + index + " is out of bounds");
//create a new node that holds elt
DLLNode
//case1: list is empty
if (head == null)
head = tail = aNode;
//case2,3: here, index is 0 so putting it at the front
else if (index == 0)
addFirst(elt); //creates a new node and puts it at front
//index is same as size() so putting it at the end
else if (index == size())
addLast(elt);
//if we get to here, we know that it is going onto the list at a
//legal index and not at the front or the back
else
{
//find the node in front of where it goes...
DLLNode
for (int i=0; i cursor = cursor.next; //draw it out!!! /ow cursor is at the node in front of where it goes //change the links aNode.next = cursor.next; aNode.prev = cursor; cursor.next.prev = aNode; cursor.next = aNode; } } //remove - removes and returns the first occurrance of an element. // returns true if successful, false otherwise public boolean remove(E elt) { //case1: list is empty if (head == null) return false; //case2: list has 1 element - one element to check else if (head == tail) { if (head.data.equals(elt)) { removeFirst(); return true; } else return false; } //case3: list has many elements else { //check to see if the list even contains it... if (!contains(elt)) return false; //if we get to here, we know the list contains it //check to see if it is the first element... else if (head.data.equals(elt)) { removeFirst(); return true; } //if we get to here, we know the list contains it //and it is not the first element //so we can find the node in front of it (since not first) else { DLLNode //move cursor, stopping at the node in front of one to be removed while(!cursor.next.data.equals(elt)) cursor = cursor.next; //cursor should have stopped at the node before the one to be removed //if the node to be removed was the last one... if (cursor.next == tail) removeLast(); //otherwise, make the link go around it else cursor.next = cursor.next.next; cursor.next.prev = cursor; return true; } } } } //================================= //This class will implement a node in our doubly linked list class DLLNode { //data protected E data; protected DLLNode protected DLLNode //constructors public DLLNode(E theData) { data = theData; next = null; prev = null; } //methods //toString - returns its representation as a String public String toString() { return "" + data; } } 
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help