[提问，改进] 如何用C++实现一个类型安全的链表 ？

闲聊灌水
1

最近又闲得蛋疼，写链表。这里我用的插入方法是用哑节点
不过这次我用的方法是，通过类型分发来定义链表节点，并用nullnode类型对象代替 nullptr
比如

  • 抽象类型的 listnode
  • 子类型 nullnode
  • 子类型 dummynode
  • 子类型 datanode

我写过一遍 c++ 版本的代码，使用的是接口类，

class implException : public exception {
private:
  string message;

public:
  implException(const char *_message) : message(_message) {}
  const char *what() const throw() { return message.data(); }
};

class listnode;
class nullnode;
class dummynode;
class datanode;

class listnode {
public:
  virtual listnode * next_node() = 0;
  virtual void insert_next(listnode * pnode) = 0;
  // virtual void jump_next() = 0;
  virtual bool isnull() = 0;
  virtual int getdata() = 0;
  // virtual ~listnode() = 0
};

class nullnode : public listnode {
public:
  nullnode() {}

public:
  listnode * next_node() {
    throw implException("next node is not implied for nullnode type");
  }

  void insert_next(listnode * node) {
    throw implException("insert_next is not implied for nullnode type");
  }

  // void jump_next() {
  //   throw implException("jump_next is not implied for nullnode type");
  // }

  bool isnull() { return true; }

  int getdata() {
    throw implException("getdata is not implied for nullnode type");
  }
};

class dummynode : public listnode {
private:
  listnode * pnext;

public:
  dummynode(listnode * pnode): pnext(pnode) {}

public:
  listnode * next_node() { return pnext; }

  void insert_next(listnode * pnode) { pnext = pnode; }

  // void jump_next() { this = this -> pnext; }

  bool isnull() { return false; }

  int getdata() {
    throw implException("getdata is not implied for dummynode type");
  }
};

class datanode : public listnode {
private:
  int data;
  listnode * pnext;

public:
  datanode(int _data, listnode * _pnext) : data(_data), pnext(_pnext) {}

public:
  listnode * next_node() { return pnext; }

  void insert_next(listnode * pnode) { pnext = pnode; }

  // void jump_next() { this = this -> pnext; }

  bool isnull() { return false; }

  int getdata() { return data; }
};

static nullnode null = nullnode();

class list {
private:
  listnode * phead;
  listnode * ptail;

public:
  list() {
    phead = ptail = new dummynode(&null);
  }

  ~list() {
    listnode * pnode = phead;
    listnode * prev = nullptr;
    while(!pnode -> isnull()) {
      prev = pnode;
      pnode = pnode -> next_node();

      delete prev;
    }
  }

public:
  void push(int data) {
    datanode * pnode = new datanode(data, &null);
    ptail -> insert_next(pnode);
    ptail = ptail -> next_node();
  }

  friend ostream &operator<<(ostream &os, list &lst) {
    listnode * pnode = lst.phead -> next_node();
    while (!pnode -> isnull()) {
      os << pnode -> getdata() << ' ';
      pnode = pnode -> next_node();
    }
    return os;
  }
};

int main() {
  list lst;
  for(int i = 0; i <= 10; i += 1) {
    lst.push(i);
  }

  cout << lst << endl;
  return 0;
}

我的问题是，虽然 listnode 接口为子类型定义了方法，
但是你调用 getdata 的时候，调用的对象是 nullnode 类型怎么办 ？
为了简单，我选择抛出一个异常
但是要是放到 Java 实现，抛出异常又要一个又一个声明一遍，不得写死啊

我也可以定义一个类似于 Rust 中的 Option 数据类型来声明接口中所有函数的返回值，还没试过

不知道各位大佬有没有写过，有没有更好的方法

2

链表node不应该为null啊，要么存在，要么删掉，代码可以自己参考stl的list，比较省事

3

空节点nullnode，我主要是想替代nullptr

4

我觉得现在出现的复杂问题恰恰是nullnode引入的，有过度设计的嫌疑。这个nullnode替代nullptr的目的是什么呢

5

使用 nullptr 调用方法 nullptr -> foo() 会发生段错误，这是发生在运行时
我就想用 nullnode 类型来替代，这样就会在编译时检查到错误 pnull -> foo()
检测到的错误是没有为nullnode定义foo函数

6

我觉得这是一个设计的权衡问题，目前看来你这里使用nullobject的结果还是弊大于利的，链表中的insert和delete遇到nullnote应该是都需要特殊处理，为此你还特意定义了一个isnull的方法，不如直接在需要调用nullptr->foo()之前判断一下if (node == nullptr)简单直接。另外在c++里面抛出异常在大多数情况下都不是明智的做法

1 个赞