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
Python
# Program to delete a node in a # doubly-linked list # For Garbage collection import gc # A node of the doubly linked list class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.next = None self.prev = None class DoublyLinkedList: # Constructor for empty Doubly # Linked List def __init__(self): self.head = None # Function to delete a node in a Doubly # Linked List. head_ref --> pointer to # head node pointer. dele --> pointer to # node to be deleted. def deleteNode(self, dele): # Base Case if self.head is None or dele is None: return # If node to be deleted is head node if self.head == dele: self.head = dele.next # Change next only if node to be # deleted is NOT the last node if dele.next is not None: dele.next.prev = dele.prev # Change prev only if node to be # deleted is NOT the first node if dele.prev is not None: dele.prev.next = dele.next # Finally, free the memory occupied # by dele # Call python garbage collector gc.collect() # Given a reference to the head of a # list and an integer, inserts a new # node on the front of list def push(self, new_data): # 1. Allocates node # 2. Put the data in it new_node = Node(new_data) # 3. Make next of new node as head # and previous as None (already None) new_node.next = self.head # 4. Change prev of head node to # new_node if self.head is not None: self.head.prev = new_node # 5. Move the head to point to the # new node self.head = new_node def printList(self, node): while(node is not None): print node.data, node = node.next # Driver code # Start with empty list dll = DoublyLinkedList() # Let us create the doubly linked list # 10<->8<->4<->2 dll.push(2); dll.push(4); dll.push(8); dll.push(10); print "Original Linked List", dll.printList(dll.head) # Delete nodes from doubly linked list dll.deleteNode(dll.head) dll.deleteNode(dll.head.next) dll.deleteNode(dll.head.next) # Modified linked list will be NULL<-8->NULL print "Modified Linked List", dll.printList(dll.head) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
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