Используется ли использование только `* head` или было бы более конкретно c с использованием` * tail` и `size` в C?

Question

При изучении структуры данных я пришел к разделу Linked List , в частности к главному и хвостовому узлам.

Из того, что мне читали, многие пользователи C склонны использовать только Node *head;.

Но была часть, где рекомендовалось использовать следующий код:

typedef structure _node node;

struct _node{
  int data;
  Node *next;
}

typedef structure list {
  Node *head;
  Node *tail;
  int size;
} List;

Как человек, который только начал изучать C и структуру данных, я нахожу это более понятным, когда пишу это так, но поскольку учитель сказал нам, что большинство людей пишут не так, а просто используют Node *head, мне было любопытно узнать, что на самом деле используют другие.

Разработчики и C пользователи действительно используют только одну строку, или они используют ее как код, написанный выше?

Answer 1

Структура данных зависит от того, хотите ли вы оптимизировать для конкретных c вариантов использования. Например, если у вас есть связанный список, где элементы должны быть вставлены в основном перед первым элементом, тогда может быть излишним поддерживать значение tail. Однако, если элементы должны быть вставлены в основном в конце, имеет смысл сохранять указатель на хвост, вместо того, чтобы снова и снова пробегать полный список всякий раз, когда элемент должен быть вставлен. И если вы хотите использовать свой список для случая использования «первым пришел - первым обслужен» (FIFO), то полезно иметь прямой доступ к голове и хвосту.

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

Так что это зависит, и могут быть и другие факторы, которые следует учитывать.