Рубрики

Связанный список | Набор 3 (удаление узла)

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

Мы обсуждали введение связанного списка и вставку связанного списка в предыдущих постах в односвязном списке.

Давайте сформулируем постановку задачи, чтобы понять процесс удаления. Получив «ключ», удалите первое вхождение этого ключа в связанном списке .
Чтобы удалить узел из связанного списка, нам нужно выполнить следующие шаги.
1) Найти предыдущий узел удаляемого узла.
2) Изменить следующий из предыдущего узла.
3) Свободная память для удаляемого узла.

Поскольку каждый узел связанного списка динамически выделяется с помощью malloc () в C, нам нужно вызвать free () для освобождения памяти, выделенной для удаляемого узла.

C / C ++

// Полная рабочая программа на C для демонстрации удаления по отдельности
// связанный список
#include <stdio.h>
#include <stdlib.h>

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

struct Node

{

    int data;

    struct Node *next;

};

  
/ * Дана ссылка (указатель на указатель) на заголовок списка

   и int, вставляет новый узел в начало списка. * /

void push(struct Node** head_ref, int new_data)

{

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    new_node->data  = new_data;

    new_node->next = (*head_ref);

    (*head_ref)    = new_node;

}

  
/ * Дана ссылка (указатель на указатель) на заголовок списка

   и ключ, удаляет первое вхождение ключа в связанном списке * /

void deleteNode(struct Node **head_ref, int key)

{

    // Сохранить головной узел

    struct Node* temp = *head_ref, *prev;

  

    // Если головной узел сам содержит ключ для удаления

    if (temp != NULL && temp->data == key)

    {

        *head_ref = temp->next;   // Измененная голова

        free(temp);               // свободная старая голова

        return;

    }

  

    // Поиск ключа для удаления, отслеживание

    // предыдущий узел, так как нам нужно изменить 'prev-> next'

    while (temp != NULL && temp->data != key)

    {

        prev = temp;

        temp = temp->next;

    }

  

    // Если ключ не присутствовал в связанном списке

    if (temp == NULL) return;

  

    // Отключить узел от связанного списка

    prev->next = temp->next;

  

    free(temp);  // Свободная память

}

  
// Эта функция печатает содержимое связанного списка, начиная с
// данный узел

void printList(struct Node *node)

{

    while (node != NULL)

    {

        printf(" %d ", node->data);

        node = node->next;

    }

}

  
/ * Сушилка для тестирования вышеуказанных функций * /

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head = NULL;

  

    push(&head, 7);

    push(&head, 1);

    push(&head, 3);

    push(&head, 2);

  

    puts("Created Linked List: ");

    printList(head);

    deleteNode(&head, 1);

    puts("\nLinked List after Deletion of 1: ");

    printList(head);

    return 0;

}

Джава

// Полная рабочая Java-программа для демонстрации удаления по отдельности
// связанный список

class LinkedList

{

    Node head; // заголовок списка

  

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

    class Node

    {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Учитывая ключ, удаляет первое вхождение ключа в связанном списке * /

    void deleteNode(int key)

    {

        // Сохранить головной узел

        Node temp = head, prev = null;

  

        // Если головной узел сам содержит ключ для удаления

        if (temp != null && temp.data == key)

        {

            head = temp.next; // Измененная голова

            return;

        }

  

        // Поиск ключа для удаления, отслеживание

        // предыдущий узел, так как нам нужно изменить temp.next

        while (temp != null && temp.data != key)

        {

            prev = temp;

            temp = temp.next;

        }    

  

        // Если ключ не присутствовал в связанном списке

        if (temp == null) return;

  

        // Отключить узел от связанного списка

        prev.next = temp.next;

    }

  

    / * Вставляет новый узел в начало списка. * /

    public void push(int new_data)

    {

        Node new_node = new Node(new_data);

        new_node.next = head;

        head = new_node;

    }

  

    / * Эта функция печатает содержимое связанного списка, начиная с

        данный узел * /

    public void printList()

    {

        Node tnode = head;

        while (tnode != null)

        {

            System.out.print(tnode.data+" ");

            tnode = tnode.next;

        }

    }

  

    / * Сушилка для проверки вышеуказанных функций. В идеале эта функция

    должен быть в отдельном пользовательском классе. Он хранится здесь, чтобы сохранить

    компактный код * /

    public static void main(String[] args)

    {

        LinkedList llist = new LinkedList();

  

        llist.push(7);

        llist.push(1);

        llist.push(3);

        llist.push(2);

  

        System.out.println("\nCreated Linked list is:");

        llist.printList();

  

        llist.deleteNode(1); // Удалить узел в позиции 4

  

        System.out.println("\nLinked List after Deletion at position 4:");

        llist.printList();

    }

}

питон

# Python программа для удаления узла из связанного списка

  
# Класс узла

class Node:

  

    # Конструктор для инициализации объекта узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

    # Функция для вставки нового узла в начале

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

    # Учитывая ссылку на заголовок списка и ключ,

    # удалить первое вхождение ключа в связанном списке

    def deleteNode(self, key):

          

        # Хранить головной узел

        temp = self.head

  

        # Если головной узел сам содержит ключ для удаления

        if (temp is not None):

            if (temp.data == key):

                self.head = temp.next

                temp = None

                return

  

        # Поиск ключа, который нужно удалить, следить за

        # предыдущий узел, так как нам нужно изменить 'prev.next'

        while(temp is not None):

            if temp.data == key:

                break 

            prev = temp

            temp = temp.next 

  

        # если ключ отсутствует в связанном списке

        if(temp == None):

            return 

  

        # Отключить узел от связанного списка

        prev.next = temp.next 

  

        temp = None 

  

  

    # Утилита для печати связанного LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print " %d" %(temp.data),

            temp = temp.next

  

  
# Драйверная программа

llist = LinkedList()

llist.push(7)

llist.push(1)

llist.push(3)

llist.push(2)

  

print "Created Linked List: "

llist.printList()

llist.deleteNode(1) 

print "\nLinked List after Deletion of 1:"

llist.printList()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)


Выход:

Created Linked List:
 2  3  1  7
Linked List after Deletion of 1:
 2  3  7

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Связанный список | Набор 3 (удаление узла)

0.00 (0%) 0 votes