добавление связанного списка в хвост, путаница

Question

Visual Studio 2008 C

Что я не могу понять в этом связанном списке, так это добавление к хвосту в остальной части оператора if.

Когда головке и хвостам назначен адрес памяти node_temp для хвоста и головки, оба указывают на одну и ту же ячейку памяти.

Однако в остальной части голова фактически все еще указывает на хвост. Есть что-то, чего я не могу объяснить и не понимаю в остальной части?

Надеюсь, кто-нибудь сможет мне лучше объяснить.

static struct convert_temp
{
    size_t cel;
    size_t fah;
    struct convert_temp *next;
} *head = NULL, *tail = NULL;

/** Add the new converted temperatures on the list */
void add(size_t cel, size_t fah)
{
    struct convert_temp *node_temp = NULL; /* contain temp data */

    node_temp = malloc(sizeof(*node_temp));

    if(node_temp == NULL)
    {
        fprintf(stderr, "Cannot allocate memory [ %s ] : [ %d ]\n",
            __FUNCTION__, __LINE__);
        exit(0);
    }

    /* Assign data */
    node_temp->cel = cel;
    node_temp->fah = fah;
    node_temp->next = NULL;

    if(head == NULL)
    {
        /* The list is at the beginning */
        head = node_temp;   /* Head is the first node = same node */
        tail = node_temp;   /* Tail is also the last node = same node */
    }
    else
    {
        /* Append to the tail */
        tail->next = node_temp;
        /* Point the tail at the end */
        tail = node_temp; 
    }
}

Answer 1

Когда вы в первый раз добавляете элемент (назовем его A) в список, head равен нулю, и вы проходите через часть if. Это означает, что и head, и tail устанавливаются так, чтобы указывать на A при добавлении этого первого элемента.

Теперь давайте добавим еще один элемент B. На этот раз head не равно нулю, поэтому он проходит через часть else, устанавливая tail для указания на B, но оставляя head указывая на A.

Это, как и ожидалось, теперь у вас есть head, указывающий на A, A, указывающий на B, B, указывающий на ничто (ноль) и tail, указывающий на B.

Давайте рассмотрим шаг за шагом.

Initial state:  head -+-> null
                      |
                tail -+

Insert item A:  head -+-> A ---> null
                      |
                tail -+

Insert item B:  head ---> A -+-> B ---> null
                             |
                tail --------+

Insert item C:  head ---> A ---> B -+-> C ---> null
                                    |
                tail ---------------+

Вы можете видеть на каждом этапе (кроме начального), что текущий хвост настроен так, чтобы указывать на новый узел (который уже указывает на NULL для его следующего узла), а затем указатель хвоста обновляется, чтобы указывать на новый последний узел.

На самом деле, давайте пройдем добавление C даже на больше деталей (строка за строкой), чтобы вы могли видеть, что делает каждая строка кода (я переименовал node_temp в * 1036) * просто чтобы помочь с форматированием):

Starting state:                head ---> A -+-> B ---> null
                                            |
                               tail --------+

node = malloc(sizeof(*node));  node ---> C ----------> ?
 (allocate node C)             head ---> A -+-> B ---> null
                                            |
                               tail --------+

node->next = NULL;             node ---> C --------+
 (ignore payload cel/fah                           |
  for now since it's not       head ---> A -+-> B -+-> null
    relevant to the list                    |
               structure)      tail --------+

tail->next = node;             node ---------------+
 (first in else clause)                            |
                               head ---> A -+-> B -+-> C ---> null
                                            |
                               tail --------+

tail = node;                   node ---------------+
 (second in else clause)                           |
                               head ---> A ---> B -+-> C ---> null
                                                   |
                               tail ---------------+

Затем, в конце концов, node исчезает, поскольку это локальная переменная, и у вас есть конечное состояние:

                               head ---> A ---> B -+-> C ---> NULL
                                                   |
                               tail ---------------+

Преимущество сохранения указателя tail в односвязном списке состоит в том, что вам не нужно обходить весь список, чтобы найти конец при попытке добавить элемент в конец.

Обход по всему списку делает вставку в конце операции O(n) времени (время зависит от количества элементов в списке). Использование указателя tail делает эту операцию O(1) времени (то же время независимо от размера списка).

Кроме того, двусвязный список имеет дополнительное использование для указателя tail - он дает возможность быстро начать обход с конца списка до начала, используя tail и prev указатели вместо head и указатели next.

Answer 2

Другая часть просто обновляет tail списка, так как заголовок не изменяется при добавлении в связанный список.

Оптимизация для сохранения указателя на буферизованный хвостовой элемент, так что вам не нужно проходить весь список из заголовка каждого добавления.

Answer 3

При первом вызове add голова и хвост указывают на вновь созданный блок памяти. Все последующие вызовы add будут перенесены в остальную часть, которая изменит только указатель хвоста, в основном изменив старый tail-> рядом с указателем на новый блок памяти, а затем обновит tail, чтобы он также указывал на этот новый блок памяти. .

Это эффективный способ добавления. Если бы использовался только head, то каждый раз, когда вы добавляли новый node_temp, вам приходилось обходить все следующие указатели, начиная с head, пока вы не достигли ранее добавленного node_temp (следующий указатель которого был бы равен NULL), а затем добавили новый узел , Тогда это будет алгоритм O (n), а не описанный выше O (1).

Answer 4

Дело не в том, что голова все еще указывает на хвост. Голова указывает на бывший хвост. Когда список содержал только один элемент, это были и голова, и хвост. Когда новый узел был добавлен, хвостовой указатель был обновлен. Указатель головы по-прежнему указывает на первый узел, что является правильным.