Requisito previo: conjunto de listas de enlaces dobles 1 | Introducción e Inserción
Escriba una función para eliminar un Node dado en una lista doblemente enlazada.
Lista original doblemente enlazada
Enfoque: La eliminación de un Node en una lista doblemente enlazada se puede dividir en tres categorías principales:
- Después de la eliminación del Node principal.
- Después de la eliminación del Node medio.
- Después de la eliminación del último Node.
Los tres casos mencionados se pueden manejar en dos pasos si se conocen el puntero del Node a eliminar y el puntero principal.
- Si el Node que se eliminará es el Node principal, haga que el siguiente Node sea principal.
- Si se elimina un Node, conecte el Node siguiente y anterior del Node eliminado.
Algoritmo
- Deje que el Node a eliminar sea del .
- Si el Node que se eliminará es el Node principal, cambie el puntero principal al siguiente encabezado actual.
if headnode == del then
headnode = del.nextNode
- Establezca siguiente de anterior a del , si existe anterior a del .
if del.nextNode != none
del.nextNode.previousNode = del.previousNode
- Establecer prev de next to del , si existe next to del .
if del.previousNode != none
del.previousNode.nextNode = del.next
C++
// C++ program to delete a node from
// Doubly Linked List
#include <bits/stdc++.h>
using namespace std;
// Anode of the doubly linked list
class Node
{
public:
int data;
Node* next;
Node* prev;
};
/* Function to delete a node in a Doubly
Linked List. head_ref --> pointer to
head node pointer. del --> pointer to
node to be deleted. */
void deleteNode(Node** head_ref, Node* del)
{
// Base case
if (*head_ref == NULL || del == NULL)
return;
// If node to be deleted is head node
if (*head_ref == del)
*head_ref = del->next;
/* Change next only if node to be
deleted is NOT the last node */
if (del->next != NULL)
del->next->prev = del->prev;
/* Change prev only if node to be
deleted is NOT the first node */
if (del->prev != NULL)
del->prev->next = del->next;
/* Finally, free the memory occupied
by del*/
free(del);
return;
}
// UTILITY FUNCTIONS
/* Function to insert a node at the
beginning of the Doubly Linked List */
void push(Node** head_ref, int new_data)
{
// Allocate node
Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
/* Since we are adding at the
beginning, prev is always NULL */
new_node->prev = NULL;
/* Link the old list off the
new node */
new_node->next = (*head_ref);
/* Change prev of head node to
new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* Move the head to point to the
new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given
doubly linked list. This function is
same as printList() of singly linked list */
void printList(Node* node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
// Driver code
int main()
{
// Start with the empty list
Node* head = NULL;
/* Let us create the doubly linked list
10<->8<->4<->2 */
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
cout << "Original Linked list ";
printList(head);
/* Delete nodes from the doubly
linked list */
// Delete first node
deleteNode(&head, head);
// Delete middle node
deleteNode(&head, head->next);
// Delete last node
deleteNode(&head, head->next);
/* Modified linked list will be
NULL<-8->NULL */
cout << "Modified Linked list ";
printList(head);
return 0;
}
// This code is contributed by rathbhupendra
Producción:
Original Linked list 10 8 4 2 Modified Linked list 8
Análisis de Complejidad:
- Complejidad Temporal: O(1).
Dado que no se requiere atravesar la lista enlazada, la complejidad del tiempo es constante. - Complejidad espacial: O(1).
Como no se requiere espacio adicional, la complejidad del espacio es constante.
¡Consulte el artículo completo sobre Eliminar un Node en una lista doblemente vinculada para obtener más detalles!
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