How do I improve my performance with this singly linked list struct within my program?

Hey guys, I have a program that does operations of sets of strings. I have to implement functions such as addition and subtraction of two sets of strings. I need to get it down to the point where performance if of O(N+M), where N,M are sets of strings. Right now, I believe my performance is at O(N*M), since I for each element of N, I go through every element of M. I'm particularly focused on getting the subtraction to the proper performance, as if I can get that down to proper performance, I believe I can carry that knowledge over to the rest of things I have to implement.

The '-' operator is suppose to work like this, for example.

Declare set1 to be an empty set.

Declare set2 to be a set with { a b c } elements

Declare set3 to be a set with ( b c d } elements

set1 = set2 - set3

And now set1 is suppose to equal { a }. So basically, just remove any element from set3, that is also in set2.

For the addition implementation (overloaded '+' operator), I also do the sorting of the strings (since we have to).

All the functions work right now btw.

So I was wondering if anyone could

a) Confirm that currently I'm doing O(N*M) performance

b) Give me some ideas/implementations on how to improve the performance to O(N+M)

Note: I cannot add any member variables or functions to the class strSet or to the node structure.

The implementation of the main program isn't very important, but I will post the code for my class definition and the implementation of the member functions:

strSet2.h (Implementation of my class and struct)

// Class to implement sets of strings

// Implements operators for union, intersection, subtraction,
//  etc. for sets of strings

// V1.1 15 Feb 2011 Added guard (#ifndef), deleted using namespace RCH

#ifndef _STRSET_
#define _STRSET_

#include <iostream>
#include <vector>
#include <string>
// Deleted: using namespace std;  15 Feb 2011 RCH

struct node {
    std::string s1;
    node * next;
};

class strSet {

private:
    node * first;

public:
    strSet ();  // Create empty set
    strSet (std::string s); // Create singleton set
    strSet (const strSet &copy); // Copy constructor
    ~strSet (); // Destructor

    int SIZE() const;

    bool isMember (std::string s) const;

    strSet  operator +  (const strSet& rtSide);  // Union
    strSet  operator -  (const strSet& rtSide);  // Set subtraction
    strSet& operator =  (const strSet& rtSide);  // Assignment


};  // End of strSet class

#endif  // _STRSET_

strSet2.cpp (implementation of member functions)

#include <iostream>
#include <vector>
#include <string>
#include "strset2.h"

using namespace std;

strSet::strSet() {
    first = NULL;
}

strSet::strSet(string s) {
    node *temp;
    temp = new node;
    temp->s1 = s;
    temp->next = NULL;
    first = temp;
}

strSet::strSet(const strSet& copy) {
    if(copy.first == NULL) {
        first = NULL;
    }
    else {
        node *n = copy.first;
        node *prev = NULL;
        while (n) {
            node *newNode = new node;
            newNode->s1 = n->s1;
            newNode->next = NULL;
            if (prev) {
                prev->next = newNode;
            }
            else {
                first = newNode;
            }
            prev = newNode;
            n = n->next;
        }
    }
}

strSet::~strSet() {
    if(first != NULL) {
        while(first->next != NULL) {
            node *nextNode = first->next;
            first->next = nextNode->next;
            delete nextNode;
        }
    }
}

int strSet::SIZE() const {
    int size = 0;
    node *temp = first;
    while(temp!=NULL) {
        size++;
        temp=temp->next;
    }
    return size;
}    

bool strSet::isMember(string s) const {
    node *temp = first;
    while(temp != NULL) {
        if(temp->s1 == s) {
            return true;
        }
        temp = temp->next;
    }
    return false;
}

strSet strSet::operator +  (const strSet& rtSide) {
    strSet newSet;
    newSet = *this;
    node *temp = rtSide.first;
    while(temp != NULL) {
        string newEle = temp->s1;
        if(!isMember(newEle)) {
            if(newSet.first==NULL) {
   开发者_如何学运维             node *newNode;
                newNode = new node;
                newNode->s1 = newEle;
                newNode->next = NULL;
                newSet.first = newNode;
            }
            else if(newSet.SIZE() == 1) {
                if(newEle < newSet.first->s1) {
                    node *tempNext = newSet.first;
                    node *newNode;
                    newNode = new node;
                    newNode->s1 = newEle;
                    newNode->next = tempNext;
                    newSet.first = newNode;
                }
                else {
                    node *newNode;
                    newNode = new node;
                    newNode->s1 = newEle;
                    newNode->next = NULL;
                    newSet.first->next = newNode;
                }
            }
            else {
                node *prev = NULL;
                node *curr = newSet.first;
                while(curr != NULL) {
                    if(newEle < curr->s1) {
                        if(prev == NULL) {
                            node *newNode;
                            newNode = new node;
                            newNode->s1 = newEle;
                            newNode->next = curr;
                            newSet.first = newNode;
                            break;
                        }
                        else {
                            node *newNode;
                            newNode = new node;
                            newNode->s1 = newEle;
                            newNode->next = curr;
                            prev->next = newNode;
                            break;
                        }
                    }
                    if(curr->next == NULL) {
                        node *newNode;
                        newNode = new node;
                        newNode->s1 = newEle;
                        newNode->next = NULL;
                        curr->next = newNode;
                        break;
                    }
                    prev = curr;
                    curr = curr->next;
                }
            }
        }
        temp = temp->next;
    }
    return newSet;
}

strSet strSet::operator - (const strSet& rtSide) {
    strSet newSet;
    newSet = *this;
    node *temp = rtSide.first;
    while(temp != NULL) {
        string element = temp->s1;
        node *prev = NULL;
        node *curr = newSet.first;
        while(curr != NULL) {
            if( element < curr->s1 ) break;
            if( curr->s1 == element ) {
                if( prev == NULL) {
                    node *duplicate = curr;
                    newSet.first = newSet.first->next;
                    delete duplicate;
                    break;
                }
                else {
                    node *duplicate = curr;
                    prev->next = curr->next;
                    delete duplicate;
                    break;
                }
            }
            prev = curr;
            curr = curr->next;
        }
        temp = temp->next;
    }
    return newSet;
}

strSet& strSet::operator =  (const strSet& rtSide) {
    if(this != &rtSide) {
        if(first != NULL) {
            while(first->next != NULL) {
                node *nextNode = first->next;
                first->next = nextNode->next;
                delete nextNode;
            }
        }
        if(rtSide.first == NULL) {
            first = NULL;
        }
        else {
            node *n = rtSide.first;
            node *prev = NULL;
            while (n) {
                node *newNode = new node;
                newNode->s1 = n->s1;
                newNode->next = NULL;
                if (prev) {
                    prev->next = newNode;
                }
                else {
                    first = newNode;
                }
                prev = newNode;
                n = n->next;
            }
        }
    }
    return *this;
}

Yes, I believe your current operator- is O(N*M).

Since this is homework, I don't want to give you too much information, but ...

If your linked list were ordered, then you could write subtraction in O(N+M). This leaves two questions for you: how to keep the list ordered? and how to write an O(N+M) subtraction algorithm, given ordered lists.