Eliminación de una lista enlazada circular

Ya hemos discutido la lista enlazada circular y el recorrido en una lista enlazada circular en los siguientes artículos: 
Introducción a la lista enlazada circular  
Recorrido en una lista enlazada circular 
En este artículo, aprenderemos a eliminar un Node de una lista enlazada circular. Considere la lista enlazada como se muestra a continuación:  

cll_inserted

Se nos dará un Node y nuestra tarea es eliminar ese Node de la lista circular enlazada.

Complete Interview Preparation - GFG

Ejemplos: 

Input : 2->5->7->8->10->(head node)
        data = 5
Output : 2->7->8->10->(head node)

Input : 2->5->7->8->10->(head node)
         7
Output : 2->5->8->10->(head node)

Algoritmo
Caso 1 : La lista está vacía. 

  • Si la lista está vacía simplemente regresaremos.

Caso 2 : la lista no está vacía  

  • Si la lista no está vacía, definimos dos punteros curr y prev e inicializamos el puntero curr con el Node principal .
  • Recorra la lista usando curr para encontrar el Node a eliminar y antes de pasar a curr al siguiente Node, establezca cada vez prev = curr.
  • Si se encuentra el Node, verifique si es el único Node en la lista. En caso afirmativo, configure head = NULL y free (curr).
  • Si la lista tiene más de un Node, compruebe si es el primer Node de la lista. Condición para verificar esto (curr == head). En caso afirmativo, mueva anterior hasta que llegue al último Node. Después de que prev llegue al último Node, configure head = head -> next y prev -> next = head. Eliminar actual
  • Si curr no es el primer Node, verificamos si es el último Node de la lista. La condición para verificar esto es (curr -> next == head).
  • Si curr es el último Node. Establezca prev -> next = head y elimine el Node curr by free(curr).
  • Si el Node que se va a eliminar no es ni el primer Node ni el último, establezca anterior -> siguiente = actual -> siguiente y elimine actual.

Programa completo para demostrar la eliminación en la lista circular enlazada: 

C++14

// C++ program to delete a given key from
// linked list.
#include <bits/stdc++.h>
using namespace std;
  
/* structure for a node */
class Node {
public:
    int data;
    Node* next;
};
  
/* Function to insert a node at the beginning of 
a Circular linked list */
void push(Node** head_ref, int data)
{
    // Create a new node and make head as next
    // of it.
    Node* ptr1 = new Node();
    ptr1->data = data;
    ptr1->next = *head_ref;
  
    /* If linked list is not NULL then set the 
    next of last node */
    if (*head_ref != NULL) 
    {
        // Find the node before head and update
        // next of it.
        Node* temp = *head_ref;
        while (temp->next != *head_ref)
            temp = temp->next;
        temp->next = ptr1;
    }
    else
        ptr1->next = ptr1; /*For the first node */
  
    *head_ref = ptr1;
}
  
/* Function to print nodes in a given 
circular linked list */
void printList(Node* head)
{
    Node* temp = head;
    if (head != NULL) {
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
    }
  
    cout << endl;
}
  
/* Function to delete a given node from the list */
void deleteNode(Node** head, int key) 
{
      
    // If linked list is empty
    if (*head == NULL)
        return;
          
    // If the list contains only a single node
    if((*head)->data==key && (*head)->next==*head)
    {
        free(*head);
        *head=NULL;
        return;
    }
      
    Node *last=*head,*d;
      
    // If head is to be deleted
    if((*head)->data==key) 
    {
          
        // Find the last node of the list
        while(last->next!=*head)
            last=last->next;
              
        // Point last node to the next of head i.e. 
        // the second node of the list
        last->next=(*head)->next;
        free(*head);
        *head=last->next;
      return;
    }
      
    // Either the node to be deleted is not found 
    // or the end of list is not reached
    while(last->next!=*head&&last->next->data!=key) 
    {
        last=last->next;
    }
      
    // If node to be deleted was found
    if(last->next->data==key) 
    {
        d=last->next;
        last->next=d->next;
        free(d);
    }
    else
        cout<<"no such keyfound";
    }
  
/* Driver code */
int main()
{
    /* Initialize lists as empty */
    Node* head = NULL;
  
    /* Created linked list will be 2->5->7->8->10 */
    push(&head, 2);
    push(&head, 5);
    push(&head, 7);
    push(&head, 8);
    push(&head, 10);
  
    cout << "List Before Deletion: ";
    printList(head);
  
    deleteNode(&head, 7);
  
    cout << "List After Deletion: ";
    printList(head);
  
    return 0;
}
  
// This is code is contributed by rathbhupendra

C

// C program to delete a given key from
// linked list.
#include <stdio.h>
#include <stdlib.h>
  
/* structure for a node */
struct Node {
    int data;
    struct Node* next;
};
  
/* Function to insert a node at the beginning of
   a Circular linked list */
void push(struct Node** head_ref, int data)
{
    // Create a new node and make head as next
    // of it.
    struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
    ptr1->data = data;
    ptr1->next = *head_ref;
  
    /* If linked list is not NULL then set the
       next of last node */
    if (*head_ref != NULL) {
        // Find the node before head and update
        // next of it.
        struct Node* temp = *head_ref;
        while (temp->next != *head_ref)
            temp = temp->next;
        temp->next = ptr1;
    }
    else
        ptr1->next = ptr1; /*For the first node */
  
    *head_ref = ptr1;
}
  
/* Function to print nodes in a given
  circular linked list */
void printList(struct Node* head)
{
    struct Node* temp = head;
    if (head != NULL) {
        do {
            printf("%d ", temp->data);
            temp = temp->next;
        } while (temp != head);
    }
  
    printf("\n");
}
  
/* Function to delete a given node from the list */
void deleteNode(struct Node* head, int key)
{
    if (head == NULL)
        return;
  
    // Find the required node
    struct Node *curr = head, *prev;
    while (curr->data != key) 
    {
        if (curr->next == head)
        {
            printf("\nGiven node is not found"
                   " in the list!!!");
            break;
        }
  
        prev = curr;
        curr = curr->next;
    }
  
    // Check if node is only node
    if (curr->next == head) 
    {
        head = NULL;
        free(curr);
        return;
    }
  
    // If more than one node, check if
    // it is first node
    if (curr == head) 
    {
        prev = head;
        while (prev->next != head)
            prev = prev->next;
        head = curr->next;
        prev->next = head;
        free(curr);
    }
  
    // check if node is last node
    else if (curr->next == head && curr == head) 
    {
        prev->next = head;
        free(curr);
    }
    else 
    {
        prev->next = curr->next;
        free(curr);
    }
}
  
/* Driver code */
int main()
{
    /* Initialize lists as empty */
    struct Node* head = NULL;
  
    /* Created linked list will be 2->5->7->8->10 */
    push(&head, 2);
    push(&head, 5);
    push(&head, 7);
    push(&head, 8);
    push(&head, 10);
  
    printf("List Before Deletion: ");
    printList(head);
  
    deleteNode(head, 7);
  
    printf("List After Deletion: ");
    printList(head);
  
    return 0;
}

Java

// Java program to delete a given key from
// linked list.
class GFG {
  
    /* ure for a node */
    static class Node {
        int data;
        Node next;
    };
  
    /* Function to insert a node at the beginning of 
a Circular linked list */
    static Node push(Node head_ref, int data)
    {
        // Create a new node and make head as next
        // of it.
        Node ptr1 = new Node();
        ptr1.data = data;
        ptr1.next = head_ref;
  
        /* If linked list is not null then set the 
    next of last node */
        if (head_ref != null) {
            // Find the node before head and update
            // next of it.
            Node temp = head_ref;
            while (temp.next != head_ref)
                temp = temp.next;
            temp.next = ptr1;
        }
        else
            ptr1.next = ptr1; /*For the first node */
  
        head_ref = ptr1;
        return head_ref;
    }
  
    /* Function to print nodes in a given 
circular linked list */
    static void printList(Node head)
    {
        Node temp = head;
        if (head != null) {
            do {
                System.out.printf("%d ", temp.data);
                temp = temp.next;
            } while (temp != head);
        }
  
        System.out.printf("\n");
    }
  
    /* Function to delete a given node from the list */
    static Node deleteNode(Node head, int key)
    {
        if (head == null)
            return null;
  
        // Find the required node
        Node curr = head, prev = new Node();
        while (curr.data != key) {
            if (curr.next == head) {
                System.out.printf("\nGiven node is not found"
                                  + " in the list!!!");
                break;
            }
  
            prev = curr;
            curr = curr.next;
        }
  
        // Check if node is only node
        if (curr == head && curr.next == head) {
            head = null;
            return head;
        }
  
        // If more than one node, check if
        // it is first node
        if (curr == head) {
            prev = head;
            while (prev.next != head)
                prev = prev.next;
            head = curr.next;
            prev.next = head;
        }
  
        // check if node is last node
        else if (curr.next == head) {
            prev.next = head;
        }
        else {
            prev.next = curr.next;
        }
        return head;
    }
  
    /* Driver code */
    public static void main(String args[])
    {
        /* Initialize lists as empty */
        Node head = null;
  
        /* Created linked list will be 2.5.7.8.10 */
        head = push(head, 2);
        head = push(head, 5);
        head = push(head, 7);
        head = push(head, 8);
        head = push(head, 10);
  
        System.out.printf("List Before Deletion: ");
        printList(head);
  
        head = deleteNode(head, 7);
  
        System.out.printf("List After Deletion: ");
        printList(head);
    }
}
  
// This code is contributed by Arnab Kundu

Python

# Python program to delete a given key from
# linked list.
  
# Node of a doubly linked list 
class Node: 
    def __init__(self, next = None, data = None): 
        self.next = next
        self.data = data 
  
# Function to insert a node at the beginning of 
# a Circular linked list 
def push(head_ref, data):
  
    # Create a new node and make head as next
    # of it.
    ptr1 = Node()
    ptr1.data = data
    ptr1.next = head_ref
  
    # If linked list is not None then set the 
    # next of last node 
    if (head_ref != None) :
          
        # Find the node before head and update
        # next of it.
        temp = head_ref
        while (temp.next != head_ref):
            temp = temp.next
        temp.next = ptr1
      
    else:
        ptr1.next = ptr1 # For the first node 
  
    head_ref = ptr1
    return head_ref
  
# Function to print nodes in a given 
# circular linked list 
def printList( head):
  
    temp = head
    if (head != None) :
        while(True) :
            print( temp.data, end = " ")
            temp = temp.next
            if (temp == head):
                break
    print()
  
# Function to delete a given node from the list 
def deleteNode( head, key) :
  
    # If linked list is empty
    if (head == None):
        return
          
    # If the list contains only a single node
    if((head).data == key and (head).next == head):
      
        head = None
      
    last = head
    d = None
      
    # If head is to be deleted
    if((head).data == key) :
          
        # Find the last node of the list
        while(last.next != head):
            last = last.next
              
        # Point last node to the next of head i.e. 
        # the second node of the list
        last.next = (head).next
        head = last.next
      
    # Either the node to be deleted is not found 
    # or the end of list is not reached
    while(last.next != head and last.next.data != key) :
        last = last.next
  
    # If node to be deleted was found
    if(last.next.data == key) :
        d = last.next
        last.next = d.next
      
    else:
        print("no such keyfound")
      
    return head
  
# Driver code
  
# Initialize lists as empty 
head = None
  
# Created linked list will be 2.5.7.8.10 
head = push(head, 2)
head = push(head, 5)
head = push(head, 7)
head = push(head, 8)
head = push(head, 10)
  
print("List Before Deletion: ")
printList(head)
  
head = deleteNode(head, 7)
  
print( "List After Deletion: ")
printList(head)
  
# This code is contributed by Arnab Kundu

C#

// C# program to delete a given key from
// linked list.
using System;
  
class GFG {
  
    /* structure for a node */
    public class Node {
        public int data;
        public Node next;
    };
  
    /* Function to insert a node at the beginning of 
a Circular linked list */
    static Node push(Node head_ref, int data)
    {
        // Create a new node and make head as next
        // of it.
        Node ptr1 = new Node();
        ptr1.data = data;
        ptr1.next = head_ref;
  
        /* If linked list is not null then set the 
         next of last node */
        if (head_ref != null) 
        {
            // Find the node before head and update
            // next of it.
            Node temp = head_ref;
            while (temp.next != head_ref)
                temp = temp.next;
            temp.next = ptr1;
        }
        else
            ptr1.next = ptr1; /*For the first node */
  
        head_ref = ptr1;
        return head_ref;
    }
  
    /* Function to print nodes in a given 
       circular linked list */
    static void printList(Node head)
    {
        Node temp = head;
        if (head != null) 
        {
            do 
            {
                Console.Write("{0} ", temp.data);
                temp = temp.next;
            } while (temp != head);
        }
  
        Console.Write("\n");
    }
  
    /* Function to delete a given node from the list */
    static Node deleteNode(Node head, int key)
    {
        if (head == null)
            return null;
  
        // Find the required node
        Node curr = head, prev = new Node();
        while (curr.data != key)
        {
            if (curr.next == head) 
            {
                Console.Write("\nGiven node is not found"
                              + " in the list!!!");
                break;
            }
  
            prev = curr;
            curr = curr.next;
        }
  
        // Check if node is only node
        if (curr.next == head && curr == head) 
        {
            head = null;
            return head;
        }
  
        // If more than one node, check if
        // it is first node
        if (curr == head) 
        {
            prev = head;
            while (prev.next != head)
                prev = prev.next;
            head = curr.next;
            prev.next = head;
        }
  
        // check if node is last node
        else if (curr.next == head) 
        {
            prev.next = head;
        }
        else
        {
            prev.next = curr.next;
        }
        return head;
    }
  
    /* Driver code */
    public static void Main(String[] args)
    {
        /* Initialize lists as empty */
        Node head = null;
  
        /* Created linked list will be 2.5.7.8.10 */
        head = push(head, 2);
        head = push(head, 5);
        head = push(head, 7);
        head = push(head, 8);
        head = push(head, 10);
  
        Console.Write("List Before Deletion: ");
        printList(head);
  
        head = deleteNode(head, 7);
  
        Console.Write("List After Deletion: ");
        printList(head);
    }
}
  
// This code has been contributed by 29AjayKumar

Javascript

<script>
// javascript program to delete a given key from
// linked list.    /* ure for a node */
class Node {
    constructor() {
        this.data = 0;
        this.next = null;
    }
}
    /*
     * Function to insert a node at the beginning of a Circular linked list
     */
    function push(head_ref , data) {
        // Create a new node and make head as next
        // of it.
        var ptr1 = new Node();
        ptr1.data = data;
        ptr1.next = head_ref;
  
        /*
         * If linked list is not null then set the next of last node
         */
        if (head_ref != null) {
            // Find the node before head and update
            // next of it.
            var temp = head_ref;
            while (temp.next != head_ref)
                temp = temp.next;
            temp.next = ptr1;
        } else
            ptr1.next = ptr1; /* For the first node */
  
        head_ref = ptr1;
        return head_ref;
    }
  
    /*
     * Function to print nodes in a given circular linked list
     */
    function printList(head) {
    var temp = head;
        if (head != null) {
            do {
                document.write( temp.data+" ");
                temp = temp.next;
            } while (temp != head);
        }
  
        document.write("<br/>");
    }
  
    /* Function to delete a given node from the list */
    function deleteNode(head , key) {
        if (head == null)
            return null;
  
        // Find the required node
        var curr = head, prev = new Node();
        while (curr.data != key) {
            if (curr.next == head) {
                document.write("<br/>Given node is not found" + " in the list!!!");
                break;
            }
  
            prev = curr;
            curr = curr.next;
        }
  
        // Check if node is only node
        if (curr == head && curr.next == head) {
            head = null;
            return head;
        }
  
        // If more than one node, check if
        // it is first node
        if (curr == head) {
            prev = head;
            while (prev.next != head)
                prev = prev.next;
            head = curr.next;
            prev.next = head;
        }
  
        // check if node is last node
        else if (curr.next == head) {
            prev.next = head;
        } else {
            prev.next = curr.next;
        }
        return head;
    }
  
        /* Driver code */
      
        /* Initialize lists as empty */
        var head = null;
  
        /* Created linked list will be 2.5.7.8.10 */
        head = push(head, 2);
        head = push(head, 5);
        head = push(head, 7);
        head = push(head, 8);
        head = push(head, 10);
  
        document.write("List Before Deletion: ");
        printList(head);
  
        head = deleteNode(head, 7);
  
        document.write("List After Deletion: ");
        printList(head);
  
// This code contributed by umadevi9616 
</script>
Producción

List Before Deletion: 10 8 7 5 2 
List After Deletion: 10 8 5 2 

Complejidad de tiempo: O(n)

El peor de los casos ocurre cuando el elemento a eliminar es el último elemento y necesitamos movernos por toda la lista.

Espacio Auxiliar: O(1)

Como espacio adicional constante se utiliza.

Este artículo es una contribución de Harsh Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *