Main goal: Use pointers to implement a dynamic array and a singly linked list. Y

Question

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.

Make sure you test all these above functions in the main() function. Separate compilation is required.

Explanation / Answer

PROGRAM CODE:

/*
* SinglyLinkedList.cpp
*
* Created on: 03-May-2017
* Author: kasturi
*/

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

struct Node {
int value;
Node *next;
};
class LinkedList
{
   int size_linkedList; //number of nodes on the linked list
   struct Node *head;
   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
public:
   LinkedList(int);
   ~LinkedList();
   void push_back(int);
   void pop_back();
   friend ostream &operator<<( ostream &output, const LinkedList &list );
   int size();
};

LinkedList::LinkedList(int cap)
{
   size_linkedList = 0;
   head = NULL;
   capacity = cap;
   array = new int[capacity];
   size_array = 0;
}

void LinkedList::push_back(int val)
{
   if(head == NULL)
   {
       head = new Node;
       head->value = val;
       head->next = NULL;
       size_linkedList++;
       array[size_array++] = val;
   }
   else
   {
       struct Node *temp = head;
       struct Node *tempNode = new Node;
       tempNode->value = val;
       tempNode->next = NULL;
       while(temp->next != NULL)
       {
           temp = temp->next;
       }
       temp->next = tempNode;
       size_linkedList++;
       array[size_array++] = val;
   }
}

void LinkedList::pop_back()
{
   if(head != NULL)
   {
       if(head->next == NULL)
           head = NULL;
       else
       {
           struct Node *temp = head;
           while(temp->next->next != NULL)
           {
               temp = temp->next;
           }
           temp->next = NULL;
       }
   }
}
int LinkedList::size()
{
   return size_linkedList;
}

ostream &operator<<( ostream &output, const LinkedList &list )
{
   struct Node *tempnode = list.head;
   int counter = 1;
   while(tempnode != NULL)
   {
       output<<counter++<<". "<<tempnode->value<<endl;
       tempnode = tempnode->next;
   }
   return output;
}

LinkedList::~LinkedList()
{
   delete head;
   delete array;
   size_array =0;
   size_linkedList = 0;
}

int main() {
   LinkedList lst(20);
   while(true)
   {
       int num;
       cout << "Please enter a number(-1 to stop): ";
       cin>>num;
       if(num == -1)
           break;
       else
           lst.push_back(num);
   }
   cout<<"Before removing: ";
   cout<<lst;
lst.pop_back();
lst.pop_back();
cout<<"After removing: ";
cout<<lst;
return 0;
}

OUTPUT:

Please enter a number(-1 to stop): 10

Please enter a number(-1 to stop): 20

Please enter a number(-1 to stop): 30

Please enter a number(-1 to stop): 40

Please enter a number(-1 to stop): -1

Before removing:

1. 10

2. 20

3. 30

4. 40

After removing:

1. 10

2. 20

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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