C++ 中的双向链表 - insertFirst 与 insertLast 实现

Question

在我用 C++ 实现双向链表时，我不明白为什么在 insertFirst 中，你总是需要做 pNewLink->pNext = pFirst 但在 insertLast 中，如果列表不为空，您仅执行 pNewLink->pPrevious = pLast？否则这两种方法似乎完全相反。

void insertFirst(double dd) //insert at front of list
{
    Link* pNewLink = new Link(dd);

    if( isEmpty() ) 
        pLast = pNewLink;
    else
        pFirst->pPrevious = pNewLink;

    pNewLink->pNext = pFirst;
    pFirst = pNewLink;
}


void insertLast(double dd)  //insert at end of list
{
    Link* pNewLink = new Link(dd);

    if( isEmpty() )
        pFirst = pNewLink;
    else
    {
        pLast->pPrevious = pLast;
        pNewLink->pPrevious = pLast;
    }

    pLast = pNewLink;
}

Answer 1

首先，您的实现似乎不正确，因为当列表为空时，您不应在 insertFirst 中设置 pNewLink->pNext。

如果您进行此修改，两种方法看起来都会更像 "symetric"。

如果最后插入。你没有 "next value" 所以你没有设置它但是你有以前的值所以你设置这个。

如果你先插入，你没有 "previous value" 所以你不设置它但是你有下一个值所以你设置这个。

C++ 中的双向链表 - insertFirst 与 insertLast 实现

Doubly-linked list in C++ - insertFirst vs. insertLast implementation

c++

doubly-linked-list