c++ - 如何删除双向链表数据并返回？

Question

template <class T>
class Node
{
public:
    T data;
    Node<T>* prev;
    Node<T>* next;

    // default constructor (parameterized)
    template <class T>
    Node(T value)
    {  
        data = value;
        prev = NULL;
        next = NULL;
    }
};

---

template <class T>
T CircularLinkedList<T>::RemoveAt(int p){
    Node<T>* temp = head;
    if (head == NULL){
        return 0;
    }
    else if (p == 0){
        return temp;
    }
    else{
        temp = head->next;
        for (int i = 0; i < p-1; i++)
            temp = temp->next; 
        temp->next = 
    }
}

我正在制作双向链表的删除函数。
如果 p 大于等于 0，我不知道如何处理这段代码。
如何移除值并同时返回？

Answer 1

假设 head 位于位置 p == 0，那么您应该首先检查 head 不是最后一个元素，因为如果是，列表将为空。然后，您只需遍历列表直到所需位置，然后将 temp 的 prev->next 设置为 temp->next，同样将 temp 的 next->prev 设置为 temp->prev 以删除 temp。这适用于 0 和大于 0 的值。

这是一个可能实现的简单示例:

template <class T>
T CircularLinkedList<T>::RemoveAt(int p)
{
    Node<T>* temp = head;
    if(head == NULL)
    {
        return NULL;
    }
    if(head->next == head)
    {
        // Set head to null and return
        head = NULL;

        return NULL;
    }

    // List won't be depleted after removal
    // Move to next p number of times, temp already at head
    for(int i = p; i > 0; --i)
    {
        temp = temp->next;
    }
    // Now remove temp and let it be return value
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;

    return temp.data;
}