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

Существует три варианта удаления узла из связанного списка:

  1. Удалить из начала.
  2. Удалить из конца.
  3. Удалить из указанной позиции.

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

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

Рис.1 Связанный список

1. Удаление узла из начала:

  • Чтобы удалить первый узел из списка, сделайте указатель temp указывающим на первый узел, скопировав указатель head в указатель temp.

  • Скопируйте часть адреса первого узла, на который указывает temp, в head, обратившись к члену структуры next. Это создает ссылку из head на второй узел в списке.

  • Теперь связь для первого узла, на который указывает temp, нарушена, поэтому освободите это место в памяти с помощью функции free(temp).

  • Отобразите связанный список после удаления.

void deleteFromBeg(struct node ** head)
{
    struct node *temp;
    temp = *head;
    *head = temp->next;
    free(temp);
}
Вход в полноэкранный режим Выход из полноэкранного режима

2. Удаление узла из конца :

  • Сделайте temp указателем на первый узел в списке.

  • Возьмите один указатель prevnode типа struct node для указания на предыдущий узел в списке.

  • Перемещайте temp до последнего узла, используя цикл while, и каждый раз копируйте temp в prevnode. Когда temp указывает на последний узел, prevnode указывает на предпоследний узел.

  • Теперь разорвите связь последнего узла из списка, на который указывает temp, обновив адресную часть узла, на который указывает указатель prevnode, на zero, так как он должен быть последним узлом в списке.

  • Освободите узел, на который указывает указатель temp, используя free(temp) и отобразите связанный список.

void deleteFromEnd(struct node **head, struct node *temp)
{
    struct node *prevnode;
    temp = *head;
    while(temp->next != 0)
    {
        prevnode = temp;
        temp = temp->next;
    }
    if(temp == *head)
        *head = 0;
    else
         prevnode->next = 0;
         free(temp);     
}
Войти в полноэкранный режим Выход из полноэкранного режима

3. Удаление узла из указанной позиции :

  • Введите позицию, после которой узел должен быть вставлен в список, и сохраните значение этой позиции в любой переменной типа int. Здесь переменная position принимается за pos.

  • Если pos (введенная позиция) больше, чем количество узлов в связанном списке, то выведите invalid position.

  • Если pos (введенная позиция) меньше количества узлов в связанном списке, то сделайте temp первым узлом.

  • Переместите temp из первого узла в тот узел, позиция которого равна pos-1, используя цикл while.

  • Возьмите один указатель nextnode типа struct node и сделайте его указывающим на узел (который вы хотите удалить) путем копирования части адреса узла, на который указывает temp.

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

  • Чтобы удалить узел из списка, создайте ссылку от узла, расположенного непосредственно перед узлом, который вы хотите удалить, к узлу, расположенному сразу после узла указанной позиции (pos). Ссылка создается следующим образом,
temp->next = nextnode->next;
Войти в полноэкранный режим Выйти из полноэкранного режима
  • Освободите nextnode, указывающий на узел, который вы хотите удалить, и отобразите связанный список.
void deleteFromPos(struct node *head, struct node *temp, int count)
{
    struct node *nextnode;
    int pos, i=1;
    printf("Enter the position : ");
    scanf("%d", &pos);
    if(pos>count)
    {
        printf("Invalid position.");
        exit(0);
    }
    else
    {
      temp = head;
      while(i < pos-1)
      {
        temp=temp->next;
        i++;
      }
      nextnode = temp->next;
      temp->next = nextnode->next;
      free(nextnode);
    } 
}
Войти в полноэкранный режим Выход из полноэкранного режима

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

#include <stdio.h>
#include <stdlib.h> 

struct node
{
    int data;
    struct node * next;
};

int displayLL(struct node * head)
{
    int num = 0;
    struct node * temp;
    temp = head;
    temp=head;
    while(temp!=0)
    {
       printf("%d ",temp->data);
       temp = temp->next;
       num++;
    }
return num;
}

void deleteFromBeg(struct node * * head)
{
    struct node * temp;
    temp = * head;
    * head = temp->next;
    free(temp);
}

void deleteFromEnd(struct node **head, struct node *temp)
{
    struct node *prevnode;
    temp = *head;
    while(temp->next != 0)
    {
        prevnode = temp;
        temp = temp->next;
    }
    if(temp == *head)
        *head = 0;
    else
         prevnode->next = 0;
      free(temp);     
}

void deleteFromPos(struct node *head, struct node *temp, int count)
{
    struct node *nextnode;
    int pos, i=1;
    printf("Enter the position : ");
    scanf("%d", &pos);
    if(pos>count)
    {
        printf("Invalid position.");
        exit(0);
    }
    else
    {
       temp = head;
       while(i < pos-1)
       {
          temp=temp->next;
          i++;
       }
       nextnode = temp->next;
       temp->next = nextnode->next;
       free(nextnode);
    } 
}

int main()
{
   struct node *head = 0, *newnode, *temp; 
   int n, choice, newdata;

// Create Linked List // 

   printf("Enter the number of nodes in the list : ");
   scanf("%d", &n);
   for(int i = 1; i<=n; i++)
   {
     newnode = (struct node *)malloc(sizeof(struct node));
     printf("Enter the data%d : ", i);
     scanf("%d", &newnode->data);
     newnode->next = 0;
     if(head == 0)
     {
        head = temp = newnode;
     } 
     else
       { 
        temp->next = newnode;
        temp = newnode;
       }
    }
   printf("--------------------------------n");
   printf("Linked list : ");
   int count = displayLL(head);
   printf("nCount = %d", count);

   printf("nEnter '1' for deleting node from beginning.nEnter '2' for deleting node from end.nEnter '3' for deleting after given position.n");
   scanf("%d", &choice);

   switch(choice)
   {
      case 1:
      {
         deleteFromBeg(&head);
         printf("nLinked list after deleting a node from beginning : ");
         int count = displayLL(head);
                 break;
      }
      case 2:
      {
         deleteFromEnd(&head, temp);
         printf("nLinked list after deleting a node from end : ");
         int count = displayLL(head);
                 break;
      }
      case 3:
      {
         deleteFromPos(head, temp, count);
         printf("nLinked list after deleting a node from specified pos : ");
         int count = displayLL(head);
                 break;
      }
   }
}
Вход в полноэкранный режим Выход из полноэкранного режима

У меня есть сайт www.coderlogs.com, где я пишу подобные блоги, так что заходите на этот сайт, чтобы узнать больше подобных статей.

Оцените статью
Procodings.ru
Добавить комментарий