c++ - 制作通用链表将下一个指针放在结构的开头

Question

我正在阅读其中一本书并卡在一个特定的问题上。

链表结构的定义:::

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

书上说“将 next 指针放在结构或类的开头可以轻松编写通用列表处理例程，无论数据保存什么。”

我不明白将下一个指针放在顶部会有什么帮助。

此外，要制作一个通用列表，我们不需要数据类型为通用或 void* 吗？

Answer 1

您正在看的这本书Programming Interviews Exposed(据我所知)不是一本关于 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*，并在 Employee 上使用您为 Person 编写的任何操作。如果您为 LinkedList 的 type 字段分配适当的常量，您甚至可以混合 PersonNode 并使用 type 字段稍后确定每个节点的类型。

这在 20 多年前是一种有用的编程方式。当然，它仍然有效，但大多数人会选择让编译器为他们管理继承，如果他们有选择的话，所有现代面向对象的语言都提供该选项。

类(class):了解该技术以防您在旧代码中遇到它，但如果可以的话，为您的新代码选择不同的实现。