Question

Two sorted lists have been created, one implemented using a linked list (LinkedListLibrary class) and the other implemented using the built-in Vector class (VectorLibrary class). Each list contains 100 books (title, ISBN number, author), sorted in ascending order by ISBN number.

Complete main() by inserting a new book into each list using the respective LinkedListLibrary and VectorLibrary InsertSorted() functions and outputting the number of book copy operations the computer must perform to insert the new book. Each InsertSorted() returns the number of book copy operations the computer performs.
Ex: If the input is:
Their Eyes Were Watching God
9780060838676
Zora Neale Hurston
the output is:
Number of linked list book copy operations: 1
Number of vector book copy operations: 95
Which list do you think will require the most operations? Why?
#include "LinkedListLibrary.h"
#include "VectorLibrary.h"
#include "BookNode.h"
#include "Book.h"
#include
#include
using namespace std;
void FillLibraries(LinkedListLibrary &linkedListLibrary, VectorLibrary &vectorLibrary) {
ifstream inputFS; // File input stream
int linkedListOperations = 0;
int vectorOperations = 0;
BookNode* currNode;
Book tempBook;
string bookTitle;
string bookAuthor;
long long bookISBN;
// Try to open file
inputFS.open("books.txt");
while(getline(inputFS, bookTitle)) {
inputFS >> bookISBN;
inputFS.ignore(1, '\\');
getline(inputFS, bookAuthor);
// Insert into linked list
currNode = new BookNode(bookTitle, bookAuthor, bookISBN);
linkedListOperations = linkedListLibrary.InsertSorted(currNode, linkedListOperations);
// Insert into vector
tempBook = Book(bookTitle, bookAuthor, bookISBN);
vectorOperations = vectorLibrary.InsertSorted(tempBook, vectorOperations);
}
inputFS.close(); // close() may throw ios_base::failure if fails
}
int main () {
int linkedListOperations = 0;
int vectorOperations = 0;
// Create libraries
LinkedListLibrary linkedListLibrary = LinkedListLibrary();
VectorLibrary vectorLibrary;
// Fill libraries with 100 books
FillLibraries(linkedListLibrary, vectorLibrary);
// Create new book to insert into libraries
BookNode* currNode;
Book tempBook;
string bookTitle;
string bookAuthor;
long bookISBN;
getline(cin, bookTitle);
cin >> bookISBN;
cin.ignore();
getline(cin, bookAuthor);
// Insert into linked list
// No need to delete currNode, deleted by LinkedListLibrary destructor
currNode = new BookNode(bookTitle, bookAuthor, bookISBN);
// TODO: Call LL_Library's InsertSorted() method to insert currNode and return
// the number of operations performed
// Insert into VectorList
tempBook = Book(bookTitle, bookAuthor, bookISBN);
// TODO: Call VectorLibrary's InsertSorted() method to insert tempBook and return
// the number of operations performed
// TODO: Print number of operations for linked list
// TODO: Print number of operations for vector
}

Answer 1

The linked list will likely require fewer book copy operations when inserting a new book compared to the vector because it involves adjusting pointers rather than shifting elements. The completion of the main function involves calling the appropriate insert methods and printing the number of operations for each data structure.

Step-by-step explanation:

The question pertains to the efficiency of insertion operations in two different data structures: a linked list and a vector. When inserting a new book into each structure, the number of copy operations required can vary significantly. The linked list, represented by the LinkedListLibrary class, typically requires fewer copy operations because elements can be inserted directly into their proper place without shifting the elements that follow. In contrast, the vector, represented by the VectorLibrary class, may require numerous copy operations as all elements past the insertion point need to be shifted.

To complete the main() function, the following pseudo-code can be used:

• 
  
• Call the InsertSorted() function on the linkedListLibrary with currNode and store the result in linkedListOperations.
• 
  
• Call the InsertSorted() function on the vectorLibrary with tempBook and store the result in vectorOperations.
• 
  
• Output the number of copy operations for the linked list and vector.

Based on the information given, it is expected that the vector will require more book copy operations for insertion because it must shift multiple elements to maintain the order. Conversely, the linked list can simply adjust pointers, resulting in potentially significantly fewer operations.