Почему так много примеров связанных списков помещают следующий указатель в конце каждого узла, а не в начале?

Question

Я видел довольно много примеров реализаций C связанных списков на этом сайте, и большинство из них размещают следующий указатель в конце каждого узла следующим образом ...

struct intNode1 {
   int data;
   intNode1 *next;
};

Почему они реализуют их так, а не так?

struct node {
   struct node *next;
};

struct intNode2 {
   struct node node;
   int data;
};

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

Например, вот (неполная) реализация односвязного списка, использующего оба вида узлов:

struct intList {
   struct intNode1 *head;
};

struct list {
   struct node *head;
};

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

/* Returns zero if successful or nonzero otherwise */
int list-insertInt(struct list *list, int n) {
   struct intNode2 * newNode;
   if(!(newNode = malloc(sizeof *newNode)) {
      return -1;
   }
   newNode->data = n;
   return list-insertNode(list, (struct node *)newNode);
}

/* Assumes that the list contains only int nodes. */
int list-containsInt(struct list *list, int n) {
   struct intNode2 *current = (intNode2 *)list->head;
   while (current) {
      if(current->data == n) {
         return true;
      }
      current = current->next;
   }
   return false;
}

Конечно, вы можете free список, не зная, какие у него узлы:

void list-free(struct list *list) {
   struct node *current = list->head;
   struct node *next;
   while(current) {
      next = current->next;
      free(current);
      current = next;
   }
}

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

Answer 1

Потому что учебники по структурам данных в основном предназначены для обучения понятий для начинающих.Такая «оптимизация» просто добавляет много шума в ухо новичка.То, что вы делаете со своими знаниями после школы, отделяет вас от остальных ...

Answer 2

Преимущество указателя в конце состоит в том, что узел и полезная нагрузка имеют один и тот же адрес.Это может показаться не слишком большим преимуществом, но вспомним, что было до ANSI C. Да, я говорю о том времени, когда компилятор даже не пытался проверить тип данных указателей.

Когда выхотел передать полезную нагрузку функции, которую вы могли бы просто передать указатель, сэкономив несколько байтов ввода (и ценное дисковое пространство!).

Answer 3

Я не знаю ни о ком другом, но я делаю это просто так, когда я хочу записать часть данных в файл, я просто пишу бит без указателей в конце (включая указатель prev, если это двусвязный список).

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

Answer 4

Некоторые связанные списки помещают указатель Next в конец структуры, некоторые нет. Я не вижу в этом проблемы.

Если честно, я не уверен, что когда-либо сталкивался с делом в C, где связанный список поддерживал разные типы узлов. Но делать то, что вы описываете, можно, если вам нужно это сделать.

Обратите внимание, что большинство программистов на C сегодня используют C ++, что позволит вам использовать наследование для достижения той же цели. Используя наследование, не имеет значения, где член Next размещен в классе.