Hemos discutido la introducción de la lista enlazada doblemente circular y su inserción .
Formulemos el enunciado del problema para comprender el proceso de eliminación. Dada una ‘clave’ , elimine la primera aparición de esta clave en la lista circular doblemente enlazada.
Algoritmo:
Caso 1: Lista vacía (inicio = NULL)
- Si la lista está vacía, simplemente devuélvela.
Caso 2: La Lista contiene inicialmente algunos Nodes, puntos de inicio en el primer Node de la Lista
- Si la lista no está vacía, definimos dos punteros curr y prev_1 e inicializamos el puntero curr apunta al primer Node de la lista, y prev_1 = NULL.
- Recorra la lista usando el puntero curr para encontrar el Node que se eliminará y antes de pasar de curr al siguiente Node, establezca cada vez prev_1 = curr .
- Si se encuentra el Node, verifique si es el único Node en la lista. En caso afirmativo, establezca start = NULL y libere el Node apuntado por curr .
- Si la lista tiene más de un Node, compruebe si es el primer Node de la lista. La condición para verificar esto es (curr == start). En caso afirmativo, mueva prev_1 al último Node (prev_1 = inicio -> anterior). Después de que prev_1 llegue al último Node, configure start = start -> next y prev_1 -> next = start y start -> prev = prev_1. Libera el Node apuntando por curr.
- 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 == start). En caso afirmativo, configure prev_1 -> next = start y start -> prev = prev_1. Libera el Node apuntando por curr.
- Si el Node que se va a eliminar no es ni el primer Node ni el último Node, declare un puntero temporal más e inicialice los puntos temporales del puntero al siguiente del puntero actual (temp = curr->next). Ahora configure, prev_1 -> next = temp y temp ->prev = prev_1. Libera el Node apuntando por curr.
- Si la clave dada (Digamos 4) coincide con el primer Node de la lista (Paso 4):
- Si la clave dada (Digamos 8) coincide con el último Node de la lista (Paso 5):
- Si la clave dada (Diga 6) coincide con el Node medio de la lista (Paso 6):
Implementación:
C++
// C++ program to delete a given key from
// circular doubly linked list.
#include <bits/stdc++.h>
using namespace std;
// Structure of a Node
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Function to insert node in the list
void insert(struct Node** start, int value)
{
// If the list is empty, create a single node
// circular and doubly list
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;
}
// If list is not empty
/* Find last node */
Node* last = (*start)->prev;
// Create Node dynamically
struct Node* new_node = new Node;
new_node->data = value;
// Start is going to be next of new_node
new_node->next = *start;
// Make new node previous of start
(*start)->prev = new_node;
// Make last previous of new node
new_node->prev = last;
// Make new node next of old last
last->next = new_node;
}
// Function to delete a given node from the list
void deleteNode(struct Node** start, int key)
{
// If list is empty
if (*start == NULL)
return;
// Find the required node
// Declare two pointers and initialize them
struct Node *curr = *start, *prev_1 = NULL;
while (curr->data != key) {
// If node is not present in the list
if (curr->next == *start) {
printf("\nList doesn't have node with value = %d", key);
return;
}
prev_1 = curr;
curr = curr->next;
}
// Check if node is the only node in list
if (curr->next == *start && prev_1 == NULL) {
(*start) = NULL;
free(curr);
return;
}
// If list has more than one node,
// check if it is the first node
if (curr == *start) {
// Move prev_1 to last node
prev_1 = (*start)->prev;
// Move start ahead
*start = (*start)->next;
// Adjust the pointers of prev_1 and start node
prev_1->next = *start;
(*start)->prev = prev_1;
free(curr);
}
// check if it is the last node
else if (curr->next == *start) {
// Adjust the pointers of prev_1 and start node
prev_1->next = *start;
(*start)->prev = prev_1;
free(curr);
}
else {
// create new pointer, points to next of curr node
struct Node* temp = curr->next;
// Adjust the pointers of prev_1 and temp node
prev_1->next = temp;
temp->prev = prev_1;
free(curr);
}
}
// Function to display list elements
void display(struct Node* start)
{
struct Node* temp = start;
while (temp->next != start) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d ", temp->data);
}
// Driver program to test above functions
int main()
{
// Start with the empty list
struct Node* start = NULL;
// Created linked list will be 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);
// Delete the node which is not present in list
deleteNode(&start, 9);
printf("\nList After Deletion: ");
display(start);
// Delete the first node
deleteNode(&start, 4);
printf("\nList After Deleting %d: ", 4);
display(start);
// Delete the last node
deleteNode(&start, 8);
printf("\nList After Deleting %d: ", 8);
display(start);
// Delete the middle node
deleteNode(&start, 6);
printf("\nList After Deleting %d: ", 6);
display(start);
return 0;
}
Java
// Java program to delete a given key from
// circular doubly linked list.
class GFG {
// structure of a Node
static class Node {
int data;
Node next;
Node prev;
};
// Function to insert node in the list
static Node insert(Node start, int value)
{
// If the list is empty, create a single node
// circular and doubly list
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;
}
// If list is not empty
// Find last node /
Node last = (start).prev;
// Create Node dynamically
Node new_node = new Node();
new_node.data = value;
// Start is going to be next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
return start;
}
// Function to delete a given node from the list
static Node deleteNode(Node start, int key)
{
// If list is empty
if (start == null)
return null;
// Find the required node
// Declare two pointers and initialize them
Node curr = start, prev_1 = null;
while (curr.data != key) {
// If node is not present in the list
if (curr.next == start) {
System.out.printf("\nList doesn't have node with value = %d", key);
return start;
}
prev_1 = curr;
curr = curr.next;
}
// Check if node is the only node in list
if (curr.next == start && prev_1 == null) {
(start) = null;
return start;
}
// If list has more than one node,
// check if it is the first node
if (curr == start) {
// Move prev_1 to last node
prev_1 = (start).prev;
// Move start ahead
start = (start).next;
// Adjust the pointers of prev_1 and start node
prev_1.next = start;
(start).prev = prev_1;
}
// check if it is the last node
else if (curr.next == start) {
// Adjust the pointers of prev_1 and start node
prev_1.next = start;
(start).prev = prev_1;
}
else {
// create new pointer, points to next of curr node
Node temp = curr.next;
// Adjust the pointers of prev_1 and temp node
prev_1.next = temp;
temp.prev = prev_1;
}
return start;
}
// Function to display list elements
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);
}
// Driver program to test above functions
public static void main(String args[])
{
// Start with the empty list
Node start = null;
// Created linked list will be 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);
// Delete the node which is not present in list
start = deleteNode(start, 9);
System.out.printf("\nList After Deletion: ");
display(start);
// Delete the first node
start = deleteNode(start, 4);
System.out.printf("\nList After Deleting %d: ", 4);
display(start);
// Delete the last node
start = deleteNode(start, 8);
System.out.printf("\nList After Deleting %d: ", 8);
display(start);
// Delete the middle node
start = deleteNode(start, 6);
System.out.printf("\nList After Deleting %d: ", 6);
display(start);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to delete a given key from
# circular doubly linked list.
# structure of a node of linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
def insert( start, value):
# If the list is empty, create a single node
# circular and doubly list
if (start == None):
new_node = Node(0)
new_node.data = value
new_node.next = new_node.prev = new_node
start = new_node
return start
# If list is not empty
# Find last node /
last = (start).prev
# Create Node dynamically
new_node = Node(0)
new_node.data = value
# Start is going to be next of new_node
new_node.next = start
# Make new node previous of start
(start).prev = new_node
# Make last previous of new node
new_node.prev = last
# Make new node next of old last
last.next = new_node
return start
# Function to delete a given node
# from the list
def deleteNode(start, key):
# If list is empty
if (start == None):
return None
# Find the required node
# Declare two pointers and initialize them
curr = start
prev_1 = None
while (curr.data != key) :
# If node is not present in the list
if (curr.next == start) :
print ("List doesn't have node",
"with value = ", key)
return start
prev_1 = curr
curr = curr.next
# Check if node is the only node in list
if (curr.next == start and prev_1 == None) :
(start) = None
return start
# If list has more than one node,
# check if it is the first node
if (curr == start) :
# Move prev_1 to last node
prev_1 = (start).prev
# Move start ahead
start = (start).next
# Adjust the pointers of prev_1
# and start node
prev_1.next = start
(start).prev = prev_1
# check if it is the last node
elif (curr.next == start) :
# Adjust the pointers of prev_1
# and start node
prev_1.next = start
(start).prev = prev_1
else :
# create new pointer,
# points to next of curr node
temp = curr.next
# Adjust the pointers of prev_1
# and temp node
prev_1.next = temp
temp.prev = prev_1
return start
# Function to display list elements
def display(start):
temp = start
while (temp.next != start) :
print (temp.data, end = " ")
temp = temp.next
print (temp.data)
# Driver Code
if __name__=='__main__':
# Start with the empty list
start = None
# Created linked list will be 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)
# Delete the node which is not present in list
start = deleteNode(start, 9)
print ("List After Deletion: ")
display(start)
# Delete the first node
start = deleteNode(start, 4)
print ("List After Deleting", 4)
display(start)
# Delete the last node
start = deleteNode(start, 8)
print ("List After Deleting ", 8)
display(start)
# Delete the middle node
start = deleteNode(start, 6)
print ("List After Deleting ", 6)
display(start)
# This code is contributed by Arnab Kundu
C#
// C# program to delete a given key from
// circular doubly linked list.
using System;
class GFG {
// structure of a Node
public class Node {
public int data;
public Node next;
public Node prev;
};
// Function to insert node in the list
static Node insert(Node start, int value)
{
// If the list is empty, create a single node
// circular and doubly list
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;
}
// If list is not empty
// Find last node /
Node last = (start).prev;
// Create Node dynamically
new_node = new Node();
new_node.data = value;
// Start is going to be next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
return start;
}
// Function to delete a given node from the list
static Node deleteNode(Node start, int key)
{
// If list is empty
if (start == null)
return null;
// Find the required node
// Declare two pointers and initialize them
Node curr = start, prev_1 = null;
while (curr.data != key) {
// If node is not present in the list
if (curr.next == start) {
Console.Write("\nList doesn't have node with value = {0}", key);
return start;
}
prev_1 = curr;
curr = curr.next;
}
// Check if node is the only node in list
if (curr.next == start && prev_1 == null) {
(start) = null;
return start;
}
// If list has more than one node,
// check if it is the first node
if (curr == start) {
// Move prev_1 to last node
prev_1 = (start).prev;
// Move start ahead
start = (start).next;
// Adjust the pointers of prev_1 and start node
prev_1.next = start;
(start).prev = prev_1;
}
// check if it is the last node
else if (curr.next == start) {
// Adjust the pointers of prev_1 and start node
prev_1.next = start;
(start).prev = prev_1;
}
else {
// create new pointer, points to next of curr node
Node temp = curr.next;
// Adjust the pointers of prev_1 and temp node
prev_1.next = temp;
temp.prev = prev_1;
}
return start;
}
// Function to display list elements
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);
}
// Driver code
public static void Main(String[] args)
{
// Start with the empty list
Node start = null;
// Created linked list will be 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);
// Delete the node which is not present in list
start = deleteNode(start, 9);
Console.Write("\nList After Deletion: ");
display(start);
// Delete the first node
start = deleteNode(start, 4);
Console.Write("\nList After Deleting {0}: ", 4);
display(start);
// Delete the last node
start = deleteNode(start, 8);
Console.Write("\nList After Deleting {0}: ", 8);
display(start);
// Delete the middle node
start = deleteNode(start, 6);
Console.Write("\nList After Deleting {0}: ", 6);
display(start);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// javascript program to delete a given key from
// circular doubly linked list.
// structure of a Node
class Node {
constructor() {
this.data = 0;
this.prev = null;
this.next = null;
}
}
// Function to insert node in the list
function insert(start , value)
{
// If the list is empty, create a single node
// circular and doubly list
if (start == null) {
var new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return start;
}
// If list is not empty
// Find last node /
var last = (start).prev;
// Create Node dynamically
var new_node = new Node();
new_node.data = value;
// Start is going to be next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
return start;
}
// Function to delete a given node from the list
function deleteNode(start , key) {
// If list is empty
if (start == null)
return null;
// Find the required node
// Declare two pointers and initialize them
var curr = start, prev_1 = null;
while (curr.data != key) {
// If node is not present in the list
if (curr.next == start) {
document.write("<br/>List doesn't have node with value = "+ key);
return start;
}
prev_1 = curr;
curr = curr.next;
}
// Check if node is the only node in list
if (curr.next == start && prev_1 == null) {
(start) = null;
return start;
}
// If list has more than one node,
// check if it is the first node
if (curr == start) {
// Move prev_1 to last node
prev_1 = (start).prev;
// Move start ahead
start = (start).next;
// Adjust the pointers of prev_1 and start node
prev_1.next = start;
(start).prev = prev_1;
}
// check if it is the last node
else if (curr.next == start) {
// Adjust the pointers of prev_1 and start node
prev_1.next = start;
(start).prev = prev_1;
}
else {
// create new pointer, points to next of curr node
var temp = curr.next;
// Adjust the pointers of prev_1 and temp node
prev_1.next = temp;
temp.prev = prev_1;
}
return start;
}
// Function to display list elements
function display(start)
{
var temp = start;
while (temp.next != start) {
document.write( temp.data+" ");
temp = temp.next;
}
document.write( temp.data+" ");
}
// Driver program to test above functions
// Start with the empty list
var start = null;
// Created linked list will be 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);
document.write("List Before Deletion: ");
display(start);
// Delete the node which is not present in list
start = deleteNode(start, 9);
document.write("<br/>List After Deletion: ");
display(start);
// Delete the first node
start = deleteNode(start, 4);
document.write("<br/>List After Deleting 4: ");
display(start);
// Delete the last node
start = deleteNode(start, 8);
document.write("<br/>List After Deleting 8: ");
display(start);
// Delete the middle node
start = deleteNode(start, 6);
document.write("<br/>List After Deleting 6: ");
display(start);
// This code contributed by aashish1995
</script>
Producción
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
Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces (para eliminar y mostrar la lista vinculada). Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Este artículo es una contribución de Akash Gupta . 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.
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