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:
Se nos dará un Node y nuestra tarea es eliminar ese Node de la lista circular enlazada.
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>
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