I'm wondering how to improve the speed of adding elements to my list or just how to speed up the whole list implementation. Function which adds new elements first checks if object would be unique. If not it will just check if the new data is better (the lower value the better) that the old one and swap the values or just skip adding element. I have no idea how to make it work faster but I know that something here is probably terribly wrong. I need to use that list to add about 3 milion elements in less than 4 seconds. I enclose the code below:

#include <iostream>
struct node
{
    long shortestRoute;
    char* name;
    node *next;
    node()
    {
        next = 0;
    }
};
class List  {
public:
    node *first;
    List() { first = 0 ;}       
    void add(long shortestRoute, char* name)
    {
        node *node = new node;
        node->name = name;
        node->shortestRoute = shortestRoute;
        if(first == 0)
            first = node;
        else
        {
            node *temp = first;
            while(temp)
            {
                if(!strcmp(temp->name, name) && temp->shortestRoute > shortestRoute)
                {
                    temp->shortestRoute = shortestRoute;
                    return;
                }
                else if (!strcmp(temp->name, name))
                    return;
                else if(temp->next)
                    temp = temp->next;
                else
                    break;
            }
            temp->next = node;
            node->next = 0;
        }
    }   
    int size()
    {
        node *temp = first;
        int size;
        if(!first)
            size = 0;
        else
            size = 1;
        while(temp->next)
        {
            ++size;
            temp = temp->next;
        }
        return size;
    }
};
struct City
{
    City() { fastConnection = true; }
    int shortestRoute;
    char* name;
    Vector<char*> citiesSoFar;      
    bool fastConnection;

};