Рубрики

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

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

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

Алгоритм

Случай 1: Пустой список (начало = NULL)

  • Если список пуст, просто вернитесь.

Случай 2: список изначально содержит несколько узлов, начальные точки указывают на первый узел списка

  1. Если список не пустой , то мы определяем два указателя Тек и prev_1 и инициализировать указатель указывает ТОК на первый узел списка и prev_1 = NULL.
  2. Траверса список с помощью указателя Тек , чтобы найти узел , который необходимо удалить , и , прежде чем перейти к следующему Curr узла, каждый раз , когда устанавливается prev_1 = ТОК.
  3. Если узел найден, проверьте, является ли он единственным узлом в списке. Если да, то уставка пуска = NULL и освободить узел , указывающий на Curr.
  4. Если в списке более одного узла, проверьте, является ли он первым узлом списка. Условие проверить это (curr == начало). Если да, то переместите prev_1 к последнему узлу (prev_1 = start -> prev). После того, как prev_1 достигнет последнего узла, установите start = start -> next и prev_1 -> next = start и start -> prev = prev_1. Освободите узел, указывающий курсором.
  5. Если curr не первый узел, мы проверяем, является ли он последним узлом в списке. Условие проверить это (curr -> next == start). Если да, установите prev_1 -> next = start и start -> prev = prev_1. Освободите узел, указывающий курсором.
  6. Если удаляемый узел не является ни первым, ни последним узлом, объявите еще один указатель temp и инициализируйте временные точки указателя следующим указателем curr (temp = curr-> next). Теперь установите, prev_1 -> next = temp и temp -> prev = prev_1. Освободите узел, указывающий курсором.
  • Если данный ключ (скажем, 4) совпадает с первым узлом списка (шаг 4):
  • Если данный ключ (скажем, 8) совпадает с последним узлом списка (шаг 5):
  • Если данный ключ (скажем 6) совпадает со средним узлом списка (шаг 6):

C ++

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

using namespace std;

  
// Структура узла

struct Node {

    int data;

    struct Node* next;

    struct Node* prev;

};

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

void insert(struct Node** start, int value)

{

    // Если список пуст, создать отдельный узел

    // круговой и двойной список

    if (*start == NULL) {

        struct Node* new_node = new Node;

        new_node->data = value;

        new_node->next = new_node->prev = new_node;

        *start = new_node;

        return;

    }

  

    // Если список не пуст

  

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

    Node* last = (*start)->prev;

  

    // Создать узел динамически

    struct Node* new_node = new Node;

    new_node->data = value;

  

    // Начало будет следующим из new_node

    new_node->next = *start;

  

    // Сделать новый узел предшествующим началу

    (*start)->prev = new_node;

  

    // Сделать последний предшествующий новый узел

    new_node->prev = last;

  

    // Сделать новый узел следующим за старым последним

    last->next = new_node;

}

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

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

{

    // Если список пуст

    if (*start == NULL)

        return;

  

    // Находим нужный узел

    // Объявляем два указателя и инициализируем их

    struct Node *curr = *start, *prev_1 = NULL;

    while (curr->data != key) {

        // Если узел отсутствует в списке

        if (curr->next == *start) {

            printf("\nList doesn't have node with value = %d", key);

            return;

        }

  

        prev_1 = curr;

        curr = curr->next;

    }

  

    // Проверяем, является ли узел единственным узлом в списке

    if (curr->next == *start && prev_1 == NULL) {

        (*start) = NULL;

        free(curr);

        return;

    }

  

    // Если список имеет более одного узла,

    // проверяем, является ли это первым узлом

    if (curr == *start) {

        // Переместить prev_1 к последнему узлу

        prev_1 = (*start)->prev;

  

        // Двигаться вперед

        *start = (*start)->next;

  

        // Корректируем указатели prev_1 и начального узла

        prev_1->next = *start;

        (*start)->prev = prev_1;

        free(curr);

    }

  

    // проверяем, является ли это последним узлом

    else if (curr->next == *start) {

        // Корректируем указатели prev_1 и начального узла

        prev_1->next = *start;

        (*start)->prev = prev_1;

        free(curr);

    }

    else {

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

        struct Node* temp = curr->next;

  

        // Корректируем указатели на prev_1 и временный узел

        prev_1->next = temp;

        temp->prev = prev_1;

        free(curr);

    }

}

  
// Функция для отображения элементов списка

void display(struct Node* start)

{

    struct Node* temp = start;

  

    while (temp->next != start) {

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

        temp = temp->next;

    }

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

}

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

int main()

{

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

    struct Node* start = NULL;

  

    // Созданный связанный список будет 4-> 5-> 6-> 7-> 8

    insert(&start, 4);

    insert(&start, 5);

    insert(&start, 6);

    insert(&start, 7);

    insert(&start, 8);

  

    printf("List Before Deletion: ");

    display(start);

  

    // Удалить узел, которого нет в списке

    deleteNode(&start, 9);

    printf("\nList After Deletion: ");

    display(start);

  

    // Удалить первый узел

    deleteNode(&start, 4);

    printf("\nList After Deleting %d: ", 4);

    display(start);

  

    // Удалить последний узел

    deleteNode(&start, 8);

    printf("\nList After Deleting %d: ", 8);

    display(start);

  

    // Удалить средний узел

    deleteNode(&start, 6);

    printf("\nList After Deleting %d: ", 6);

    display(start);

  

    return 0;

}

Джава

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

class GFG {

  

    // структура узла

    static class Node {

        int data;

        Node next;

        Node prev;

    };

  

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

    static Node insert(Node start, int value)

    {

        // Если список пуст, создать отдельный узел

        // круговой и двойной список

        if (start == null) {

            Node new_node = new Node();

            new_node.data = value;

            new_node.next = new_node.prev = new_node;

            start = new_node;

            return start;

        }

  

        // Если список не пуст

  

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

        Node last = (start).prev;

  

        // Создать узел динамически

        Node new_node = new Node();

        new_node.data = value;

  

        // Начало будет следующим из new_node

        new_node.next = start;

  

        // Сделать новый узел предшествующим началу

        (start).prev = new_node;

  

        // Сделать последний предшествующий новый узел

        new_node.prev = last;

  

        // Сделать новый узел следующим за старым последним

        last.next = new_node;

        return start;

    }

  

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

    static Node deleteNode(Node start, int key)

    {

        // Если список пуст

        if (start == null)

            return null;

  

        // Находим нужный узел

        // Объявляем два указателя и инициализируем их

        Node curr = start, prev_1 = null;

        while (curr.data != key) {

            // Если узел отсутствует в списке

            if (curr.next == start) {

                System.out.printf("\nList doesn't have node with value = %d", key);

                return start;

            }

  

            prev_1 = curr;

            curr = curr.next;

        }

  

        // Проверяем, является ли узел единственным узлом в списке

        if (curr.next == start && prev_1 == null) {

            (start) = null;

            return start;

        }

  

        // Если список имеет более одного узла,

        // проверяем, является ли это первым узлом

        if (curr == start) {

            // Переместить prev_1 к последнему узлу

            prev_1 = (start).prev;

  

            // Двигаться вперед

            start = (start).next;

  

            // Корректируем указатели prev_1 и начального узла

            prev_1.next = start;

            (start).prev = prev_1;

        }

  

        // проверяем, является ли это последним узлом

        else if (curr.next == start) {

            // Корректируем указатели prev_1 и начального узла

            prev_1.next = start;

            (start).prev = prev_1;

        }

        else {

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

            Node temp = curr.next;

  

            // Корректируем указатели на prev_1 и временный узел

            prev_1.next = temp;

            temp.prev = prev_1;

        }

        return start;

    }

  

    // Функция для отображения элементов списка

    static void display(Node start)

    {

        Node temp = start;

  

        while (temp.next != start) {

            System.out.printf("%d ", temp.data);

            temp = temp.next;

        }

        System.out.printf("%d ", temp.data);

    }

  

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

    public static void main(String args[])

    {

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

        Node start = null;

  

        // Созданный связанный список будет 4.5.6.7.8

        start = insert(start, 4);

        start = insert(start, 5);

        start = insert(start, 6);

        start = insert(start, 7);

        start = insert(start, 8);

  

        System.out.printf("List Before Deletion: ");

        display(start);

  

        // Удалить узел, которого нет в списке

        start = deleteNode(start, 9);

        System.out.printf("\nList After Deletion: ");

        display(start);

  

        // Удалить первый узел

        start = deleteNode(start, 4);

        System.out.printf("\nList After Deleting %d: ", 4);

        display(start);

  

        // Удалить последний узел

        start = deleteNode(start, 8);

        System.out.printf("\nList After Deleting %d: ", 8);

        display(start);

  

        // Удалить средний узел

        start = deleteNode(start, 6);

        System.out.printf("\nList After Deleting %d: ", 6);

        display(start);

    }

}

  
// Этот код предоставлен Арнабом Кунду

python3

# Python3 программа для удаления данного ключа из
# круговой двусвязный список.

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

class Node: 

    def __init__(self, data): 

        self.data = data 

        self.next = None

        self.prev = None

  

def insert( start, value):

      

    # Если список пуст, создайте один узел

    # круговой и двукратный список

    if (start == None): 

        new_node = Node(0)

        new_node.data = value

        new_node.next = new_node.prev = new_node

        start = new_node

        return start

          

    # Если список не пуст

  

    # Найти последний узел /

    last = (start).prev

  

    # Создать узел динамически

    new_node = Node(0)

    new_node.data = value

  

    # Начало будет следующим из new_node

    new_node.next = start

  

    # Сделать новый узел предшествующим началу

    (start).prev = new_node

  

    # Сделать последний предшествующий новый узел

    new_node.prev = last

  

    # Сделать новый узел следующим за старым последним

    last.next = new_node

    return start

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

def deleteNode(start, key):

      

    # Если список пуст

    if (start == None):

        return None

  

    # Найти нужный узел

    # Объявить два указателя и инициализировать их

    curr = start

    prev_1 = None

    while (curr.data != key) :

          

        # Если узел отсутствует в списке

        if (curr.next == start) :

            print ("List doesn't have node"

                       "with value = ", key)

            return start

              

        prev_1 = curr

        curr = curr.next

          

    # Проверьте, является ли узел единственным узлом в списке

    if (curr.next == start and prev_1 == None) :

        (start) = None

        return start

          

    # Если список имеет более одного узла,

    # проверить, если это первый узел

    if (curr == start) :

          

        # Переместить prev_1 к последнему узлу

        prev_1 = (start).prev

  

        # Двигаться вперед

        start = (start).next

  

        # Отрегулируйте указатели prev_1

        # и начальный узел

        prev_1.next = start

        (start).prev = prev_1

          

    # проверить, если это последний узел

    elif (curr.next == start) :

          

        # Отрегулируйте указатели prev_1

        # и начальный узел

        prev_1.next = start

        (start).prev = prev_1

          

    else :

          

        # создать новый указатель,

        # указывает на следующий узел curr

        temp = curr.next

  

        # Отрегулируйте указатели prev_1

        # и временный узел

        prev_1.next = temp

        temp.prev = prev_1

          

    return start

      
# Функция для отображения элементов списка

def display(start):

      

    temp = start

  

    while (temp.next != start) :

        print (temp.data, end = " "

        temp = temp.next

          

    print (temp.data)

      
Код водителя

if __name__=='__main__'

      

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

    start = None

  

    # Созданный связанный список будет 4.5.6.7.8

    start = insert(start, 4)

    start = insert(start, 5)

    start = insert(start, 6)

    start = insert(start, 7)

    start = insert(start, 8)

  

    print ("List Before Deletion: ")

    display(start)

  

    # Удалить узел, которого нет в списке

    start = deleteNode(start, 9)

    print ("List After Deletion: ")

    display(start)

  

    # Удалить первый узел

    start = deleteNode(start, 4)

    print ("List After Deleting", 4)

    display(start)

  

    # Удалить последний узел

    start = deleteNode(start, 8)

    print ("List After Deleting ", 8)

    display(start)

  

    # Удалить средний узел

    start = deleteNode(start, 6)

    print ("List After Deleting ", 6)

    display(start)

      
# Этот код предоставлен Арнабом Кунду

C #

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

using System;

  

class GFG {

  

    // структура узла

    public class Node {

        public int data;

        public Node next;

        public Node prev;

    };

  

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

    static Node insert(Node start, int value)

    {

        // Если список пуст, создать отдельный узел

        // круговой и двойной список

        Node new_node = new Node();

        if (start == null) {

  

            new_node.data = value;

            new_node.next = new_node.prev = new_node;

            start = new_node;

            return start;

        }

  

        // Если список не пуст

  

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

        Node last = (start).prev;

  

        // Создать узел динамически

        new_node = new Node();

        new_node.data = value;

  

        // Начало будет следующим из new_node

        new_node.next = start;

  

        // Сделать новый узел предшествующим началу

        (start).prev = new_node;

  

        // Сделать последний предшествующий новый узел

        new_node.prev = last;

  

        // Сделать новый узел следующим за старым последним

        last.next = new_node;

        return start;

    }

  

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

    static Node deleteNode(Node start, int key)

    {

        // Если список пуст

        if (start == null)

            return null;

  

        // Находим нужный узел

        // Объявляем два указателя и инициализируем их

        Node curr = start, prev_1 = null;

        while (curr.data != key) {

            // Если узел отсутствует в списке

            if (curr.next == start) {

                Console.Write("\nList doesn't have node with value = {0}", key);

                return start;

            }

  

            prev_1 = curr;

            curr = curr.next;

        }

  

        // Проверяем, является ли узел единственным узлом в списке

        if (curr.next == start && prev_1 == null) {

            (start) = null;

            return start;

        }

  

        // Если список имеет более одного узла,

        // проверяем, является ли это первым узлом

        if (curr == start) {

            // Переместить prev_1 к последнему узлу

            prev_1 = (start).prev;

  

            // Двигаться вперед

            start = (start).next;

  

            // Корректируем указатели prev_1 и начального узла

            prev_1.next = start;

            (start).prev = prev_1;

        }

  

        // проверяем, является ли это последним узлом

        else if (curr.next == start) {

            // Корректируем указатели prev_1 и начального узла

            prev_1.next = start;

            (start).prev = prev_1;

        }

        else {

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

            Node temp = curr.next;

  

            // Корректируем указатели на prev_1 и временный узел

            prev_1.next = temp;

            temp.prev = prev_1;

        }

        return start;

    }

  

    // Функция для отображения элементов списка

    static void display(Node start)

    {

        Node temp = start;

  

        while (temp.next != start) {

            Console.Write("{0} ", temp.data);

            temp = temp.next;

        }

        Console.Write("{0} ", temp.data);

    }

  

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

    public static void Main(String[] args)

    {

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

        Node start = null;

  

        // Созданный связанный список будет 4.5.6.7.8

        start = insert(start, 4);

        start = insert(start, 5);

        start = insert(start, 6);

        start = insert(start, 7);

        start = insert(start, 8);

  

        Console.Write("List Before Deletion: ");

        display(start);

  

        // Удалить узел, которого нет в списке

        start = deleteNode(start, 9);

        Console.Write("\nList After Deletion: ");

        display(start);

  

        // Удалить первый узел

        start = deleteNode(start, 4);

        Console.Write("\nList After Deleting {0}: ", 4);

        display(start);

  

        // Удалить последний узел

        start = deleteNode(start, 8);

        Console.Write("\nList After Deleting {0}: ", 8);

        display(start);

  

        // Удалить средний узел

        start = deleteNode(start, 6);

        Console.Write("\nList After Deleting {0}: ", 6);

        display(start);

    }

}

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


Выход:

List Before Deletion: 4 5 6 7 8 
List doesn't have node with value = 9
List After Deletion: 4 5 6 7 8 
List After Deleting 4: 5 6 7 8 
List After Deleting 8: 5 6 7 
List After Deleting 6: 5 7 

Эта статья предоставлена Акашем Гуптой . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes