Не могу реализовать удаление элемента односвязного списка

Question

struct Element      
{
    int data;       
    Element* next;  
};
Element* start = nullptr;
Element* current = nullptr;

void create_list(int a)
{
    current = new Element;
    current->data = a;
    current->next = nullptr;
    start = current;
}

void new_element(int a) {
    Element* newElement = new Element;
    newElement->data = a;
    newElement->next = nullptr;

    current->next = newElement;
    current = newElement;
}

void print_list() {
    current = start;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

Answer 1

Для корректного удаления элемента односвязного списка нужно иметь указатель на предшествующий ему элемент и корректировать в нем указатель на следующий в списке.

Поэтому для поиска и удаления в односвязном списке можно предложить технику, в которой мы используем указатель на указатель в элементе списка. В этом случае для выбора удаляемого элемента надо смотреть не на текущий элемент списка, а на следующий, т.е. на тот, на который указывает поле next в текущем элементе, адресуемое указателем на указатель.

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

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

  {
    cout << "delete negatives\n";
    
    Element **p = &start;  // при удалении первого элемента списка будет корректироваться указатель на список

    while (*p) {
      // если `p` указывает на `next` в текущем элементе списка,
      // то `t` это указатель на следующий за ним.
      // если этот элемент подлежит удалению,
      // то будем корректировать значение `next` в текущем элементе списка
      Element *t = *p;

      if (t->data < 0) {
        *p = t->next;   // корректируем указатель на следующий в списке
        delete t;       // удаляем элемент 
      } else 
        p = &(t->next);  // переходим к следующему элементу в списке
    }
  }

P.S.

Не знаю, кто первый предложил такую технику работы со списками, но в Искусстве Программирования Д. Кнута она рассматривается (для программ на ассемблере).

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

void print_list (Element **plist) {
    for (Element **p = plist; *p; p = &((*p)->next)) {
        cout << (*p)->data << " ";
    }
    cout << endl;
}


...
print_list(&start);
...

БЛОГ НА HUSL

Не могу реализовать удаление элемента односвязного списка

Ответы (1 шт):