链表推送方法

Question

我正在C++中处理一个模板化的泛型链表，并且我在使用push（）方法时遇到了问题。我想我知道这个问题，但我想不出解决办法。这是我的推法。

template <class T> void DLL<T>::pushFront(T value) {
  Node<T> node(value);
  temp = node;
  temp->setPrev(*head);
  temp->setNext(*(head->getNext()));
  head->setNext(*temp);
  temp->getNext()->setPrev(*temp);                                                                                                                                    
  this->length++;                                                                                                                                                     
}

在将一些整数推入列表后，遍历列表并打印出值会导致打印出内存中看似随机空间的数字。我认为这是因为在push函数返回后，节点变量被破坏了。有人知道为什么不起作用吗？所有的setNext/Prev（）和getNext/Preve（）函数在我的其他测试中都能正常工作。我被难住了。。。

编辑*

变量head和temp是Node<T>*

Answer 1

您应该使用指针来存储列表中的节点。

Node<T> node(value);
temp = node;

在该代码超出范围后，分配给"节点"的内存将被释放，从而损坏您的链表。改为使用指针：

template <class T> void DLL<T>::pushFront(T value) {
  Node<T> *node = new Node<T>(value);
  node->setPrev(head);
  node->setNext(head->getNext());
  head->setNext(node);
  node->getNext()->setPrev(node);
  this->length++;
}

你的类节点应该是这样的：

template<class T> class Node {
public:
    /* ... */
private:
    Node<T> *next;
    T data;
};

Answer 2

首先，head应该而不是是全局的——它应该是DLL的成员，所以每个dll（糟糕的缩写，IMO）都有一个头（可能还有一个尾）。

其次，getnext、setnext、getprev和setprev在我看来是100%毫无意义的浪费时间。通过使用它们而不是读取/分配变量，您在封装或可读性方面没有获得任何好处。

第三，正如@fontanini已经指出的，当你push一个节点时，你需要实际分配一个节点，而不是每次都试图重用一个节点。

第四，在我看来，您似乎使所涉及的指针操作过于复杂，可能至少部分是由于getnext/setprev等的丑陋/不可读性。一旦您有了一个节点，将其拼接到链表的前面只需要三个操作（加上增加长度）：

template <class T> 
void DLL<T>::pushFront(T value) { 
   node<T> *tmp = new node<T>(value);
   tmp -> next = head;
   tmp -> next -> prev = tmp;
   head = tmp;
   ++length;
}

当我完成这项工作时，我发现只将指针传递到节点的ctor会简单一些。在这种情况下，结果是这样的：

template <class T> 
void DLL<T>::pushFont(T value) { 
   // These parameters are value, prev, and next, respectively.                             
   node<T> *tmp = new node<T>(value, NULL, head);
   tmp->next->prev = tmp;
   head = tmp;
   ++length;
}