For this problem, let us take the linked list we wrote in a functional manner in

Question

For this problem, let us take the linked list we wrote in a functional manner in a previous assignment and convert it into a Linked List class. For extra practice with pointers we’ll expand its functionality and make it a doubly linked list with the ability to traverse in both directions.

Since the list is doubly linked, each node will have the following structure:

In addition, we’ll maintain both a head node and a tail node as variables within the class. Your class, therefore, should have at least two private attributes (data members): (a) a Node variable that serves as the head node; (b) a Node variable that serves as the tail node. (This list can be expanded later as we add functionality to the class.)

Description of the class

At the minimum, your class should have the following public member functions:

1. A default constructor. This constructor will:

a. Instantiate the head node and the tail node.

b. Set the previous node pointer of the head node to nullptr and the nextNode pointer to point to the tail node.

c. Set the previous node pointer of the tail node to point to the head node and the next node pointer to nullptr.

2. Node * addNodeToEnd (int value);

This function will add a node to the end of the list, set the node’s value, and return a pointer to the new node added.

3. Node * addNodeToBeginning (int value);

This function will add a node to the beginning of the list, set the node’s value, and return a pointer to the new node added.

4. void printListForward ();

This member function will traverse the list from the first node to the last node and print out the values using the formatting requirements we’ve maintained throughout the semester (e.g., 10 numbers per line, 5 byte field, etc).

5. void printListBackward ();

This member function will traverse the list from the last node to the first node and print out the values using the formatting requirements we’ve maintained throughout the semester (e.g., 10 numbers per line, etc).

6. void sort ();

This member function will sort the numbers in the list by using one of the sorting algorithms we’ve implemented before. (I suggest using Bubble Sort, as it works with adjacent elements.) Note that it is not necessary to swap actual Nodes; the sort can be performed by simply swapping values between nodes.

7. A destructor for the list.

This member function will traverse the list and delete each node in turn.

General Tasking

Once the LinkedList class is built, have your main() function perform the following tasks:

1. Instantiate a LinkedList object.

2. Read the data from the same file we used in the previous linked list problem, “Perm 50.txt”, into the list.

3. Print the list in forward order by using the printListForward() member function.

4. Sort the list by calling the sort() member function.

5. Print the list in forward order again, but after it has been sorted.

6. Print the list in reverse order using the printListBackward() member function.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------
Perm 50:

Explanation / Answer

#include<iostream>
#include<fstream>

using namespace std;

struct Node
{
    int number;
    Node *nextNode;
    Node *prevNode;
};

class LinkedList{

   private:
      Node *head;
      Node *tail;
   public:
      LinkedList(){
         head = new Node;
         head->prevNode = NULL;
         head->nextNode = tail;
         tail = new Node;
         tail->nextNode = NULL;
         tail->prevNode = head;
      }
      Node *addNodeToEnd(int value){
         Node *temp;
         temp = new Node;
         temp->number = value;
         tail->prevNode->nextNode = temp;
         temp->prevNode = tail->prevNode;
         temp->nextNode = tail;
         tail->prevNode = temp;
         return temp;
      }
      Node *addNodeToBegining(int value){
         Node *temp;
         temp = new Node;
         temp->number = value;
         temp->nextNode = head->nextNode;
         temp->prevNode = head;
         head->nextNode = temp;
         return temp;
      }
      void printListForward(){
         Node *temp;
         int count;
         temp = head->nextNode;
         count = 0;
         while (temp != tail){
             cout << temp->number << " ";
             count++;
             if (count == 10){
                count = 0;
                cout << endl;
             }
             temp = temp->nextNode;             
         }
      }
      void printListBackward(){
         Node *temp;
         int count;
         temp = tail->prevNode;
         count = 0;
         while (temp != head){
             cout << temp->number << " ";
             count++;
             if (count == 10){
                cout << endl;
                count = 0;
             }
             temp = temp->prevNode;             
         }
      }
      void sort(){
         Node *temp, *curr;
         int count;
         int value;
         temp = head->nextNode;
         count = 0;
         while (temp != tail){
             curr = temp->nextNode;
             while (curr != tail){
                   if (temp->number > curr->number){
                       value = temp->number;
                       temp->number = curr->number;
                       curr->number = value;
                   }
                   curr = curr->nextNode;
             }
             temp = temp->nextNode;             
         }
      }
      ~LinkedList(){

          Node *curr;
          curr = head->nextNode;
          while (curr != tail){
               delete(curr->prevNode);
               curr = curr->nextNode;
          }
          delete(head);
          delete(tail);
      }
  

};

int main(){

   int input;
   ifstream fin;
   LinkedList lt;

   fin.open("Perm50.txt");
   if (fin){
        while (fin >> input){
               lt.addNodeToEnd(input);
        }
        fin.close();
        lt.printListForward();
        cout << endl;
        lt.sort();
        lt.printListForward();
        cout << endl;
        lt.printListBackward();
   }
   else {
      cout << "Error in opening file";
   }
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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