Question

c++ Computational Complexity

Create a singly linked list for storing positive integers. Each node will store one integer. For example, 12->3->5->777-111 is such a list. There are five nodes in this list. 12 is the head node and 111 is the tail node. (111 points to NULL.) Your linked list starts empty. It should support the following three operations: Add x to tail: Create a new node whose data field contains x. Append this node at the end of the list. For example, for the list 12->3->5->777->111, if we add 2 to the tail, then the list becomes 12->3->5->777-111->2. Remove from head: If the list is empty, then do nothing. Otherwise, remove the head node from the list For example, for the list 12-5-777-11, if we remove a node from its head, then it becomes 5777>11 . Find middle node: Find the middle node(s) from the list and returns the corresponding data field(s). If the number of nodes is odd, then the middle node is just the one in the middle of the list. For the list 12→3→5→777-111, there are five nodes, the middle node's data field contains 5. If the number of nodes is even, then the middle nodes are the two nodes in the middle of the list. For the list 12→3→5→777-111->2, there are six nodes, the middle nodes, data fields contain 5 and 777. If the number of nodes is zero, then return 0.

Answer 1

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

class LinkedList{
    // Struct inside the class LinkedList
    // This is one node which is not needed by the caller. It is just
    // for internal work.
    struct Node {
        int x;
        Node *next;
        //Node *head;
    };

// public member
public:

    Node *head;
    Node *last;
    // constructor
    LinkedList(){
        head = NULL; // set head to NULL
        last = NULL;
    }

    // This adds a new value at the end of the list
    void addValue(int val){
        Node *n = new Node();   // create new Node
        n->x = val;             // set value
        n->next = NULL;         // make the node point to NULL.
        if (this->head==NULL){
            head = n;
            last = n;
        }
        else{
            last->next = n;
            last = n;
        }

    }

    // returns the first element in the list and deletes the Node.
    // caution, no error-checking here!
    int popValue(){
        Node *n = head;
        int ret = n->x;

        head = head->next;
        delete n;
        return ret;
    }

// private member
/*private:
    Node *head; // this is the private member variable. It is just a pointer to the first Node
};*/
};

int main() {
    LinkedList list;
    string input;
    cout<<"Please provide input of values: ";
    getline(cin, input);
    istringstream iss(input);
    string operation;
    while (iss>>operation){
        if (operation.length()==1){
            list.popValue();
        }
        else{
            int number = stoi(operation.substr(1, operation.length()));
            //int number = atoi(a.c_str());
            list.addValue(number);
        }
    }

    //list.addValue(5);
    //list.addValue(10);
    //list.addValue(20);
    if (list.head==NULL){
        cout<<"empty"<<endl;
    }
    while(list.head!=NULL){
        cout << list.popValue()<<" -> ";
    }

    //cout << list.popValue() << endl;
    //cout << list.popValue() << endl;
    // because there is no error checking in popValue(), the following
    // is undefined behavior. Probably the program will crash, because
    // there are no more values in the list.
    // cout << list.popValue() << endl;
    return 0;
}