Lista Doblemente Enlazada

por

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.

Listas Doblemente Enlazadas
Listas Doblemente Enlazadas

Tabla de contenidos

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:

  1. Los elementos del menú doble se pueden desplazar tanto hacia adelante como hacia atrás.
  2. La operación de eliminación en listas pareadas es más eficiente si se especifica el puntero al nodo que se eliminará.
  3. Se puede insertar un nuevo nodo antes de un nodo dado rápidamente.
  4. 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

  1. 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.
  2. 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:

  1. Al comienzo de la lista de doble hilo.
  2. después de cierto nodo.
  3. Al final de la lista de doble hilo.
  4. antes de un nodo en particular.

Agregar un nodo al principio de la lista

Agregar un nodo al principio de la lista
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:

  1. Comprobando si un valor next_node es igual Null, si lo es detenemos la función porque no se puede añadir un nuevo nodo Null antes.
  2. Reservamos la memoria necesaria para el nuevo nodo y le damos el nombre new_node.
  3. Asigne los datos al nuevo nodo new_node->data = new_data.
  4. 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.
  5. Establecemos el puntero anterior al nodo next_node de la siguiente manera: next_node->prev = new_node.
  6. Establecemos el puntero del sufijo al nodo new_node de next_node la siguiente manera: new_node->next = next_node.
  7. Si el nodo anterior no new_node existe (es decir, no es Null), entonces configuramos el puntero después de este nodo anterior para que se convierta en new_node, de la siguiente manera: new_node->prev->next = new_node.
  8. Pero si el nodo anterior new_node es el nodo Null, 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:

  1. Si el nodo a eliminar es el nodo principal, el puntero del encabezado debe moverse al siguiente nodo.
  2. Establezca el nodo que sigue al nodo anterior del nodo eliminado, si hay un nodo anterior.
  3. 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