Question

Assignment: The Ordered List

In this assignment, you will create an ordered list of movies. The list will always be maintained in sorted order (ascending order, by movie title) by assuring that all new movies are inserted in the correct location in the list.

Create a new project to hold your implementation of an ordered singly-linked list. You will need a main.cppto use as a test driver, as well as header and implementation files as described below.

Movie

To represent movies for this assignment, create a library implementing a structure Movie. Use the files Movie.h and Movie.cpp to implement the movie library. The class definition is shown below:

struct Movie {
    std::string title;              /// Movie title
    unsigned short year;            /// Movie release year
    std::string director;           /// Director's name
    std::string rating;             /// Movie audience rating

    Movie( std::istream& infile );  /// construct given an input stream
    void write( std::ostream& outfile ) const;
};
std::ostream& operator<<( std::ostream& outfile, const Movie& movie );

Use the Item structure you created in lab as a guide for implementing the write() method and overloaded stream insertion operator for Movie. Movies should be written a format matching the following example:

Blade Runner 2049 (2017) R - Denis Villeneuve

Where “Blade Runner 2049” is the movie title, 2017 is the release year, the director’s name is “Denis Villeneuve”, and the audience rating is “R” (info from imdb.com).

The Movie constructor takes an input stream and reads the values for the movie from that input stream, provided they are in the following format:

Blade Runner 2049|2017|Denis Villeneuve|R

Specifically, the values for each attribute are provided in the order they are listed in the class (title, year, director, rating), and fields are separated by a vertical bar (“pipe”) symbol. You may assume the rating will be followed by the end of a line or end-of-file.

MovieNode

Create a library to represent a singly-linked list node that will contain a Movie as its payload. Call the node class MovieNode. Use the files MovieNode.h and MovieNode.cpp to implement the MovieNode library.

Use the ItemNode class you implemented in lab as a guide to create MovieNode; it should implement all the same functionality.

MovieNode Constructor
The constructor for MovieNode will need to use member initializer list syntax to sink the value of the Movieparameter into its payload attribute. See (http://en.cppreference.com/w/cpp/language/initializer_list). The reason for this is that unlike the Item you created in lab, the Movie structure does not have a default constructor. By the time the body of the MovieNode constructor begins executing, C++ requires that all members of the object must be fully constructed. But, since Movie does not have a default constructor, there is no way for it to be fully constructed before the MovieNode constructor begins to execute — except that a member initializer list is evaluated before the constructor itself begins executing! So, this solves the timing problem without requiring you to modify the Movie definition.

MovieNode Comparisons
When we create the method to insert in order to our list, it will be necessary to compare the titles stored in two nodes to find the correct location for an addition to take place. For convenience, we can overload the “less than” operator for the nodes themselves to perform this comparison. Add the following method to the MovieNode class:

bool operator < ( const MovieNode& rhs ) const;

This method will compare the title of the Movie it contains with the title contained in rhs’s Movie. The operator<() method should return true or false based on the comparison of the titles.

OrderedMovieList

Create a library to represent an ordered singly-linked list of movies called OrderedMovieList. Use the files OrderedMovieList.h and OrderedMovieList.cpp to implement the library. The class OrderedMovieList should follow the basic outline of the unordered list you created in lab. It will need a head pointer, but not a tail pointer (a tail isn’t useful for ordered lists). Also create implementations for write(), erase(), remove_front(), destructor, and an overloaded stream-insertion operator based on the ones you had in the unordered list class.

Implement an is_empty() method that will return true if the list is empty, or false otherwise.

Implement a method insert() which will insert a new Movie into the list while maintaining the order of the list; “order” will be defined here as alphabetical order by title. The insert() method must take a Movieas its only parameter, and will not return any value.

Complete method insert() to put the Movie (we’ll refer to it as new_movie here) in place. An overview of the algorithm is shown below.

   * create new node containing new_movie
   * initialize "current" & "previous" pointers for list traversal
   * while correct location not yet found
      * move on to next location to check
   * insert new_movie at correct location (2 cases: "at head" or "not at head")

Add the code shown below to function main() and use it to test the new methods. An input file movies.txt is provided as a resource with this assignment. Be sure to try adding different movies to movies.txt to be sure your implementation works in all possible cases.

OrderedMovieList movie_list;
std::ifstream    movie_db {"movies.txt"};
if( movie_db ) {
    while ( movie_db.good() ) {
      movie_list.insert( Movie{movie_db} ); 
    }
    movie_db.close();
    cout << "Alphabetical listing of movies available:\n"
         << movie_list << "\n\n";
}
else{
    cout << "file not found!\n";
}

Note that this class must not expose public methods similar to add_front() and add_back() as the consistency or integrity of the list object’s data could be compromised by their use — write a comment block in the class definition for OrderedMovieList that explains how. These two methods could be implemented as private, but there is little value in doing so.

Answer 1

Approach: The basic idea is to apply merge sort on linked list.
The implementation is discussed in this article: Merge Sort for linked List.

Complexity Analysis:

• Time Complexity: The merge sort of linked list takes O(n log n) time. In the merge sort tree the height is log n. Sorting each level will take O(n) time. So time complexity is O(n log n).
• Auxiliary Space: O(n log n), In the merge sort tree the height is log n. Storing each level will take O(n) space. So space complexity is O(n log n).

Efficient Solution
Approach:

1. Separate two lists.
2. Reverse the one with descending order
3. Merge both lists.

#include <bits/stdc++.h> using namespace std; // Linked list node struct Node {     int data;     struct Node* next; }; Node* mergelist(Node* head1, Node* head2); void splitList(Node* head, Node** Ahead, Node** Dhead); void reverselist(Node*& head); // This is the main function that sorts the // linked list void sort(Node** head) {     // Split the list into lists     Node *Ahead, *Dhead;     splitList(*head, &Ahead, &Dhead);     // Reverse the descending linked list     reverselist(Dhead);     // Merge the two linked lists     *head = mergelist(Ahead, Dhead); } // A utility function to create a new node Node* newNode(int key) {     Node* temp = new Node;     temp->data = key;     temp->next = NULL;     return temp; } // A utility function to reverse a linked list void reverselist(Node*& head) {     Node *prev = NULL, *curr = head, *next;     while (curr) {         next = curr->next;         curr->next = prev;         prev = curr;         curr = next;     }     head = prev; } // A utility function to print a linked list void printlist(Node* head) {     while (head != NULL) {         cout << head->data << " ";         head = head->next;     }     cout << endl; } // A utility function to merge two sorted linked lists Node* mergelist(Node* head1, Node* head2) {     // Base cases     if (!head1)         return head2;     if (!head2)         return head1;     Node* temp = NULL;     if (head1->data < head2->data) {         temp = head1;         head1->next = mergelist(head1->next, head2);     }     else {         temp = head2;         head2->next = mergelist(head1, head2->next);     }     return temp; } // This function alternatively splits // a linked list with head as head into two: // For example, 10->20->30->15->40->7 \ // is splitted into 10->30->40 // and 20->15->7 // "Ahead" is reference to head of ascending linked list // "Dhead" is reference to head of descending linked list void splitList(Node* head, Node** Ahead, Node** Dhead) {     // Create two dummy nodes to initialize     // heads of two linked list     *Ahead = newNode(0);     *Dhead = newNode(0);     Node* ascn = *Ahead;     Node* dscn = *Dhead;     Node* curr = head;     // Link alternate nodes     while (curr) {         // Link alternate nodes of ascending linked list         ascn->next = curr;         ascn = ascn->next;         curr = curr->next;         // Link alternate nodes of descending linked list         if (curr) {             dscn->next = curr;             dscn = dscn->next;             curr = curr->next;         }     }     ascn->next = NULL;     dscn->next = NULL;     *Ahead = (*Ahead)->next;     *Dhead = (*Dhead)->next; } // Driver program to test above function int main() {     Node* head = newNode(10);     head->next = newNode(40);     head->next->next = newNode(53);     head->next->next->next = newNode(30);     head->next->next->next->next = newNode(67);     head->next->next->next->next->next = newNode(12);     head->next->next->next->next->next->next = newNode(89);     cout << "Given Linked List is " << endl;     printlist(head);     sort(&head);     cout << "Sorted Linked List is " << endl;     printlist(head);     return 0; }