Рубрики

Удалить узел в двусвязном списке

Двойной список ссылок Set 1 | Введение и вставка

Напишите функцию для удаления данного узла в двусвязном списке.

     (a) Original Doubly Linked List

     (a) After deletion of head node

     (a) After deletion of middle node

     (a) After deletion of last node

Алгоритм
Пусть удаляемый узел — это del .
1) Если удаляемый узел является головным узлом, измените указатель заголовка на следующий текущий заголовок.
2) Установите следующий из предыдущих в del , если предыдущий в del существует.
3) Установите prev рядом с del , если рядом с del существует.

C ++

// C ++ программа для удаления узла из
// Двусвязный список
#include <bits/stdc++.h>

using namespace std;

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

class Node 

    public:

    int data; 

    Node* next; 

    Node* prev; 

}; 

  
/ * Функция для удаления узла в двусвязном списке.
head_ref -> указатель на указатель главного узла.
del -> указатель на удаляемый узел. * /

void deleteNode(Node** head_ref, Node* del) 

    /* базовый вариант */

    if (*head_ref == NULL || del == NULL) 

        return

  

    / * Если удаляемый узел является головным узлом * /

    if (*head_ref == del) 

        *head_ref = del->next; 

  

    / * Изменить следующий, только если узел будет

    удалено НЕ последний узел * /

    if (del->next != NULL) 

        del->next->prev = del->prev; 

  

    / * Изменить предыдущий, только если узел должен быть

    удалено НЕ первый узел * /

    if (del->prev != NULL) 

        del->prev->next = del->next; 

  

    / * Наконец, освободите память, занятую del * /

    free(del); 

    return

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла в
начало двусвязного списка * /

void push(Node** head_ref, int new_data) 

    / * выделить узел * /

    Node* new_node = new Node();

  

    / * вставить данные * /

    new_node->data = new_data; 

  

    / * так как мы добавляем в начале,

    prev всегда NULL * /

    new_node->prev = NULL; 

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref); 

  

    / * изменить prev головного узла на новый узел * /

    if ((*head_ref) != NULL) 

        (*head_ref)->prev = new_node; 

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node; 

  
/ * Функция для печати узлов в заданном двусвязном списке
Эта функция аналогична printList () односвязного списка * /

void printList(Node* node) 

    while (node != NULL) 

    

        cout << node->data << " "

        node = node->next; 

    

  
/ * Код водителя * /

int main() 

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

    Node* head = NULL; 

  

    / * Давайте создадим двусвязный список 10 <-> 8 <-> 4 <-> 2 * /

    push(&head, 2); 

    push(&head, 4); 

    push(&head, 8); 

    push(&head, 10); 

  

    cout << "Original Linked list "

    printList(head); 

  

    / * удалить узлы из двусвязного списка * /

    deleteNode(&head, head); / * удалить первый узел * /

    deleteNode(&head, head->next); / * удалить средний узел * /

    deleteNode(&head, head->next); / * удалить последний узел * /

  

    / * Измененный связанный список будет NULL <-8-> NULL * /

    cout << "\nModified Linked list "

    printList(head); 

  

    return 0;

  
// Этот код предоставлен rathbhupendra

С

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

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

struct Node {

    int data;

    struct Node* next;

    struct Node* prev;

};

  
/ * Функция для удаления узла в двусвязном списке.

   head_ref -> указатель на указатель главного узла.

   del -> указатель на удаляемый узел. * /

void deleteNode(struct Node** head_ref, struct Node* del)

{

    /* базовый вариант */

    if (*head_ref == NULL || del == NULL)

        return;

  

    / * Если удаляемый узел является головным узлом * /

    if (*head_ref == del)

        *head_ref = del->next;

  

    / * Изменить следующий, только если удаляемый узел НЕ является последним узлом * /

    if (del->next != NULL)

        del->next->prev = del->prev;

  

    / * Изменить prev только если удаляемый узел НЕ является первым узлом * /

    if (del->prev != NULL)

        del->prev->next = del->next;

  

    / * Наконец, освободите память, занятую del * /

    free(del);

    return;

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла в начало двусвязного списка * /

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

{

    / * выделить узел * /

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

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * так как мы добавляем в начале,

    prev всегда NULL * /

    new_node->prev = NULL;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * изменить prev головного узла на новый узел * /

    if ((*head_ref) != NULL)

        (*head_ref)->prev = new_node;

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node;

}

  
/ * Функция для печати узлов в заданном двусвязном списке

   Эта функция аналогична printList () односвязного списка * /

void printList(struct Node* node)

{

    while (node != NULL) {

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

        node = node->next;

    }

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

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

    struct Node* head = NULL;

  

    / * Давайте создадим двусвязный список 10 <-> 8 <-> 4 <-> 2 * /

    push(&head, 2);

    push(&head, 4);

    push(&head, 8);

    push(&head, 10);

  

    printf("\n Original Linked list ");

    printList(head);

  

    / * удалить узлы из двусвязного списка * /

    deleteNode(&head, head); / * удалить первый узел * /

    deleteNode(&head, head->next); / * удалить средний узел * /

    deleteNode(&head, head->next); / * удалить последний узел * /

  

    / * Измененный связанный список будет NULL <-8-> NULL * /

    printf("\n Modified Linked list ");

    printList(head);

  

    getchar();

}

Джава

// Java программа для удаления узла из
// Двусвязный список

  
// Класс для двусвязного списка

public class DLL {

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

  

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

    class Node {

        int data;

        Node prev;

        Node next;

  

        // Конструктор для создания нового узла

        // next и prev по умолчанию инициализируются

        // как ноль

        Node(int d) { data = d; }

    }

  

    // Добавление узла в начало списка

    public void push(int new_data)

    {

        // 1. выделить узел

        // 2. вставить данные

        Node new_Node = new Node(new_data);

  

        // 3. Сделать следующий из нового узла в качестве головы

        // и предыдущий как NULL

        new_Node.next = head;

        new_Node.prev = null;

  

        // 4. меняем предысторию головного узла на новый

        if (head != null)

            head.prev = new_Node;

  

        // 5. перемещаем голову, чтобы указать на новый узел

        head = new_Node;

    }

  

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

    // начиная с данного узла

    public void printlist(Node node)

    {

        Node last = null;

  

        while (node != null) {

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

            last = node;

            node = node.next;

        }

  

        System.out.println();

    }

  

    // Функция для удаления узла в двусвязном списке.

    // head_ref -> указатель на указатель главного узла.

    // del -> данные удаляемого узла.

    void deleteNode(Node head_ref, Node del)

    {

  

        // Базовый вариант

        if (head == null || del == null) {

            return;

        }

  

        // Если удаляемый узел является головным узлом

        if (head == del) {

            head = del.next;

        }

  

        // Изменить следующий, только если удаляемый узел

        // НЕ последний узел

        if (del.next != null) {

            del.next.prev = del.prev;

        }

  

        // Изменить prev только если удаляемый узел

        // НЕ первый узел

        if (del.prev != null) {

            del.prev.next = del.next;

        }

  

        // Наконец, освобождаем память, занятую del

        return;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

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

        DLL dll = new DLL();

  

        // Вставить 2. Таким образом, связанный список становится 2-> NULL

        dll.push(2);

  

        // Вставить 4. Таким образом, связанный список становится 4-> 2-> NULL

        dll.push(4);

  

        // Вставка 8. Таким образом, связанный список становится 8-> 4-> 2-> NULL

        dll.push(8);

  

        // Вставка 10. Таким образом, связанный список становится 10-> 8-> 4-> 2-> NULL

        dll.push(10);

  

        System.out.print("Created DLL is: ");

        dll.printlist(dll.head);

  

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

        dll.deleteNode(dll.head, dll.head);

  

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

        // 8-> 4-> 2

        System.out.print("\nList after deleting first node: ");

        dll.printlist(dll.head);

  

        // Удаление среднего узла из 8-> 4-> 2

        dll.deleteNode(dll.head, dll.head.next);

  

        System.out.print("\nList after Deleting middle node: ");

        dll.printlist(dll.head);

    }

}

питон

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

  
# для сборки мусора

import gc

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

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data 

        self.next = None

        self.prev = None

  

class DoublyLinkedList:

     # Конструктор для пустого двусвязного списка

    def __init__(self):

        self.head = None

   

   # Функция для удаления узла в двусвязном списке.

   # head_ref -> указатель на указатель главного узла.

   # delete -> указатель на удаляемый узел

  

    def deleteNode(self, dele):

          

        # Базовый вариант

        if self.head is None or dele is None:

            return 

          

        # Если удаляемый узел является головным узлом

        if self.head == dele:

            self.head = dele.next

  

        # Изменять следующее, только если удаляемый узел НЕ

        # последний узел

        if dele.next is not None:

            dele.next.prev = dele.prev

      

        # Изменить prev, только если удаляемый узел НЕ

        # первый узел

        if dele.prev is not None:

            dele.prev.next = dele.next

        # Наконец, освободите память, занятую удалением

        # Вызвать Python сборщик мусора

        gc.collect()

  

  

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

    # integer вставляет новый узел в начало списка

    def push(self, new_data):

   

        # 1. Распределяет узел

        # 2. Поместите в него данные

        new_node = Node(new_data)

   

        # 3. Сделать следующий из нового узла в качестве головы и

        # предыдущий как None (уже None)

        new_node.next = self.head

   

        # 4. измените prev главного узла на new_node

        if self.head is not None:

            self.head.prev = new_node

   

        # 5. переместить голову, чтобы указать на новый узел

        self.head = new_node

  

  

    def printList(self, node):

        while(node is not None):

            print node.data,

            node = node.next

  

  
# Драйвер программы для проверки вышеуказанных функций

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

dll = DoublyLinkedList()

  
# Давайте создадим двусвязный список 10 <-> 8 <-> 4 <-> 2

dll.push(2);

dll.push(4);

dll.push(8);

dll.push(10);

  

print "\n Original Linked List",

dll.printList(dll.head)

  
# удалить узлы из двусвязного списка
dll.deleteNode(dll.head)

dll.deleteNode(dll.head.next)

dll.deleteNode(dll.head.next)

# Измененный связанный список будет NULL <-8-> NULL

print "\n Modified Linked List",

dll.printList(dll.head)

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

C #

// C # программа для удаления узла из
// Двусвязный список

using System;

  
// Класс для двусвязного списка

public class DLL 

{

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

  

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

    public class Node 

    {

        public int data;

        public Node prev;

        public Node next;

  

        // Конструктор для создания нового узла

        // следующий и предыдущий по умолчанию

        // инициализируется как ноль

        public Node(int d) { data = d; }

    }

  

    // Добавление узла в начало списка

    public void push(int new_data)

    {

        // 1. выделить узел

        // 2. вставить данные

        Node new_Node = new Node(new_data);

  

        // 3. Сделать следующий из нового узла в качестве головы

        // и предыдущий как NULL

        new_Node.next = head;

        new_Node.prev = null;

  

        // 4. меняем предысторию головного узла на новый

        if (head != null)

            head.prev = new_Node;

  

        // 5. перемещаем голову, чтобы указать на новый узел

        head = new_Node;

    }

  

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

    // начиная с данного узла

    public void printlist(Node node)

    {

        Node last = null;

  

        while (node != null)

        {

            Console.Write(node.data + " ");

            last = node;

            node = node.next;

        }

  

        Console.WriteLine();

    }

  

    // Функция для удаления узла в двусвязном списке.

    // head_ref -> указатель на указатель главного узла.

    // del -> данные удаляемого узла.

    void deleteNode(Node head_ref, Node del)

    {

  

        // Базовый вариант

        if (head == null || del == null

        {

            return;

        }

  

        // Если удаляемый узел является головным узлом

        if (head == del) 

        {

            head = del.next;

        }

  

        // Изменить следующий, только если удаляемый узел

        // НЕ последний узел

        if (del.next != null

        {

            del.next.prev = del.prev;

        }

  

        // Изменить prev только если удаляемый узел

        // НЕ первый узел

        if (del.prev != null

        {

            del.prev.next = del.next;

        }

  

        // Наконец, освобождаем память, занятую del

        return;

    }

  

    // Код драйвера

    public static void Main()

    {

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

        DLL dll = new DLL();

  

        // Вставить 2. Таким образом, связанный список становится 2-> NULL

        dll.push(2);

  

        // Вставить 4. Таким образом, связанный список становится 4-> 2-> NULL

        dll.push(4);

  

        // Вставка 8. Таким образом, связанный список становится 8-> 4-> 2-> NULL

        dll.push(8);

  

        // Вставка 10. Таким образом, связанный список становится 10-> 8-> 4-> 2-> NULL

        dll.push(10);

  

        Console.Write("Created DLL is: ");

        dll.printlist(dll.head);

  

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

        dll.deleteNode(dll.head, dll.head);

  

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

        // 8-> 4-> 2

        Console.Write("\nList after deleting first node: ");

        dll.printlist(dll.head);

  

        // Удаление среднего узла из 8-> 4-> 2

        dll.deleteNode(dll.head, dll.head.next);

  

        Console.Write("\nList after Deleting middle node: ");

        dll.printlist(dll.head);

    }

}

  
// Этот код предоставлен PrinciRaj1992

Выход:

Original Linked list 10 8 4 2 
 Modified Linked list 8

Сложность времени: O (1)

Пожалуйста, пишите комментарии, если вы обнаружите, что какой-либо из приведенных выше кодов / алгоритмов неверен, или найдете лучшие способы решения той же проблемы

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

Удалить узел в двусвязном списке

0.00 (0%) 0 votes