如何删除双向链表数据并将其返回？

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 = 
    }
}

I'm making remove function of doubly linked list.
I don't know how to proceed this code if p is greater than equal to 0.
How to remove value and return it at the same time?

我正在制作双向链表的删除功能。如果p大于等于0，我不知道如何继续这个代码。如何删除值并同时返回它？

1 个解决方案

#1

Assuming head is at position p == 0, then you should first check that head is not the last element since the list will be empty if it is. Then you simply iterate over the list until the desired position and set temp's prev->next to temp->next and similarly temp's next->prev to temp->prev to remove temp. This works for both values of 0 and greater than 0.

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

Here's a quick example of a possible implementation:

以下是可能实现的快速示例：

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;
}