Создание общего связанного списка с размещением следующего указателя в начале структуры

Question

Я читаю одну из книг и застрял на одном конкретном вопросе.

Определение структуры для связанного списка :::

typedef struct LinkedList{
  LinkedList* next;
  int data;
}

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

Я не могу понять, как размещение следующего указателя сверху поможет здесь.

Кроме того, чтобы составить общий список, не нужен ли нам тип данных как общий или, скажем, void *?

Answer 1

Книга, которую вы просматриваете, Программируемые интервью - это (насколько я могу судить) не книга на C ++, а книга, предназначенная для подготовки вас ответить на вопросы, которые могут быть заданы на типичном техническом собеседовании. Я бы не стал воспринимать что-либо в книге как лучшую практику C ++, если только она не помечена как таковая (и, возможно, даже тогда).

Совет по размещению следующего указателя первым в структуре узла связанного списка исходит от языков, подобных C, где нельзя полагаться на реальное наследование, поддерживаемое компилятором. На самом деле идея заключается в том, чтобы реализовать что-то вроде наследования самостоятельно путем совмещения данных в структуре узла связанного списка. Рассмотрим:

typedef struct LinkedList {
  LinkedListNode* next;
  int type;
}

typedef struct Person {
  LinkedList listNode;
  char name[64];
  int age;
}

typedef struct Address {
  LinkedList listNode;
  char streetAddress[128];
  char city[32];
  char state[2];
  char zip[10];
}

typedef struct Employee {
  Person person;
  int department;
  int salary;
}

LinkedList здесь является базовым типом - сам по себе не слишком хорош, но полезен в качестве отправной точки для узлов с большим количеством данных. Вам не нужно ничего знать о других типах для выполнения операций со связанным списком на узле ... вы можете привести любой указатель узла к LinkedList * и получить доступ к необходимой информации. Таким образом, вы можете иметь список Person и список Address, и обоими можно управлять с помощью одного и того же набора процедур. Точно так же вы можете привести Employee * к Person * и использовать любые операции, которые вы написали для Person на Employee. Если вы назначите соответствующие константы полю type LinkedList, вы даже можете смешать PersonNode и использовать поле type, чтобы позже определить тип каждого узла.

Это был полезный способ программирования более 20 лет назад. Конечно, это все еще работает, но большинство людей предпочли бы, чтобы компилятор управлял наследованием для них, если у них есть опция, и все современные объектно-ориентированные языки действительно предлагают эту опцию.

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

Answer 2

Если вы поместите следующий указатель в начале, и все, что у вас есть, это void *, но вы знаете, что это узел связанного списка, вы всегда можете найти следующий указатель.Это в отличие от следующего указателя, размещаемого после «данных», при условии, что «данные» могут иметь разные размеры, вам нужно больше знать об объекте, чтобы найти следующий указатель

Answer 3

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

template <class T> class ListElement
{
   T data;
   ListElement* next;
   ...
}

Могут быть некоторые проблемы, касающиеся скорости с выравниванием памяти, наоборот, немного лучше, ноЯ сомневаюсь в этом!

hth

Марио