如何利用void指针与类型转换实现通用双向链表类？

问题背景 #

我已经完成了基于int类型的双向链表ADT实现，代码如下：

class DoublyLinkedList{
    struct Node{
        int value;
        Node* next; 
        Node* back;
    };
    Node* head;
    Node* tail;
    int count;
    Node* GetNewNode(int data);
    Node* NodeByIndex(int index);

public:
    DoublyLinkedList(){
        head = nullptr;
        head = nullptr;
    }

    // 成员函数声明，未包含定义
    void insertFront( int data );
    void insertRear( int data );
    int removeFrontInt();
    int removeRearInt();
    int size( );
    void makeEmpty();
    void print();
    bool insertAt( int data, int index );
    int removeAt(int index);
    int findIndex( int data );
};

int main(){
    DoublyLinkedList list;

    list.insertFront(1);
    list.insertFront(2);
    list.insertFront(3);
    list.insertRear(100);
    list.insertRear(200);
    list.insertRear(300);

    std::cout << "List: " << "\t";
    list.print();
    std::cout << "Size of the list: " << list.size() << std::endl;

    std::cout << "Removing first number in the list... " << std::endl;
    list.removeFrontInt();
    std::cout << "Removing last number in the list... " << std::endl;
    list.removeRearInt();
    return 0;
}

拓展任务要求 #

教授要求将节点的int类型数据改为void*，使链表能存储任意类型数据（存入和取出数据的指针而非数据本身），并新增以下成员函数：

void insertFront( void *data );
void insertRear( void *data );
void * removeFrontPtr( );
void * removeRearPtr( );

我的困惑 #

我完全搞不懂怎么操作，比如取出数据时难道不需要知道用户输入的数据类型才能进行类型转换吗？希望得到讲解帮助。

核心原理与实现讲解 #

用void*作为存储类型的核心逻辑是：让链表只负责管理指针的存储与传递，把类型判断的责任交给链表的使用者。void*是通用指针类型，可以指向任何数据类型的内存地址，链表不需要关心指针指向的具体内容，只需要保存这个地址即可。

具体修改步骤 #

1. 修改Node结构体
   把Node里的int value改成void* data，让每个节点存储指向任意类型数据的指针：

struct Node{
    void* data;
    Node* next; 
    Node* back;
};

2. 调整核心成员函数

• 原有的insertFront(int)、insertRear(int)可以保留（作为int类型的重载，方便兼容旧代码），新增要求的void*版本插入函数，实现逻辑和int版本类似，只是把传入的void*直接赋值给Node的data成员。
• 替换/新增取出函数：removeFrontPtr()和removeRearPtr()返回void*，取出节点保存的指针后，释放节点内存，返回这个指针。

3. 存入与取出的关键细节

• 存入数据：必须传入数据的地址，而非数据本身。比如存储int变量或自定义对象：

  // 存储int
  int num = 10;
  list.insertFront(&num);
  // 存储自定义对象
  class MyObj { /* ... */ };
  MyObj obj;
  list.insertRear(&obj);
  

• 取出数据：确实需要使用者自己做类型转换——因为只有使用者才知道自己存的是什么类型。比如取出int数据：

  void* ptr = list.removeFrontPtr();
  int* numPtr = static_cast<int*>(ptr);
  if(numPtr != nullptr) {
      std::cout << *numPtr << std::endl;
  }
  

  这里必须保证转换的类型和存入时的类型一致，否则会出现未定义行为（比如崩溃）。

4. 其他成员函数的适配
   比如原有的print()函数，因为void*无法直接打印内容，有两种适配方案：

• 新增需要使用者提供打印回调的版本：

  void print(void (*printFunc)(void*)) {
      Node* curr = head;
      while(curr != nullptr) {
          printFunc(curr->data);
          curr = curr->next;
      }
  }
  

  使用者调用时传入对应类型的打印函数：

  void printInt(void* data) {
      std::cout << *static_cast<int*>(data) << " ";
  }
  list.print(printInt);
  

• 或者让使用者自己取出数据后再打印，放弃链表的直接打印功能。

关键修改示例片段 #

class DoublyLinkedList{
    struct Node{
        void* data; // 改为void*
        Node* next; 
        Node* back;
    };
    Node* head;
    Node* tail;
    int count;
    Node* GetNewNode(void* data); // 调整参数为void*
    Node* NodeByIndex(int index);

public:
    DoublyLinkedList(){
        head = nullptr;
        tail = nullptr; // 修正原代码的笔误
    }

    // 保留原int版本函数（可选）
    void insertFront( int data );
    void insertRear( int data );
    int removeFrontInt();
    int removeRearInt();

    // 新增void*版本函数
    void insertFront( void *data );
    void insertRear( void *data );
    void * removeFrontPtr( );
    void * removeRearPtr( );

    int size( );
    void makeEmpty();
    // 适配后的print函数，需要回调
    void print(void (*printCallback)(void*));
    bool insertAt( void* data, int index ); // 调整参数
    void* removeAt(int index); // 返回void*
    // findIndex需要使用者提供比较函数，因为void*无法直接比较
    int findIndex( void* data, bool (*compareFunc)(void*, void*) );
};

// GetNewNode实现
DoublyLinkedList::Node* DoublyLinkedList::GetNewNode(void* data){
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = nullptr;
    newNode->back = nullptr;
    return newNode;
}

// insertFront void*版本实现
void DoublyLinkedList::insertFront(void* data){
    Node* newNode = GetNewNode(data);
    if(head == nullptr){
        head = tail = newNode;
    } else {
        newNode->next = head;
        head->back = newNode;
        head = newNode;
    }
    count++;
}

// removeFrontPtr实现
void* DoublyLinkedList::removeFrontPtr(){
    if(head == nullptr) return nullptr;
    Node* temp = head;
    void* data = temp->data;
    head = head->next;
    if(head != nullptr){
        head->back = nullptr;
    } else {
        tail = nullptr;
    }
    delete temp;
    count--;
    return data;
}

逻辑梳理 #

这种设计是C++模板出现前，实现通用容器的常用方式：链表的角色从"存储具体数据"变成"存储指针的容器"，只负责指针的增删改查，不关心指针指向的内容。类型安全的责任完全转移给调用者——调用者必须确保存入和取出时的类型一致，否则会出错。

内容的提问来源于stack exchange，提问作者Thalia