Вставка/удаление любого места в связанном списке в C++

Question

Я изучаю C++ некоторое время и только недавно начал просматривать связанные списки. Я могу построить класс класса List с обычными функциями insert/remove из back/front. Теперь я придумал упражнение, которое просит меня написать функцию для обработки вставок/удалений в любом месте списка.

Пожалуйста, имейте в виду, что мои вопросы очень просты.

Проблема у меня есть то, что я вижу вопрос как неоднозначный. Какая информация требуется этой функции? Например, для удаления я могу найти несколько кандидатов: 1) удалить первый узел с определенным значением (аргумент: значение) 2) удалить все узлы с определенным значением (аргумент: значение) 3) удалить конкретный узел (аргумент: указатель на этот узел) 1) и 2) я могу легко закодировать. 3) сложнее, но я тоже могу это сделать. Я просто не вижу смысла в 3). Обычным ли манипулировать узлами (вне определения списка) при использовании списков? Как, например, обычная программа, использующая списки для фактического манипулирования указателями на узлы?

Каково обычное значение «удалить в любом месте» в этой настройке?

Аналогичным образом, для «вставки в любом месте» формулировка является странной. Что означает «где угодно»? Предполагается ли, что место в связанном списке задано конкретным узлом?

Answer 1

В связанном списке у вас есть постоянный доступ к первому элементу. Таким образом, удаление/вставка в любом месте означает место, которое существует между первым и последним элементом. В основном вам нужно иметь 2 итератора. Когда вы найдете место, которое хотите удалить/вставить элемент, вы должны обратиться к объекту непосредственно перед ним. потому что вы не получить доступ к элементу предыдущего, только к следующему: Допустим, наш связанный список выглядит следующим образом:
E0-> E1-> E2-> E3-> E4

Если вы хотите удалите E3, вам нужно установить итератор на E2, чтобы вы могли исправить указатели для E2-> next.

Хорошая ссылка на книгу Стандартная библиотека, написанная Николаем М. Йосуттисом. Проблема, с которой вы столкнулись, широко описывается там.

Answer 2

node*insert(node*head,int d){ 

    node*temp=new node; 
    temp->data=d; 
    if(head==NULL){ 
     temp->next=NULL; 
     head=temp;} 
    else 
     {node*curr=head,*pre=NULL; 
    while (curr!=NULL && curr->data<temp->data) 
    { 
     pre=curr; 
     curr=curr->next; 
    } 
    temp->next=curr; 
    if(pre==NULL) 
     head=temp; 
    pre->next=temp; 
    } 
    return head; 
}