Scribd
Upload
4 views

LinkedListLabReport

The document is a lab report detailing the implementation of a singly linked list to manage very large integers in C++. It describes the program's functionality, including adding, removing, and peeking at digits, as well as handling the sign of the number. The report also discusses implementation challenges, known bugs, and lessons learned during the process.

Uploaded by

e.song200
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views

LinkedListLabReport

The document is a lab report detailing the implementation of a singly linked list to manage very large integers in C++. It describes the program's functionality, including adding, removing, and peeking at digits, as well as handling the sign of the number. The report also discusses implementation challenges, known bugs, and lessons learned during the process.

Uploaded by

e.song200
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

Ethan Song

Gentry-Kolen

COMSC-210

9 February 2020

Linked List Lab Report

Problem: Identify a problem that can efficiently be solved with linked lists and

Implement a singularly linked list within the solution to the problem.

Discussion:

Solution/Program Description: This program uses a singly linked list to store very large

integers that may be larger than what the primitive data types of C++ can normally

handle. It has functions to add and remove digits, as well as functions to peek at digits,

and finally, a Boolean that determines the sign of the number.

Pseudocode:

using namespace std;


template <class T>
class LinkedList {
protected:
ListNode Structure{
Value
ListNode *next;
ListNode(T value1, ListNode *next1 = NULL){
value = value1;
next = next1;
}
};
public:
ListNode *head;
ListNode *tail;
int size;
LinkedList(){
head = NULL;
tail = NULL;
size = 0;
}
void add(T value){
if(head == NULL || value < head->value)
addFirst(value);
else if(value >tail->value)
addLast(value);
else{
ListNode *temp = head;
ListNode *prev;
while(temp->value < value){
prev = temp;
temp = temp->next;
}
if(value < temp->value){
prev->next = new ListNode(value);
prev->next->next = temp;
}

}
size++;
}

void addFirst(T value){


if(head == NULL){
head = new ListNode(value);
tail = head;
}else{
ListNode *temp;
temp = new ListNode(value);
temp->next = head;
head = temp;
}
size++;
}
void addLast(T value){
if(head == NULL){
head = new ListNode(value);
tail = head;
}else{
tail->next = new ListNode(value);
tail = tail->next;
}
size++;
}
T peekFirst(){
if(head == NULL)
return -1;
else
return head->value;
}
T peekLast(){
if(tail==NULL)
return -1;
else
return tail->value;
}
void remove(T value){
if(head == NULL)
cout << "Error. Empty List" << endl;
ListNode *temp, *prev;
if(head->value == value){
temp = head;
head = head->next;
delete temp;
size--;
}else{
temp = head;
while(temp != NULL && temp->value != value){
prev = temp;
temp = temp->next;
}
if(temp){
prev->next = temp->next;
delete temp;
cout << "Element removed" << endl;
}else{
cout << "Error. Number not found" << endl;
}
size--;
}
}
T removeFirst(){
T returnValue = NULL;
if(size==0)
return false;
returnValue = head->value;
head = head->next;
size--;
return returnValue;
}
T removeLast(){
T returnValue = NULL;
if(tail==NULL)
return returnValue;
else if(size==1)
return removeFirst();
else{
ListNode *temp = head;
for(int i = 1; i<size-1; i++)
temp = temp->next;
temp->next = NULL;
tail = temp;
}
size--;
return returnValue;
}
bool search(T value){
if(head == NULL)
return false;
ListNode *temp;
int counter = 0;
if(head->value == value)
return true;
else{
temp = head;
while(temp != NULL && temp->value != value){
temp = temp->next;
counter++;
}
if(temp)
return true;
else
return false;
}
}

int getSize(){
return size;
}

void displayList() const{


ListNode *temp = head;
while(temp){
cout <<temp->value;
temp = temp->next;
}
cout << endl;
}

};

class BigNumber {
private:
LinkedList<int> bigNumberList;
bool isNegative;
public:
BigNumber(){
isNegative = false;
}
void addDigit(int n){
bigNumberList.addLast(n);
}
int peekLastDigit(){
return bigNumberList.peekLast();
}
int peekFirstDigit(){
return bigNumberList.peekFirst();
}
int removeLastDigit(){
return bigNumberList.removeLast();
}
int removeFirstDigit(){
return bigNumberList.removeFirst();
}
int getSize(){
return bigNumberList.getSize();
}
void display(){
if(isNegative){
cout << "-";
bigNumberList.displayList();
}else
bigNumberList.displayList();
}
int getNumSize(){
return bigNumberList.getSize();
}
void setNegative(){
isNegative = true;
}
void setPositive(){
isNegative = false;
}
bool getSign(){
return isNegative;
}
};

int main(int argc, const char * argv[]) {


string bigNumStr = "";
BigNumber bigNum;
cout << "Enter a large number: ";
cin >>bigNumStr;
if(bigNumStr.substr(0,1).compare("-")==0){
for(int i=1; i<bigNumStr.length(); i++)
bigNum.addDigit(stoi(bigNumStr.substr(i,1)));
bigNum.setNegative();
}else{
for(int i=0; i<bigNumStr.length(); i++)
bigNum.addDigit(stoi(bigNumStr.substr(i,1)));
bigNum.setPositive();
}
cout << endl << "Big Number: ";
bigNum.display();
cout << endl;
cout << "First Digit: " << bigNum.peekFirstDigit() << endl;
cout << "Last Digit: " << bigNum.peekLastDigit() << endl;
cout << "Size of bigNumber: " << bigNum.getSize() << endl;

bigNum.removeFirstDigit();

cout << "After removing first digit: ";


bigNum.display();

bigNum.removeLastDigit();
cout << endl << "After removing last digit: ";
bigNum.display();

return 0;
}
Major Implementation Issues: The biggest difficulty in implementing this program was

the linked list. More specifically, the remove methods were especially hard since they

involved a deeper understanding of how pointers work in practice.

Screenshots:

Known Bugs/Errors:

• When given a non-integer input, the program terminates with an uncaught exception of

type “std::invalid argument: stoi: no conversion”

• When the number is too big, say past 200 digits, the program runs extremely slowly.

Sometimes, with numbers sufficiently past 200 digits, the program simply doesn’t run

and gives a stack overflow error.

Lessons Learned:

• What went well during this lab included the successful implementation of a working

linked list with all the required functions working.


• Next time, I will try to go above and beyond and try to implement a data structure that

is more versatile and one that contains more advanced functions to do more.

You might also like