c++ - 如何遍历链表？

Question

我可以从头到尾遍历双向链表，打印出列表并相应地对元素进行排序。但是我不能从尾指针遍历到头指针。我想通过向后遍历来打印列表。我也想要从排序列表中删除元素并显示内容。

Answer 1

您的 SortedInsert() 方法正在分配 2 个 Node 对象，但没有正确初始化它们。它应该只分配 1 个 Node 对象，因为您只插入 1 个元素。当列表中有 1 个 Node 对象时，Head 和 Tail 指针应该指向那个 Node 对象，而不是在不同的 Node 对象。

试试这个:

void DoublyLinkedList::SortedInsert(const int& new_element) {

    Node* np = new Node(new_element);

    if (!Head)
    {
        Head = np;
        Tail = np;
    }
    else if (new_element < Head->Element)
    {
        np->Next = Head;
        Head->Prev = np;
        Head = np;
    }
    else
    {
        Node *cur = Head->Next;
        while ((cur) && (new_element >= cur->Element))
            cur = cur->Next;

        if (cur)
        {
            np->Prev = cur->Prev;
            np->Next = cur;
            cur->Prev->Next = np;
            cur->Prev = np;
        }
        else
        {
            Tail->Next = np;
            np->Prev = Tail;
            Tail = np;
        }
    }    
}

当删除一个Node对象时，这是一个简单的遍历找到Node然后更新周围的Node对象不指向它不再存在，例如:

void DoublyLinkedList::Delete(const int& del_element)
{
    Node *cur = Head;
    while (cur)
    {
        if (cur->Element == del_element)
        {
            if (cur->Prev)
                cur->Prev->Next = cur->Next;
            if (cur->Next)
                cur->Next->Prev = cur->Prev;
            if (cur == Head)
                Head = cur->Next;
            if (cur == Tail)
                Tail = cur->Prev;
            delete cur;
            break;
        }
        cur = cur->Next;
    }
}