связанный список, добавляющий к хвосту, беспорядку
Visual Studio 2008 C
То, что я не могу понять об этом связанном списке, еще является добавлением к хвосту в часть если оператор.
Когда голова и хвосты присвоены адрес памяти 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;
}
}
4 ответа
Когда вы впервые добавляете элемент (назовем его A ) в список, head имеет значение null, и вы проходите через если часть. Это означает, что и голова , и хвост устанавливаются так, чтобы указывать на A при добавлении этого первого элемента
Теперь давайте добавим еще один элемент B . На этот раз head не является нулевым, поэтому он проходит через часть else , устанавливая tail так, чтобы он указывал на B , но оставлял голова указывает на A .
Как и ожидалось, теперь у вас есть голова , указывающая на A , A указывая к B ,
head ---> A ---> B -+-> C ---> NULL
|
tail ---------------+
Преимущество сохранения указателя tail в односвязном списке состоит в том, чтобы избежать необходимости проходить через весь список, чтобы найти конец, когда вы пытаетесь добавить элемент в конец.
При обходе всего списка в конце выполняется вставка за O (n) временную операцию (затраченное время зависит от количества элементов в списке). Использование указателя хвоста делает временную операцию O (1) (одинаковое количество времени независимо от размера списка).
Кроме того, двусвязный список имеет дополнительное использование для указателя tail - он дает возможность быстро начать обход от конца списка к началу, используя tail и prev ] вместо указателей head и указателей next .
Обход всего списка приводит к вставке в конце O (n) операции времени (затраченное время зависит от количества элементов в списке). Использование указателя хвоста делает временную операцию O (1) (одинаковое количество времени независимо от размера списка).
Кроме того, двусвязный список имеет дополнительное использование для указателя tail - он дает возможность быстро начать обход от конца списка к началу, используя tail и prev ] вместо указателей head и указателей next .
Обход всего списка приводит к вставке в конце O (n) операции времени (затраченное время зависит от количества элементов в списке). Использование указателя хвоста делает временную операцию O (1) (одинаковое количество времени независимо от размера списка).
Кроме того, двусвязный список имеет дополнительное использование для указателя tail - он дает возможность быстро начать обход от конца списка к началу, используя tail и prev ] вместо указателей head и указателей next .
Часть else просто обновляет хвост списка, поскольку голова не меняется, когда вы добавляете в связанный список.
Это оптимизация, чтобы сохранить указатель на хвост Буферизованный элемент, поэтому вам не нужно проходить весь список, начиная с заголовка каждого добавления.
При первом вызове add, head и tail будут указывать на вновь созданный блок памяти. Все последующие вызовы add будут выполняться в части else, которая изменит только указатель хвоста, в основном изменяя старый хвост-> рядом, чтобы указывать на новый блок памяти, а затем обновлять хвост, чтобы также указывать на этот новый блок памяти .
Это эффективный способ добавления. Если бы использовалась только голова, то каждый раз, когда вы добавляли новый node_temp, вам пришлось бы обходить все следующие указатели, начиная с head, пока вы не дойдете до ранее добавленного node_temp (чей следующий указатель будет NULL), а затем добавить новый node . Тогда это будет алгоритм O (n), а не вышеупомянутый O (1).
Дело не в том, что голова все еще указывает на хвост. Голова указывает на бывший хвост. Когда список содержал только один элемент, это были и голова, и хвост. Когда был добавлен новый узел, хвостовой указатель был обновлен. Указатель головы по-прежнему указывает на первый узел, что верно.