C - Удаление узла, когда в одном связанном списке только 1 элемент

Question

Эй, ребята, так что я понимаю, что для удаления узлов, когда в связанном списке есть несколько элементов, вы берете предыдущий узел из текущего узла, который вы хотите удалить, и указываете на current->next, а затем вы free() текущий узел.

Но моя проблема в том, что когда у меня есть только один элемент в одном связанном списке, при попытке удалить узел возникает ошибка сегментации (дамп ядра), я предполагаю, что это так, потому что в этом сценарии current->next будет указывать на NULL (я могу ошибаться здесь). Также допустим, что у меня есть узел, в котором хранится значение 5, часто встречающаяся проблема - вместо удаления узла он меняет значение на 0.

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

Большое спасибо за вашу помощь, я извиняюсь, если что-то неясно, но я действительно хотел сначала дать контекст, прежде чем задавать мой вопрос.

Answer 1

1: если элемент является головой.

   nodeptr deleteBeginning(nodeptr head){
        nodeptr current = head;
        head= head->next;
        free(current);
        return head;
   }

2: для остальных элементов.

   nodeptr deleteNode(nodeptr head, int value){
    if(value == head->data) {
        head = deleteBeginning(head);
        return head;
    }

    nodeptr current = head;
    nodeptr previous;

    while(current->data != value){
        previous = current;
        current = current->next;
    }

    previous->next = current->next;
    free(current);
    return head;
   }

nodeptr - это просто typedef для struct Node *

Answer 2

Когда вы удаляете узел, который является , а не , для первого узла выполняются шаги

1) previous_node->next = node_to_delete->next;

2) free(node_to_delete)

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

3) head = node_to_delete->next;

Это может быть реализовано многими способами. Например что-то вроде:

node* delete(node* head, int n)
{
    node* prev = NULL;
    node* temp = head;

    while (temp)
    {
        if (temp->value == n) 
        {
            if (prev)
            {
                // All except first node
                prev->next = temp->next;
            }
            else
            {
                // First node
                head = temp->next;
            }
            free(temp);
            return head;
        }
        prev = temp;
        temp = temp->next;
    }

    return head;
}

и назовите это как:

head = delete(head, 42);

Answer 3

Это полностью зависит от вашей реализации связанного списка.

Возможно несколько возможных реализаций.

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

В зависимости от структуры списка реализация может отличаться.

На общем основании можно сказать, что вы начинаете с указателя H, который указывает на элемент E, и этот элемент имеет next указатель на преемника S.

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

В самой простой форме (непроверенный / некомпилированный код - должен просто показывать принцип):

typedef struct ListNode{
  void* data,
  struct ListNode* next;
}ListNode;

/**
  *  \brief  removes an element from the linked list 
  *
  *  \param  io_el  the 'next' pointer of the previous 
  *                 element or the pointer to the head
  *  \return the pointer to the removed element
  *  
  *  \details
  *  uses the io_el pointer to advance to the next list element and 
  *  sets the io_el pointer to the content of the next pointer of
  *  this element. This effectivly removes the element from the chain.
  *  The removed element is returned so that it may be free'd if necessary. 
  */
Node* ListDeleteElement(Node** io_el){
  Node* res = NULL;
  if( io_el && *io_el){
    res = *io_el;
    *io_el = (*io_el)->next;
  }
}

с учетом следующего списка.

Node E1 ,E2,E3;
Node* H = &E1;
E1.next = &E2;
E2.next = &E3;
E3.next = NULL;

// (H = ) E1 -> E2 -> E3 -> NULL

// remove E3;
ListDeleteElement( &(H->next->next) ); // passes pointer to the nextpointer of E2, 
// E2.next should be NULL now
// (H = ) E1 -> E2 -> NULL

// remove E1
ListDeleteElement( &H ); 
// *H should now be E2
// (H = ) E2 -> NULL

// again remove first element
ListDeleteElement( &H ); 
// (H = ) NULL

Эта реализация опасна - абсолютно необходимо, чтобы переданный указатель являлся указателем на голову или указателем на next указатель фактического элемента списка.

Передача адресов произвольного указателя в структуру списка приводит к повреждению списка.

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

Answer 4

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

Обе могут быть обработаны так:

typedef struct node {
    int val;
    struct node *next;
} node;

void deleteNode(node **head, int value) {
    node *prev = NULL, *curr = *head;

    // look for the node to delete
    while (curr && curr->value != value) {
        prev = curr;
        curr = curr->next;
    }

    if (curr == NULL) {
        printf("node to delete not found\n");
    } else if (prev == NULL) {
        // need to delete the first node, so repoint head to next node
        *head = (*head)->next;
    } else {
        // deleting an internal node, so have the previous point to the current's next
        prev->next = curr->next;
    }
    // no need to check for the last node 
    // since we're copying next which may or may not be NULL

    free(curr);
}

Answer 5

Ваш "связанный список" - это просто указатель на первый элемент вашего списка.

MyStruct *my_list;

Итак, если my_list-> next равно нулю, это означает, что в вашем списке только один элемент. Если вы хотите удалить его, это просто:

free(my_list)
my_list = NULL;

Ваш список теперь пуст (не пытайтесь прочитать это;))

Answer 6

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

A) Удаление первого узла

Алгоритм:

Step1: temp = head
Step2: temp = temp->next
Step3: free(temp)
Step4: head = NULL

B) Удаление последнего узла

Алгоритм

Step1: p = head
Step2: while p->next->next != NULL 
         p = p->next
Step3: temp = p->next
Step4: p->next = NULL
Step5: free(temp)

C) Удаление узла между ними.

Алгоритм:

Step1: p = head
Step2: while POSITION > 2 #Indexing from 1
         p = p->next
         POSITION = POSITION - 1
Step3: temp = p->next
Step4: p->next = p->next->next
Step5: free(temp)