Удаление узла из круглого двойного связанного списка

Question

Я написал код для вставки элементов в круглый двусвязный список и для отображения этих элементов. Я также должен удалять хвостовой узел из списка, а также искать список для определенного элемента.

Это мой рабочий код для дополнения и печати:

void Circular_DLList::add_to_tail(int a) 
{ 
    DLLNode *temp = new DLLNode; 
    temp->info = a; 
    if (is_empty()) { 
     tail = temp; 
     temp->next = tail; 
     temp->prev = tail; 
    } 
    else { 
     temp->next = tail->next; 
     temp->prev = tail; 
     tail = temp; 
     tail->prev->next = temp; 
    } 
} 

void Circular_DLList::print_list() 
{ 
    DLLNode *ptr; 
    ptr = tail->next; 
    do { 
     cout<< ptr->info << endl; 
     ptr = ptr->next; 
    } 
    while(ptr != tail->next); 
} 

Независимо от того, что я пишу для функции delete_from_tail, это не вызывает ошибку сегментации: 11. Это моя попытка для функции (которая выдает ошибку).

int Circular_DLList::delete_from_tail() 
{ 
    int a = tail->info; 
    if(tail == tail->next) { 
     delete tail; 
     tail = NULL; 
    } 
    else { 
     tail = tail->prev; 
     delete tail->next; 
     tail->next = NULL; 
    } 
    return a; 
} 

Любой совет относительно того, как исправить это, будет фантастическим. Я пробовал отлаживать, но я не могу понять, в чем проблема, или где именно это связано. Thanks

Answer 1

Вопрос довольно очевиден, если вы внимательно посмотрите на него. Ваша функция удаления разбивает круговую цепочку списка ссылок. Как так? Обратитесь к функции удаления ниже:

int Circular_DLList::delete_from_tail() 
{ 
    int a = tail->info; 
    DLLNode *temp; 

    if(tail == tail->next) { 
     delete tail; 
     tail = NULL; 
    } 
    else { 
     tail = tail->prev; 
     delete tail->next; 
     tail->next = NULL; 
    } 
    return a; 
} 

В else-condition вы настраиваете tail->next = NULL, которая на самом деле ошибка и, следовательно, разрушает цепочку. Поэтому, когда вызывается печать, предполагается, что круговая цепочка не повреждена и, следовательно, случайно пытается получить доступ к указателю NULL, что, в свою очередь, приводит к ошибке сегментации.

Исправление очень просто увидеть код ниже:

int Circular_DLList::delete_from_tail() 
{ 
    int a = tail->info; 
    if(tail == tail->next) { 
     delete tail; 
     tail = NULL; 
    } 
    else { 
     temp = tail; 
     tail = tail->prev; 
     tail->next = temp->next;  // To maintain the circular chain 
     tail->next->previous = tail; // Since this element's previous also point to the node about to be deleted 
     delete temp; 
     temp = NULL; 
    } 
    return a; 
}