Почему моя функция Вставка для списка делает новые узлы?

Question

Здравствуйте. Моя проблема с этим кодом в моем втором цикле else;я никогда не вхожу в него, и поэтому я никогда не создаю новые узлы для своего списка.Может ли кто-нибудь помочь мне увидеть, что мне не хватает?

    bool List::Insert(int data)
{
    Node* P = new Node;
    if(P==NULL)
    {
        return false;
    }
    else
    {
        P ->info = data;
        P ->next = NULL;
            if(Head == NULL)
            {
                Head = P;
            }
            else
            {
                Node* lastNode;
                for(lastNode = Head; lastNode ->next != NULL; lastNode = lastNode ->next)
                {
                    lastNode ->next = P;
                }
            }
        return true;
    }
}

Answer 1

Это:

Node* lastNode;
for(lastNode = Head; lastNode ->next != NULL; lastNode = lastNode ->next)
{
    lastNode ->next = P;
}

совершенно неправильно. Он изменит указатель next, чтобы каждый отдельный узел , находящийся в данный момент в списке, указывал на ваш новый узел. Вам нужно только изменить указатель в последнем узле:

Node* lastNode = Head;
while (lastNode->next != NULL)
    lastNode = lastNode->next;
lastNode->next = P;

Для эффективности вы также можете использовать отдельный указатель Tail (в дополнение к Head), чтобы вы могли просто заменить всю эту операцию на:

Tail->next = P;
Tail = P;

Таким образом, вам не придется обходить весь список каждый раз, когда вы хотите добавить новый узел. Ваш код становится примерно таким (без обхода, а также с обновлением указателя хвоста):

// Prepare new node.

Node *P = new Node;
P->info = data;
P->next = NULL;

// If list empty, set head and tail to new node, otherwise
//   append it.

if (Head == NULL) {
    Head = P;
    Tail = P;
} else {
    Tail->next = P;
    Tail = P;
}

Я не стану критиковать тот факт, что ваш Insert метод на самом деле не вставляет, а скорее добавляет. Моя почти анальная сохраняющая придирчивость вряд ли поразит меня: -)

Answer 2

lastNode -> next = P; // это должно идти после for