有没有更简洁的方法来编写此 C++ 代码？

Question

我正在学习 C++，来自动态类型语言背景，并在 C++ 中实现算法来完成此学习。我当前的（子）项目是一个将元素插入到排序（双）链表中的函数。该实现是节点的集合。每个节点都包含列表元素中的数据以及指向列表的前一个和下一个元素的指针（或

nullptr

表示第一个和最后一个元素。）通过跟随指针访问列表元素，从对头的引用开始或尾巴。

我的第一遍无法编译。我编写了以下代码（经过几次迭代后），它确实编译并产生了预期的结果（下面不包括一些边缘情况。）但是，这段代码有味道。我觉得应该有一种更干净的方法：

// Leaving out a bunch of implementation details, here's
// LinkedList; the members outside this have basically the 
// meaning you'd expect (I think, still learning...)

template <typename T>
class LinkedList {
public:

  // Node type that is particular to the LinkedList<T> type
  class Node {
  public:
    Node* next;
    Node* prev;
    T data;
    Node() : next(nullptr), prev(nullptr) {}
    Node(const T& dataArg) : next(nullptr), prev(nullptr), data(dataArg) {}

  };

private:
  Node* head_;
  Node* tail_;
  int size_;
}

// insert newData into list, preserving sorted order.
template <typename T>
void LinkedList<T>::insertOrdered(const T& newData) {
  
  // skip edge case implementation.

  Node* newNode = new Node(newData);
  Node* cur;
  cur = head_;
  while (cur) {
    // This is the smelly part.
    // I'm particlularly annoyed that `prev` isn't accessed with
    // something more like cur and newNode.
    if (cur->data > newData) {
      Node& prev = *cur->prev;  // yuck.
      prev.next = newNode;
      cur->prev = newNode;
      newNode->next = cur;
      newNode->prev = &prev;  // eew.
      size_++;
      return;
    }
    cur = cur->next;
  }
  // more edge cases.
}

这是我在第一次尝试中尝试的，看起来非常优雅。

// Doesn't work.
Node* prev;
if (cur->data > newData) {
  prev = cur->prev;  // !! cur->prev is a reference, not a pointer, etc.
  prev->next = newNode;
  cur->prev = newNode;
  newNode->prev = prev;
  newNode->next = cur;
  size_++;

特别是，我喜欢将 prev 作为节点指针使用的想法

Node* prev;

，因此它与

cur

和

newNode

具有相同的实体类型。

Answer 1

在

cur

之前插入节点的常用方法是

cur->prev->next = cur->prev = newNode;
newNode->prev = cur->prev;    
newNode->next = cur;

无需引入变量来保存

cur->prev

、引用或指针。

当然，这假设

cur

和

cur->prev

均非空。