Use the Scientific Method to discover which data structure has a faster Delete o

Question

Use the Scientific Method to discover which data structure has a faster Delete operation. For this exercise, you will compare the deleteNode function found in the NumberList class to the erase function for the vector found in the standard vector header file (#include <vector>).

Scientific Method:

Question: Which data structure has a faster delete operation?

Hypothesis: [State your Hypothesis]

Experiment: Test your Hypotheses by writing a program.

Conclusion: Was your hypothesis correct?

Communicate your results to the class (Note: For both the Linked List and the Vector, you should assign the same pseudo-random data to it.)

1. deleteNode function in NumberList class

void NumberList::deleteNode(double num)

{

   ListNode *nodePtr; // To traverse the list

   ListNode *previousNode; // To point to the previous node

   // If the list is empty, do nothing.

   if (!head)

return;

   // Determine if the first node is the one.

   if (head->value == num)

   {

nodePtr = head->next;

delete head;

head = nodePtr;

   }

   else

   {

// Initialize nodePtr to head of list

nodePtr = head;

// Skip all nodes whose value member is

// not equal to num.

while (nodePtr != NULL && nodePtr->value != num)

{

   previousNode = nodePtr;

   nodePtr = nodePtr->next;

}

// If nodePtr is not at the end of the list,

// link the previous node to the node after

// nodePtr, then delete nodePtr.

if (nodePtr)

{

   previousNode->next = nodePtr->next;

   delete nodePtr;

}

   }

}

Vector Erase Example.cpp

#include <iostream>

#include <vector>

using namespace std;

int main ()

{

vector<int> numbers;

// Push the 1st 10 numbers onto the vector

for (int i=1; i<=10; i++)

        numbers.push_back(i);

// erase the 6th element

numbers.erase (numbers.begin()+5);

// erase the first 3 elements:

numbers.erase (numbers.begin(),numbers.begin()+3);

cout << "numbers contains:";

for (unsigned i=0; i<numbers.size(); ++i)

    cout << ' ' << numbers[i];

cout<<endl;

system("pause");

return 0;

}

Explanation / Answer

Which data structure has a faster delete operation?

Ans: LinkedList Delete operation is faster if you are going to delete something from head of the Node otherwise you will have to traverse each node from head node.
Vector delete operation is faster if you are going to delete something from end otherwise you will have to shift all the elements.

LinkedList Program:
#include <iostream>
using namespace std;
struct ListNode
{
int value;
struct ListNode *next;
};

class NumberList
{
struct ListNode *head;
public:
NumberList()
{
head = NULL;
}
void push(int new_value);
void deleteNode(double num);
void printList();
};

void NumberList::push(int new_value)
{
ListNode* new_node = new ListNode();
new_node->value = new_value;
new_node->next = head;
head = new_node;
}

void NumberList::deleteNode(double num)
{
ListNode *nodePtr; // To traverse the list
ListNode *previousNode; // To point to the previous ListNode
// If the list is empty, do nothing.
if (!head)
return;
// Determine if the first ListNode is the one.
if (head->value == num)
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
// Initialize nodePtr to head of list
nodePtr = head;
// Skip all nodes whose value member is
// not equal to num.
while (nodePtr != NULL && nodePtr->value != num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
// If nodePtr is not at the end of the list,
// link the previous ListNode to the ListNode after
// nodePtr, then delete nodePtr.
if (nodePtr)
{
previousNode->next = nodePtr->next;
delete nodePtr;
}
}
}

void NumberList::printList()
{
ListNode *node = head;
while (node != NULL)
{
printf(" %d ", node->value);
node = node->next;
}
}

int main()
{
NumberList *obj = new NumberList();
obj->push(10);
obj->push(9);
obj->push(8);
obj->push(7);
obj->push(6);
obj->push(5);
obj->push(4);
obj->push(3);
obj->push(2);
obj->push(1);
cout<<"Created Linked list is: ";
obj->printList();
obj->deleteNode(6);
obj->deleteNode(1);
obj->deleteNode(2);
obj->deleteNode(3);
cout<<"After deletion Linked list is: ";
obj->printList();
return 0;
}

vector Program:
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> numbers;
// Push the 1st 10 numbers onto the vector
for (int i=1; i<=10; i++)
numbers.push_back(i);
// erase the 6th element
numbers.erase (numbers.begin()+5);
// erase the first 3 elements:
numbers.erase (numbers.begin(),numbers.begin()+3);
cout << "numbers contains:";
for (unsigned i=0; i<numbers.size(); ++i)
cout << ' ' << numbers[i];
cout<<endl;
system("pause");
return 0;
}

conclusion:
Linked listis has better performance when deleting node from head,Deleting in middle or front requires traversing of all the elements
Vectore has better performance when deleting data from end.Deleting in middle or front requires shifting of all the elements

Based on the requirement choose the proper one.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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