Implement an ADT consisting of a singly linked list and a dynamic array of integ

Question

Implement an ADT consisting of a singly linked list and a dynamic array of integers

Main goal: Use pointers to implement a dynamic array and a singly linked list. You will encapsulate both in an ADT. Specifically, your ADT will include the following data members:

int *array; //dynamic array

int size_array; //number of elements stored in the dynamic array

int capacity; //the current number of integer spaces allocated to the dynamic array

struct Node {

int value;

Node *next

};

Node *head; //point to the first node on the linked list

int size_linkedList; //number of nodes on the linked list

Your ADT will also include the following member functions:

a default constructor to initialize the array and linked list correspondingly

the "big-3": destructor, copy constructor and overloaded assignment operator

void push_back(int val ); This member function inserts the value 'val' to the end of the dynamic array and the end of the linked list. Note that this function will require memory allocation (i.e., need to call the new operator).

void pop_back(); This member function deletes the last number from the array, and the last number from the linked list. Note that this function will require memory deallocation, i,e., need to call the delete operator.

an overloaded put operator (<<) to print out all the data items stored on the dynamic array and the linked list. Note that you are recommended to overload this operator as a friend function of your ADT.

Explanation / Answer

#include<iostream>
#include<fstream>
using namespace std;

class newADT
{
int* array;
int size_array;
int capacity;
  
typedef struct node{
int value;
struct node* next;
}Node;
  
Node* head;
int size_linkedList;

public:
newADT(){
          
   array = NULL;
size_array = 0;
   capacity = 0;
          
   head = NULL;
   size_linkedList = 0;
   }
      
   ~newADT(){
          
Node* itr = NULL,*temp = NULL;
          
if(array != NULL)
delete array;
          
   size_array = 0;
   capacity = 0;
          
   itr = head;
while(itr != NULL){
              
temp = itr;
   itr = itr->next;
   temp->next = NULL;
   delete itr;
   }
          
size_linkedList = 0;
   }

newADT(newADT& val){

int i = 0;
Node* itr = NULL, *temp = NULL, *curr = NULL;

if(val.capacity > 0 ){
  
size_array = val.size_array;
capacity = val.capacity;

array = new int[val.capacity];

while(i < val.size_array){
array[i] = val.array[i];
i++;
}
}
else{
array = NULL;
size_array = 0;
capacity = 0;
}

head = NULL;
itr = val.head;
size_linkedList = val.size_linkedList;

while(itr != NULL){

temp = new Node;
temp->value = itr->value;
temp->next = NULL;

if(head == NULL){
head = curr = temp;
}
else{
curr->next = temp;
curr = curr->next;
}

itr = itr->next;
}

}

newADT operator=(const newADT& val){

int i = 0;
Node* itr = NULL, *temp = NULL, *curr = NULL;

/***************Delete the contents of the object's array and linked list ****************/
if(array != NULL)
delete array;
          
   size_array = 0;
   capacity = 0;
          
   itr = head;
while(itr != NULL){
              
temp = itr;
   itr = itr->next;
   itr->next = NULL;
   delete itr;
   }
          
size_linkedList = 0;
/*****************************************************************************************/

itr = temp = NULL;

if(val.capacity > 0 ){

size_array = val.size_array;
capacity = val.capacity;

array = new int[val.capacity];

while(i < val.size_array){
array[i] = val.array[i];
i++;
}
}
else{
array = NULL;
size_array = 0;
capacity = 0;
}
  
itr = val.head;
size_linkedList = val.size_linkedList;

while(itr != NULL){

temp = new Node;
temp->value = itr->value;
temp->next = NULL;

if(head == NULL){
head = curr = temp;
}
else{
curr->next = temp;
curr = curr->next;
}

itr = itr->next;
}

}

void push_back(int val ){

int* temp1 = NULL, i =0;
Node* itr = NULL,*temp = NULL;

if(capacity == 0){
capacity = 100;
array = new int[capacity];
size_array = 0;
}
else if(size_array == capacity){

temp1 = array;

capacity += 100;
array = new int[capacity];

for(i=0; i<size_array ;i++){
array[i] = temp1[i];
}
}

array[size_array] = val;
size_array++;

itr = head;

if(itr != NULL){
while(itr->next != NULL){
itr = itr->next;
}
}

temp = new Node;
temp->value = val;
temp->next = NULL;

if(itr == NULL){
itr = head = temp;
}
else{
itr->next = temp;
}

size_linkedList++;
}

void pop_back(){

Node* temp = NULL, *prev = NULL;
if((size_array <= 0) && (size_linkedList <= 0)){
return;
}

/*I will not deallocate value in the array, rather i will decrement the count*/
size_array--;
  
size_linkedList--;
temp = prev = head;
while(temp->next != NULL){

prev = temp;
temp = temp->next;
}
  
if(temp == head){
head = NULL;
delete temp;
}
else{
prev->next = NULL;
delete temp;
}
}

friend ostream& operator<<(ostream &out, newADT& val){

int i=0;
Node* temp = NULL;

if((val.size_array <= 0) && (val.size_linkedList <= 0)){
return out;
}

out<< "Array values:" <<endl;
for(int i=0; i< val.size_array; i++)
out<< val.array[i] << " ";

out<<endl;

out<< "Linked List values:" <<endl;

temp = val.head;
for(int i=0; i< val.size_linkedList; i++){

out<<temp->value << " ";
temp=temp->next;
}

out<<endl;
return out;
}
};

int main()
{
newADT obj1;

obj1.push_back(10);
cout<<obj1;

newADT obj2 = obj1;
obj2.push_back(100);
cout<<obj2;

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.