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>
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