在双向链表的中间插入一个节点

Question

我必须构建一个函数，其目的是在由 DequeIterator 类管理的迭代位置之前/之后插入一个节点。为此，我必须将所有指针链接到正确的位置以使它们相互连接，但是，我在将所有指针链接到正确的节点时遇到了问题。

例如，如果我有一个节点 A、B、D、E 的双向链表，并且我的迭代器目前指向节点 D，并且我想在节点 D 之前插入一个节点 C。谁能帮我？谢谢

// iter will be an object from the DequeIterator.
void insert_before(DequeIterator<E>& iter, E x)
{
        // make sure the list is not empty
        // since I have a function insert_front already        
    assert(!is_empty());
        // create a temp pointer to hold node D 
    DNode<E>* temp = iter.node();
        // create a new node C, with its prev points to (D->prev)
        // and its next points to node C
    DNode<E>* temp2 = new DNode<E>(iter.node()->prev(), x, iter.node());
        // I know that I still have 2 more pointer to link
        // but I do not know how to get it connected from
        // node B to node C and node C to node D.
    iter.node()->next() = temp2;  // I attempted to do this, but it gave me an error
    _size++;
}

这是我遇到的错误

Error   1   error C2106: '=' : left operand must be l-value e:fall 2013cpsc 131linkeddequelinkeddequemain.cpp  312

Answer 1

该错误意味着函数next() iter.node()->next() 按值返回。这会导致编译器创建结果的临时副本（即右值）。由于其临时性，您无法为其分配其他值。

要解决您的问题，您应该更改 next() 函数的签名，以便它返回对下一个节点的引用（指向的指针）：

DNode<E>*& next();

最好同时包含一个const版本：

DNode<E>* const& next() const;

这允许您检索next()节点，即使在使用const DNode<E>节点时也是如此。