Una lista doblemente enlazada contiene un puntero adicional, generalmente llamado puntero anterior, además del puntero siguiente y los datos en las listas enlazadas individuales.

Tabla de contenidos
- Crear lista doblemente enlazada o listas de doble hilo
- Ventajas de las listas de doble subproceso sobre singletons
- Desventajas de las listas de doble subproceso en comparación con singletons
- Agregar elementos a listas de doble subproceso
- Eliminar un nodo de una lista de doble subproceso
- Voltear los elementos de una lista de doble hilo
- Fuente de Recursos
Crear lista doblemente enlazada o listas de doble hilo
Los siguientes ejemplos muestran cómo crear listas de doble subproceso en varios lenguajes de programación:
struct Node { int data; struct Node* next; // Puntero al siguiente nodo en DLL struct Node* prev; // Puntero al nodo anterior en DLL }
class Node: def __init__(self, next=None, prev=None, data=None): self.next = next # Una referencia al siguiente nodo self.prev = prev # Una referencia al nodo anterior self.data = data
public class DLL { Node head; // encabezado de la lista enhebrada /* Nodo en la lista de doble subproceso*/ class Node { int data; Node prev; Node next; // constructor para crear un nuevo nodo // las señales posteriores y anteriores toman nulo como predeterminado Node(int d) { data = d; } } }
Ventajas de las listas de doble subproceso sobre singletons
Las ventajas de las listas de doble subproceso en comparación con las listas únicas son:
- Los elementos del menú doble se pueden desplazar tanto hacia adelante como hacia atrás.
- La operación de eliminación en listas pareadas es más eficiente si se especifica el puntero al nodo que se eliminará.
- Se puede insertar un nuevo nodo antes de un nodo dado rápidamente.
- El proceso de eliminar un nodo de una lista de un solo subproceso necesita conocer el puntero del nodo anterior, y para obtener este puntero a veces tenemos que pasar por los elementos de la lista, pero en el caso de listas dobles, el nodo anterior puede obtener utilizando el puntero anterior.
Desventajas de las listas de doble subproceso en comparación con singletons
- Cada nodo en las listas de doble hilo necesita más espacio que el puntero anterior, pero es posible crear listas dobles en las que cada elemento tenga un solo puntero.
- Todas las operaciones en listas de doble subproceso requieren un puntero adicional para proceder al puntero en el que estamos trabajando. Por ejemplo, al agregar un nuevo elemento, necesitaremos modificar los indicadores anteriores para él además de los indicadores posteriores, y esto significa que hay uno o más pasos adicionales para configurar el indicador anterior.
Agregar elementos a listas de doble subproceso
Los elementos se pueden agregar a las listas de doble subproceso de cuatro maneras:
- Al comienzo de la lista de doble hilo.
- después de cierto nodo.
- Al final de la lista de doble hilo.
- antes de un nodo en particular.
Agregar un nodo al principio de la lista

El nuevo nodo siempre se agrega antes del encabezado de la lista encadenada y el nodo agregado se convierte en el encabezado de esa lista. La función que agrega el nodo debe recibir un puntero al puntero principal, porque la función tiene que cambiar el puntero principal para que apunte al nuevo nodo. En la figura superior se muestra los pasos para agregar un nodo al principio de la lista de doble subproceso:
/* La función inserta un nuevo nodo al principio de la lista usando un puntero al encabezado de la lista y un número entero */ void push(struct Node** head_ref, int new_data) { /* 1. Reserve un lugar para el nodo en memoria */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* 2. Agregar datos */ new_node->data = new_data; /* 3. NULL Hace que el encabezado de la lista siga al nuevo nodo y hace que su valor anterior */ new_node->next = (*head_ref); new_node->prev = NULL; /* 4. Hacer que el nuevo nodo preceda al encabezado de la lista */ if ((*head_ref) != NULL) (*head_ref)->prev = new_node; /* 5. Mueve el encabezado de la lista para que apunte al nuevo nodo */ (*head_ref) = new_node; }
Agregar un nodo después de un nodo específico
En este caso, tenemos un puntero al nodo anterior junto con un nuevo nodo que se agregará después del nodo dado.
Agregar un nodo al final de la lista encadenada
El nuevo nodo siempre se agrega después del último nodo de la lista encadenada, y dado que el encabezado de la lista generalmente lo representa, debemos pasar los elementos de la lista hasta el final y luego cambiar el nodo que sigue al último nodo para convertirse en el nuevo nodo.
Ejemplos y aplicaciones en código
Los siguientes ejemplos muestran los tres métodos de suma y en varios lenguajes de programación:
#include <bits/stdc++.h> using namespace std; // nodo en una lista encadenada class Node { public: int data; Node* next; Node* prev; } /* La función inserta un nuevo nodo al frente de la lista encadenada usando la referencia dada (un puntero a un puntero) al encabezado de la lista y el entero dado */ void push(Node** head_ref, int new_data) { /* 1. Reservar la ubicación del nodo en memoria */ Node* new_node = new Node(); /* 2. Agregar datos */ new_node->data = new_data; /* 3. NULL Hace que el siguiente nuevo nodo sea el encabezado de la lista y lo que le precede */ new_node->next = (*head_ref); new_node->prev = NULL; /* Convierte lo que precede al nodo del encabezado de la lista en el nuevo nodo */ if ((*head_ref) != NULL) (*head_ref)->prev = new_node; /* 5. Mueva la cabeza para señalar el nuevo nodo */ (*head_ref) = new_node; } /* La función inserta un nuevo nodo después de un nodo dado */ void insertAfter(Node* prev_node, int new_data) { /*1. null Comprueba que el nodo dado es */ if (prev_node == NULL) { cout<<"el nodo anterior dado no puede ser NULL" ; return; } /* 2. Reservar la ubicación del nuevo nodo en memoria */ Node* new_node = new Node(); /* 3. Agregar datos */ new_node->data = new_data; /* 4. Hacer que el siguiente nodo sea el siguiente del nodo anterior */ new_node->next = prev_node->next; /* 5. Hacer que el nuevo nodo siga al nodo anterior */ prev_node->next = new_node; /* 6. Hacer que el nodo anterior preceda al nuevo nodo */ new_node->prev = prev_node; /* 7. Cambia lo que precede al nodo que sigue al nuevo nodo */ if (new_node->next != NULL) new_node->next->prev = new_node; } /* La función inserta un nuevo nodo al final de la lista de doble subproceso usando una referencia (un puntero a un puntero) al encabezado de la lista y el entero dado */ void append(Node** head_ref, int new_data) { /* 1. Reservar la ubicación del nodo en la memoria */ Node* new_node = new Node(); Node* last = *head_ref; /* usado en el paso 5*/ /* 2. Agregar datos */ new_node->data = new_data; /* 3. NULL Este nodo será el último nodo por lo que haremos el siguiente */ new_node->next = NULL; /* 4. Hacer que el nuevo nodo sea el encabezado de la lista si la lista está vacía */ if (*head_ref == NULL) { new_node->prev = NULL; *head_ref = new_node; return; } /* 5. De lo contrario, repasamos los elementos de la lista hasta el final */ while (last->next != NULL) last = last->next; /* 6. El nuevo nodo sigue al último nodo de la lista */ last->next = new_node; /* 7. El último nodo de la lista es el que precede al nuevo nodo */ new_node->prev = last; return; } // Esta función imprime el contenido de la lista de doble hilo a partir del nodo dado void printList(Node* node) { Node* last; cout<<" \nRecorrido en dirección de avance \n " ; while (node != NULL) { cout<<" "<<node->data<<" "; last = node; node = node->next; } cout<<"\nRecorrido en sentido inverso \n " ; while (last != NULL) { cout<<" "<<last->data<<" "; last = last->prev; } } /* Probar las funciones anteriores */ int main(){ /* Empezamos con una lista vacía */ Node* head = NULL; // inserta el elemento 6 para hacer la lista // 6-> NULL append(&head, 6); // Inserta el elemento 7 al principio de la lista para que se convierta en // 7->6->NULL push(&head, 7); // Inserta el elemento 1 al principio de la lista para que se convierta en // 1->7->6->NULL push(&head, 1); // inserta el elemento 4 al final de la lista para que // 1->7->6->4->NULL append(&head, 4); // inserta el elemento 8 después del elemento 7 en la lista para convertirlo en // 1->7->8->6->4->NULL insertAfter(head -> next, 8); cout << "La DLL creada es: "; printList(head); return 0; }
# Un nodo en una clase de lista class Node: # Función del constructor para crear un nuevo nodo def __init__(self, data): self.data = data self.next = None self.prev = None # clase para crear una clase de lista de doble subproceso class DoublyLinkedList: # Función del constructor para crear una lista vacía de doble subproceso def __init__(self): self.head = None # inserta un nuevo nodo al frente de la lista enhebrada usando # el puntero dado al encabezado de la lista y el entero dado def push(self, new_data): # 1. Reservar la ubicación del nodo en la memoria # 2. Agregar datos new_node = Node(new_data) # 3. Ninguno Haga que lo que sigue al nuevo nodo sea el encabezado de la lista y lo que lo precede new_node.next = self.head # 4. Convierta lo que precede al nodo principal de la lista en el nuevo nodo if self.head is not None: self.head.prev = new_node # 5. Mueva la cabeza para señalar el nuevo nodo self.head = new_node # inserta un nuevo nodo después de un nodo dado def insertAfter(self, prev_node, new_data): # 1. Ninguno Compruebe que un nodo dado es if prev_node is None: print "el nodo anterior dado no puede ser NULO" return # 2. Reservar la ubicación del nuevo nodo en la memoria # 3. Agregar datos new_node = Node(new_data) # 4. Haga que el siguiente del nuevo nodo sea el siguiente del new_node.next = prev_node.next # 5. Haz que el nuevo nodo siga al prev_node.next = new_node # 6. Haga que el nodo anterior preceda al new_node.prev = prev_node # 7. Cambia lo que precede al nodo que sigue al new if new_node.next is not None: new_node.next.prev = new_node # La función inserta un nuevo nodo al final de la lista de doble subproceso # usando un puntero al encabezado de la lista y el entero dado def append(self, new_data): # 1. Reservar la ubicación del nodo en la memoria # 2. Agregar datos new_node = Node(new_data) #3.Ninguno Este nodo será el último nodo, por lo que haremos que el próximo sea new_node.next = None # 4. Haga que el nuevo nodo sea el encabezado de la lista si la lista if self.head is None: new_node.prev = None self.head = new_node return # 5. De lo contrario, nos desplazaremos por los elementos de la lista hasta el final de last = self.head while(last.next is not None): last = last.next # 6. El nuevo nodo sigue al último nodo de la last.next = new_node # 7. El último nodo de la lista es el que precede a new_node.prev = last return # Esta función imprime el contenido de la lista de doble hilo a partir del nodo dado def printList(self, node): print "\n Recorrido en dirección hacia adelante" while(node is not None): print " % d" %(node.data), last = node node = node.next print "\n Recorrido en dirección inversa" while(last is not None): print " % d" %(last.data), last = last.prev #D Test de funciones anteriores # Comenzamos con una lista vacía llist = DoublyLinkedList() # Inserte el elemento 6 para convertirse en Lista # 6->Ninguna llist.append(6) # Inserte el elemento 7 al principio de la lista para que se convierta en # 7->6->None llist.push(7) # Insertamos el elemento 1 al principio de la lista para convertirse. #1->7->6->Ninguna llist.push(1) # Insertamos el elemento 4 al final de la lista para convertirse. #1->7->6->4->Ninguna llist.append(4) # Inserte el elemento 8 después del elemento 7 en la lista para convertirse en #1 ->7->8->6->4->None llist.insertAfter(llist.head.next, 8) print "La DLL creada es: " , llist.printList(llist.head)
// Clasificar la lista de doble hilo public class DLL { Node head; // principio de la lista /* Nodo en una lista de doble hilo*/ class Node { int data; Node prev; Node next; // constructor para crear un nuevo nodo // nulo predeterminado Node(int d) { data = d; } } // agregar un nodo al comienzo de la lista de subprocesos public void push(int new_data) { /* 1. Reserve una ubicación de memoria * 2. agregue datos */ Node new_Node = new Node(new_data); /* 3. NULL Hace que el siguiente nodo nuevo sea el encabezado de la lista y lo que le precede */ new_Node.next = head; new_Node.prev = null; /* 4. Convierte el nodo de encabezado anterior en el nuevo nodo de encabezado */ if (head != null) head.prev = new_Node; /* 5. Mueve la cabeza para que apunte al nuevo nodo */ head = new_Node; } /* La función inserta un nuevo nodo después de un nodo dado */ public void InsertAfter(Node prev_Node, int new_data) { /*1. null Comprobando que el nodo dado es */ if (prev_Node == null) { System.out.println("El nodo anterior dado no puede ser NULL" ); return; } /* 2. Reservar la ubicación del nuevo nodo en la memoria */ /* 3. Agregar datos */ Node new_node = new Node(new_data); /* 4. Hacer que el siguiente nodo sea el siguiente del nodo anterior */ new_node.next = prev_Node.next; /* 5. Hacer que el nuevo nodo siga al nodo anterior */ prev_Node.next = new_node; /* 6. Hacer que el nodo anterior preceda al nuevo nodo */ new_node.prev = prev_Node; /* 7. Cambia lo que precede al nodo que sigue al nuevo nodo */ if (new_node.next != null) new_node.next.prev = new_node; } // La función inserta un nuevo nodo al final de la lista de doble subproceso void append(int new_data) { /* 1. Reservar la ubicación del nodo en la memoria * 2. Agregar datos */ Node new_node = new Node(new_data); Node last = head; /* usado en el paso 5*/ /* 3. NULL Este nodo será el último nodo así que haremos el siguiente */ new_node.next = null; /* 4. Hacer que el nuevo nodo sea el encabezado de la lista si la lista está vacía */ if (head == null) { new_node.prev = null; head = new_node; return; } /* 5. De lo contrario, repasaremos los elementos de la lista hasta el final */ while (last.next != null) last = last.next; /* 6. El nuevo nodo sigue al último nodo de la lista */ last.next = new_node; /* 7. El último nodo de la lista es el que precede al nuevo nodo */ new_node.prev = last; } // Esta función imprime el contenido de la lista de doble subproceso a partir del nodo dado public void printlist(Node node) { Node last = null; System.out.println("Recorrido en dirección de avance" ); while (node != null) { System.out.print(node.data + " "); last = node; node = node.next; } System.out.println(); System.out.println("Recorrido en sentido inverso" ); while (last != null) { System.out.print(last.data + " "); last = last.prev; } } /* Prueba las funciones anteriores*/ public static void main(String[] args) { /* comienza con una lista vacía */ DLL dll = new DLL(); // inserta el elemento 6 para convertirlo en lista // 6-> NULL dll.append(6); // Inserte el elemento 7 al principio de la lista como // 7->6->NULL dll.push(7); // Inserte el elemento 1 al principio de la lista como // 1->7->6->NULL dll.push(1); // Inserte el elemento 4 al final de la lista para convertirlo en // 1->7->6->4->NULL dll.append(4); // Inserte el elemento 8 después del elemento 7 en la lista para convertirlo en // 1->7->8->6->4->NULL dll.InsertAfter(dll.head.next, 8); System.out.println("La DLL creada es:" ); dll.printlist(dll.head); } }
Agregar un nodo antes de un nodo específico
Digamos que el puntero al nodo en particular es next_node
y los datos para agregar el nuevo nodo son new_data
. Se puede agregar un nodo antes de un nodo específico siguiendo estos pasos:
- Comprobando si un valor
next_node
es igualNull
, si lo es detenemos la función porque no se puede añadir un nuevo nodoNull
antes. - Reservamos la memoria necesaria para el nuevo nodo y le damos el nombre
new_node
. - Asigne los datos al nuevo nodo
new_node->data = new_data
. - Configuramos el nodo new_node para que sea el nodo next_node del siguiente nodo anterior de la siguiente manera :
new_node->prev = next_node->prev
. - Establecemos el puntero anterior al nodo
next_node
de la siguiente manera:next_node->prev = new_node
. - Establecemos el puntero del sufijo al nodo
new_node
denext_node
la siguiente manera:new_node->next = next_node
. - Si el nodo anterior no
new_node
existe (es decir, no esNull
), entonces configuramos el puntero después de este nodo anterior para que se convierta ennew_node
, de la siguiente manera:new_node->prev->next = new_node
. - Pero si el nodo anterior
new_node
es el nodoNull
, entonces será el nuevo nodo vertical:(*head_ref) = new_node
.
El siguiente código muestra cómo realizar los pasos anteriores en C++:
#include <stdio.h> #include <stdlib.h> // nodo en una lista encadenada struct Node { int data ; estructura Nodo * siguiente ; estructura Nodo * anterior ; }; /* La función inserta un nuevo nodo al frente de la lista usando una referencia (un puntero a un puntero) al encabezado de la lista y el entero dado */ void push ( struct Node ** head_ref , int new_data ) { struct Nodo * new_node = ( struct Node * ) malloc ( sizeof ) ( struct Node ) ); nuevo_nodo -> datos = nuevos_datos ; nuevo_nodo -> siguiente = ( * head_ref ); nuevo_nodo -> anterior = NULL ; if (( * head_ref ) != NULL ) ( * head_ref ) -> anterior = nuevo_nodo ; ( * head_ref ) = new_node ; } /* La siguiente función inserta un nuevo nodo antes del nodo dado */ void insertBefore ( struct Node ** head_ref , struct Node * next_node , int new_data ) { /*1. null Comprueba que lo que sigue al nuevo nodo es */ if ( next_node == NULL ) { printf ( "el siguiente nodo dado no puede ser NULL" ); volver ; } /* 2. Reserve una ubicación para el nuevo nodo en la memoria */ struct Node * new_node = ( struct Node * ) malloc ( sizeof ( struct Node ))); /* 3. Agregar datos */ new_node -> data = new_data ; /* 4. Hacer que lo que precede al nuevo nodo sea igual a lo que precede al siguiente nodo */ new_node -> prev = next_node -> prev ; /* 5. Hacer que el nuevo nodo preceda al siguiente nodo */ next_node -> prev = new_node ; /* 6. Hacer que el siguiente nodo siga al nuevo nodo */ new_node -> next = next_node ; /* 7. Cambiar el siguiente nodo anterior a un nuevo nodo */ if ( new_node -> prev != NULL ) new_node -> prev -> next = new_node ; /* 8. null Si el nuevo nodo está precedido por él, será el nuevo encabezado */ else (*head_ref) = new_node; } // La función imprime el contenido de la lista enhebrada comenzando desde el nodo dado void printList(struct Node* node) { struct Node* last; printf("\nTraversal in forward direction \n"); while (node != NULL) { printf(" %d ", node->data); last = node; node = node->next; } printf("\nTraversal in reverse direction \n"); while (last != NULL) { printf(" %d ", last->data); last = last->prev; } } /* Probar las funciones anteriores */ int main(){ /* iniciar una nueva lista */ struct Node* head = NULL; push(&head, 7); push(&head, 1); push(&head, 4); // inserta el elemento 8 antes del elemento 1, por lo que la lista se convierte en // 4->8->1->7->NULL insertBefore(&head, head->next, 8); printf("Created DLL is: "); printList(head); getchar(); return 0; }
Eliminar un nodo de una lista de doble subproceso
Si asumimos que el nodo a eliminar es del
, entonces el proceso de eliminación del nodo sigue el siguiente algoritmo:
- Si el nodo a eliminar es el nodo principal, el puntero del encabezado debe moverse al siguiente nodo.
- Establezca el nodo que sigue al nodo anterior del nodo eliminado, si hay un nodo anterior.
- Establezca el nodo anterior en el nodo que sigue al nodo eliminado, si hay un nodo posterior.
La complejidad temporal de este algoritmo es O(1)
.
Ejemplos y aplicaciones en código
Los siguientes ejemplos muestran cómo eliminar un nodo de una lista de doble subproceso y en varios lenguajes de programación:
#include <bits/stdc++.h> using namespace std; /* Nodo en una lista de doble subproceso */ class Node { public: int data; Node* next; Node* prev; } /* Esta función elimina un nodo de la lista de doble subproceso head_ref --> puntero al puntero del nodo del encabezado. del --> Un puntero al nodo a eliminar. */ void deleteNode(Node** head_ref, Node* del) { /* condición base */ if (*head_ref == NULL || del == NULL) return; /* si el nodo a eliminar es el nodo principal */ if (*head_ref == del) *head_ref = del->next; /* Si el nodo a eliminar no es el último nodo, cambiaremos lo siguiente */ if (del->next != NULL) del->next->prev = del->prev; /* Si el nodo a borrar no es el primero, cambiaremos el que le precede */ if (del->prev != NULL) del->prev->next = del->next; /* Vaciar de memoria la parte ocupada por el nodo a borrar */ free(del); return; } /* Funciones auxiliares */ /* Esta función inserta un nodo al principio de la lista de doble subproceso */ void push(Node** head_ref, int new_data) { /* Reserva la ubicación del nodo en la memoria */ Node* new_node = new Node(); /* agregar datos */ new_node->data = new_data; /* NULL Ya que el nodo agregado está al principio de la lista, está precedido por */ new_node->prev = NULL; /* vincular la lista anterior con el nuevo nodo */ new_node->next = (*head_ref); /* Hacer que el nuevo nodo preceda al nodo principal */ if ((*head_ref) != NULL) (*head_ref)->prev = new_node; /* Mueve el encabezado de la lista para que apunte al nuevo nodo */ (*head_ref) = new_node; } /* La función imprime los nodos en la lista de doble hilo */ void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } /* prueba las funciones anteriores */ int main() { /* nueva lista de doble subproceso */ Node* head = NULL; /* Crea la siguiente lista de doble hilo: 10<->8<->4<->2 */ push(&head, 2); push(&head, 4); push(&head, 8); push(&head, 10); cout << "Lista enlazada original" ; printList(head); /* Eliminar nodos de la lista de doble subproceso */ deleteNode(&head, head); /* elimina el primer nodo */ deleteNode(&head, head->next); /*Eliminar un nodo en medio de la lista*/ deleteNode(&head, head->next); /*Eliminar el último nodo*/ /* La lista enlazada después de las modificaciones: NULL<-8->NULL */ cout << "\n Lista enlazada modificada " ; printList(head); return 0; }
# Recolector de basura de importación import gc # Nodo en la clase de lista de doble subproceso class Node: # Función del constructor para crear un nuevo nodo def __init__(self, data): self.data = data self.next = None self.prev = None class DoublyLinkedList: # Función de creación para crear una lista vacía de subprocesos def __init__(self): self.head = None # Esta función elimina un nodo de la lista de doble subproceso # head_ref --> puntero al puntero al nodo de encabezado. # eliminar --> Puntero al nodo a eliminar def deleteNode(self, dele): # requisito previo if self.head is None or dele is None: return # Si el nodo a eliminar es el nodo principal if self.head == dele: self.head = dele.next # Si el nodo a eliminar no es el último nodo, cambiaremos lo siguiente if dele.next is not None: dele.next.prev = dele.prev # Si el nodo a eliminar no es el primer nodo, cambiaremos lo que le precede if dele.prev is not None: dele.prev.next = dele.next # Vaciar la parte ocupada por el nodo a borrar de la memoria # Llamar a la función de recolección de basura en Python gc.collect() # Esta función inserta un nodo al frente de la lista de doble subproceso def push(self, new_data): # 1. Reservar la ubicación del nodo en la memoria # 2. Agregar datos new_node = Node(new_data) # 3. Ninguno Haga que lo que sigue al nuevo nodo sea el encabezado de la lista y lo que viene antes sea new_node.next = self.head # 4. Haga que el nuevo nodo preceda al nodo principal if self.head is not None: self.head.prev = new_node # 5. Mueva el encabezado de la lista para que apunte al nuevo nodo self.head = new_node def printList(self, node): while(node is not None): print node.data, node = node.next # Probar las funciones anteriores # nueva lista de subprocesos dll = DoublyLinkedList() # Cree la siguiente lista de subprocesos # 10<->8<->4<->2 dll.push(2); dll.push(4); dll.push(8); dll.push(10); print " \n Lista enlazada original" , dll.printList(dll.head) # Eliminar nodos de la lista de doble subproceso dll.deleteNode(dll.head) dll.deleteNode(dll.head.next) dll.deleteNode(dll.head.next) # Lista enlazada modificada: # NULL<-8->NULL print " \n Lista enlazada modificada" , dll.printList(dll.head)
// Clasificar la lista de doble hilo public class DLL { Node head; // al principio de la lista /* Nodo en la lista de doble subproceso */ class Node { int data; Node prev; Node next; // constructor para crear un nuevo nodo // nulo Predeterminado a Node(int d) { data = d; } } // agrega un nodo al principio de la lista de subprocesos public void push(int new_data) { /* 1. Reservar ubicación de memoria * 2. Agregar datos */ Node new_Node = new Node(new_data); /* 3. NULL Hace que el siguiente nodo nuevo sea el encabezado de la lista y lo que le precede */ new_Node.next = head; new_Node.prev = null; /* 4. Convierte el nodo de encabezado anterior en el nuevo nodo de encabezado */ if (head != null) head.prev = new_Node; /* 5. Mueve la cabeza para que apunte al nuevo nodo */ head = new_Node; } // Esta función imprime el contenido de la lista de doble subproceso a partir del nodo dado public void printlist(Node node) { Node last = null; while (node != null) { System.out.print(node.data + " "); last = node; node = node.next; } System.out.println(); } /* Esta función elimina un nodo de la lista de doble subproceso head_ref --> puntero al puntero del nodo del encabezado. del --> Un puntero al nodo a eliminar. */ void deleteNode(Node head_ref, Node del) { // requisito previo if (head == null || del == null) { return; } /* si el nodo a eliminar es el nodo principal */ if (head == del) { head = del.next; } /* Si el nodo a eliminar no es el último nodo, cambiaremos lo siguiente */ if (del.next != null) { del.next.prev = del.prev; } /* Si el nodo a borrar no es el primero, cambiaremos el que le precede */ if (del.prev != null) { del.prev.next = del.next; } /* Vaciar de memoria la parte ocupada por el nodo a borrar */ return; } // prueba las funciones anteriores public static void main(String[] args) { // comienza con una nueva lista de doble subproceso DLL dll = new DLL(); /* Crea la siguiente lista de subprocesos dobles: 10<->8<->4<->2 */ dll.push(2); dll.push(4); dll.push(8); dll.push(10); System.out.print("La DLL creada es:" ); dll.printlist(dll.head); // elimina la dll del primer nodo dll.deleteNode(dll.head, dll.head); /* Lista encadenada después de las modificaciones: NULL<-8->NULL */ System.out.print("\nLista después de eliminar el primer nodo: " ); dll.printlist(dll.head); // elimina la dll del nodo medio dll.deleteNode(dll.head, dll.head.next); System.out.print("\nLista después de eliminar el nodo medio: " ); dll.printlist(dll.head); } }
Como resultado del ejemplo del código anterior obtendremos:
Lista enlazada original 10 8 4 2 Lista enlazada modificada 8
Voltear los elementos de una lista de doble hilo
Lo que necesitamos para voltear los elementos de una lista de doble subproceso es cambiar los punteros anterior y posterior de cada nodo, cambiar lo que precede al nodo de encabezado y cambiar el puntero de encabezado al final de la lista. La complejidad temporal de este algoritmo es O(n)
.
También es posible cambiar datos en lugar de punteros para voltear los elementos de una lista encadenada, utilizando los métodos que se usan para voltear matrices, pero debe tenerse en cuenta que cambiar datos es costoso en comparación con punteros si la cantidad de datos es grande. Los siguientes ejemplos muestran cómo voltear elementos de una lista de doble subproceso en varios lenguajes de programación:
#include <bits/stdc++.h> using namespace std; /* Nodo en la lista de doble hilo */ class Node { public: int data; Node *next; Node *prev; } /* Función que invierte los nodos de la lista de doble hilo */ void reverse(Node **head_ref) { Node *temp = NULL; Node *current = *head_ref; /* Cambia los índices anterior y posterior de todos los nodos en la lista de doble subproceso */ while (current != NULL) { temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } /* Antes de cambiar el encabezado de la lista, verifique que la lista esté vacía o contenga solo un nodo */ if(temp != NULL ) *head_ref = temp->prev; } /* Funciones auxiliares */ /* Esta función inserta un nodo al principio de la lista de doble subproceso */ void push(Node** head_ref, int new_data) { /* Reserva la ubicación del nodo en la memoria */ Node* new_node = new Node(); /* agregar datos */ new_node->data = new_data; /* NULL Ya que el nodo agregado está al principio de la lista, está precedido por */ new_node->prev = NULL; /* vincular la lista anterior con el nuevo nodo */ new_node->next = (*head_ref); /* Hacer que el nuevo nodo preceda al nodo principal */ if ((*head_ref) != NULL) (*head_ref)->prev = new_node; /* Mueve el encabezado de la lista para que apunte al nuevo nodo */ (*head_ref) = new_node; } /* La función imprime los nodos en la lista de doble hilo */ void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } /* prueba las funciones anteriores */ int main() { /* nueva lista de subprocesos */ Node* head = NULL; /* Crea la siguiente lista de doble hilo: 10<->8<->4<->2 */ push(&head, 2); push(&head, 4); push(&head, 8); push(&head, 10); cout << "Lista enlazada original#69DBAC" << endl; printList(head); /* Invierte los elementos en la lista enlazada */ reverse(&head); cout << "\nLista enlazada invertida" << endl; printList(head); return 0; }
# Nodo en la clase de lista de doble subproceso class Node: # Función del constructor para crear un nuevo nodo def __init__(self, data): self.data = data self.next = None self.prev = None class DoublyLinkedList: # Función de creación para crear una nueva lista de subprocesos def __init__(self): self.head = None # Función para voltear elementos de una lista de doble subproceso def reverse(self): temp = None current = self.head # Alterne los índices anterior y posterior de todos los nodos en la lista de doble subproceso while current is not None: temp = current.prev current.prev = current.next current.next = temp current = current.prev # Antes de cambiar el encabezado de la lista, verifique si la lista está vacía o contiene solo un nodo if temp is not None: self.head = temp.prev # Esta función inserta un nodo al frente de la lista de doble subproceso def push(self, new_data): # 1. Reservar la ubicación del nodo en la memoria # 2. Agregar datos new_node = Node(new_data) # 3. Ninguno Haga que lo que sigue al nuevo nodo sea el encabezado de la lista y lo que viene antes sea new_node.next = self.head # 4. Haga que el nuevo nodo preceda al nodo principal if self.head is not None: self.head.prev = new_node # 5. Mueva el encabezado de la lista para que apunte al nuevo nodo self.head = new_node def printList(self, node): while(node is not None): print node.data, node = node.next # Probar las funciones anteriores dll = DoublyLinkedList() dll.push(2); dll.push(4); dll.push(8); dll.push(10); print "\nLista enlazada original" dll.printList(dll.head) # Invertir elementos de lista de doble subproceso dll.reverse() print "\n Lista enlazada invertida" dll.printList(dll.head)
class LinkedList { static Node head; static class Node { int data; Node next, prev; Node(int d) { data = d; next = prev = null; } } /* Una función que invierte los elementos de una lista de doble hilo */ void reverse() { Node temp = null; Node current = head; /* Cambia los índices anterior y posterior de todos los nodos en la lista de doble subproceso */ while (current != null) { temp = current.prev; current.prev = current.next; current.next = temp; current = current.prev; } /* Cambia los punteros anterior y póstumo a todos los nodos en la lista de doble subproceso */ if (temp != null) { head = temp.prev; } } /* Funciones auxiliares */ // Agregar un nodo al principio de la lista de hilos public void push(int new_data) { /* 1. Reservar ubicación de memoria * 2. Agregar datos */ Node new_Node = new Node(new_data); /* 3. NULL Hace que el siguiente nodo nuevo sea el encabezado de la lista y lo que le precede */ new_Node.next = head; new_Node.prev = null; /* 4. Convierte el nodo de encabezado anterior en el nuevo nodo de encabezado */ if (head != null) head.prev = new_Node; /* 5. Mueve la cabeza para que apunte al nuevo nodo */ head = new_Node; } // Esta función imprime el contenido de la lista de doble subproceso a partir del nodo dado public void printlist(Node node) { Node last = null; while (node != null) { System.out.print(node.data + " "); last = node; node = node.next; } System.out.println(); } public static void main(String[] args) { LinkedList list = new LinkedList(); /* Crea la siguiente lista de subprocesos dobles: 10<->8<->4<->2 */ list.push(2); list.push(4); list.push(8); list.push(10); System.out.println( "Lista enlazada original" ); list.printList(head); list.reverse(); System.out.println(""); System.out.println( "La lista enlazada invertida es" ); list.printList(head); } }
El código anterior da el siguiente resultado:
Lista enlazada original 10 8 4 2 La lista enlazada invertida es 2 4 8 10
Fuente de Recursos
- La página documentación de estructura de datos de GeeksforGeeks Introducción e inserción de listas doblemente vinculadas.
- La página documentación de estructura de datos de GeeksforGeeks Eliminar un nodo en una lista doblemente vinculada.
- La página documentación de estructura de datos de GeeksforGeeks Invierta una lista doblemente vinculada.