Authors:
Walter Savitch ,kenrick Mock
Chapter:
Linked Data Structures
Exercise:
Programming Projects
Question:2 | ISBN:9780132830317 | Edition: 5
Question
Although the long data type can store large integers, it cannot store extremely large values such as an integer with 200 digits. Create a HugeNumber class that uses a linked list of digits to represent integers of arbitrary length. The class should have a method to add a new most significant digit to the existing number so that longer and longer numbers can be created. Also add methods to reset the number and to return the value of the huge integer as a String along with appropriate constructor or accessor methods. Write code to test your class.
Note: Use of a doubly linked list will make the next problem easier to implement.
Answer
Program:
// HugeNumber.java
public class HugeNumber
{
private class DoublyNode
{
private int digit;
private DoublyNode previous;
private DoublyNode next;
public DoublyNode()
{
digit = 0;
previous = null;
next = null;
}
public DoublyNode(int newDigit, DoublyNode newPrevious,
DoublyNode newNext)
{
digit = newDigit;
previous = newPrevious;
next = newNext;
}
}
private DoublyNode head;
public HugeNumber()
{
head = null;
}
public void addMostSignificantDigit(int newDigit)
{
DoublyNode newNode = new DoublyNode(newDigit, null, head);
if(head != null)
{
head.previous = newNode;
}
head = newNode;
}
public void reset()
{
head = null;
}
public String getNumber()
{
return this.toString();
}
public int size()
{
int count = 0;
DoublyNode current = head;
while(current != null)
{
count++;
current = current.next;
}
return count;
}
public String toString()
{
String result = "";
DoublyNode current = head;
while(current != null)
{
result = current.digit + result;
current = current.next;
}
return result;
}
}
// HugeNumberDemo.java
public class HugeNumberDemo
{
public static void main(String[] args)
{
HugeNumber number = new HugeNumber();
number.addMostSignificantDigit(9);
number.addMostSignificantDigit(8);
number.addMostSignificantDigit(7);
number.addMostSignificantDigit(6);
number.addMostSignificantDigit(5);
number.addMostSignificantDigit(4);
number.addMostSignificantDigit(3);
number.addMostSignificantDigit(2);
number.addMostSignificantDigit(1);
number.addMostSignificantDigit(0);
number.addMostSignificantDigit(9);
number.addMostSignificantDigit(8);
System.out.println("Number: " + number.getNumber());
}
}
Output:
Number: 987654321098