Lista doblemente enlazada: C++, Python (Ejemplo de código)

¿Qué es una lista doblemente enlazada?

En una lista doblemente enlazada, cada nodo tiene enlaces tanto al nodo anterior como al siguiente. Cada nodo consta de tres elementos: uno contiene los datos y otros dos son los punteros del nodo siguiente y anterior. Estos dos indicadores nos ayudan a avanzar o retroceder desde un nodo en particular.

Aquí está la estructura básica de la lista doblemente enlazada.

Cada lista enlazada tiene un nodo principal y otro final. El nodo principal no tiene un nodo "anterior" (puntero anterior) y el nodo de cola no tiene un nodo "siguiente".

A continuación se muestran algunos términos importantes para una lista doblemente enlazada:

• Anterior: Cada nodo está vinculado a su nodo anterior. Se utiliza como puntero o enlace.
• Siguiente: Cada nodo está vinculado a su siguiente nodo. Se utiliza como puntero o enlace.
• Fecha: Esto se utiliza para almacenar datos en un nodo. Los “datos” pueden contener otros Estructuras de datos dentro de eso. Por ejemplo, cadenas, diccionarios, conjuntos, mapas hash, etc. se pueden almacenar en "Datos".

Aquí está la estructura básica de un solo nodo en la lista doblemente enlazada:

Operaciones de lista doblemente enlazada

Las operaciones de una lista doblemente enlazada incluyen agregar y eliminar nodos, insertar y eliminar nodos y recorrer la lista enlazada de arriba a abajo.

Aquí está la lista de operaciones que podemos implementar usando la lista doblemente enlazada:

• Inserción delante
• Inserción en la cola o último nudo.
• Inserción después de un nodo
• Inserción antes de un nodo
• Eliminación desde el frente
• Eliminación de la cola
• Buscar y eliminar un nodo
• Atravesar de cabeza a cola
• Atravesar la cola hasta la cabeza

Veremos la implementación y el pseudocódigo de todas las operaciones anteriores.

Inserción delante de la lista doblemente enlazada

La inserción al frente significa que necesitamos crear un nodo en la lista vinculada y colocarlo al principio de la lista vinculada.

Por ejemplo, hay un nodo determinado "15". Necesitamos agregar esto al nodo principal.

Aquí hay dos condiciones importantes al realizar esta operación:

1. El nuevo nodo será el nodo principal si no hay ningún nodo en la Lista Doblemente Enlazada.
2. Si ya existe un nodo principal, el anterior será reemplazado por el nuevo nodo.

Aquí está el pseudocódigo para esta operación:

function insertAtFront (ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = NewNode
  NewNode.next = ListHead
  newNode.prev = NULL
  return ListHead

Inserción al final de la Lista Doblemente Enlazada

"Inserción al final" significa que crearemos un nodo en la lista vinculada y lo colocaremos al final.

Para realizar esto, podemos utilizar dos métodos:

• Método 1: Comience a recorrer desde el principio de la Lista doblemente enlazada hasta que el "siguiente" se vuelva nulo. Luego vincule el nuevo nodo con el “siguiente”.
• Método 2: Tome el último nodo de la Lista Doblemente Enlazada. Luego, el "siguiente" nodo del último nodo se vinculará al nuevo nodo. Ahora, el nuevo nodo será el nodo de cola.

Aquí está el pseudocódigo para insertar en el nodo de cola:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
	then ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Inserción después de un nodo

Digamos que tenemos una lista doblemente enlazada existente como la siguiente:

Queremos insertar un nodo determinado que se vinculará después del nodo, que tiene el valor de "12".

Estos son los pasos para esto:

Paso 1) Atraviesa desde la cabeza hasta el último nodo. Compruebe qué nodo tiene el valor “12”.

Paso 2) Cree un nuevo nodo y asígnelo como el siguiente puntero del nodo "12". El "siguiente" nodo del nuevo nodo será el 15.

Aquí está el pseudocódigo para insertar un nodo después de un nodo en una lista doblemente enlazada:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  NewNode = Node()
  NewNode.value = value
  while List.value is not equal searchItem
	then List = ListHead.next
  List = List.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode

Inserción antes de un nodo

Esta operación es más parecida a la “inserción después de un nodo”. Necesitamos buscar el valor de un nodo específico para realizar esto. Luego crearemos un nuevo nodo y lo insertaremos antes del nodo buscado.

Digamos que queremos insertar un nodo "15" determinado antes del nodo "12". Entonces estos son los pasos para hacerlo:

Paso 1) Recorra la lista vinculada desde el nodo principal hasta el nodo final.

Paso 2) Compruebe si el siguiente puntero del nodo actual tiene el valor "12" o no.

Paso 3) Inserte el nuevo nodo como el "siguiente" nodo del nodo actual.

Aquí está el pseudocódigo para insertar un nodo antes de un nodo en una lista doblemente enlazada:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  NewNode = Node()
  NewNode.value = value
  while List.next.value is not equal searchItem
	then List = ListHead.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode

Eliminar el encabezado de la lista doblemente enlazada

El nodo principal de la lista doblemente enlazada que no tiene ningún nodo anterior. Entonces, el siguiente puntero será el nuevo nodo principal si queremos eliminar el nodo principal. También necesitamos liberar la memoria ocupada por un nodo mientras eliminamos un nodo.

Estos son los pasos para eliminar el nodo principal:

Paso 1) Asigne una variable al nodo principal actual.

Paso 2) Visite el nodo "siguiente" del nodo principal actual y convierta el nodo "anterior" (puntero anterior) en "NULL". Esto significa que estamos desconectando el segundo nodo del primer nodo.

Paso 3) Libere la memoria ocupada por el nodo principal anterior.

Aquí está el pseudocódigo para eliminar el encabezado de una lista doblemente enlazada:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

Es necesario eliminar la memoria asignada después de realizar cualquier tipo de operación de eliminación. De lo contrario, durante todo el tiempo de ejecución del programa, la memoria del bloque eliminado permanecerá ocupada. Ninguna otra aplicación puede utilizar ese segmento de memoria.

Elimina la cola de la lista doblemente enlazada.

Esta operación es similar a la eliminación de la cabeza. Aquí, en lugar de la cabeza, debemos eliminar la cola. Para identificar un nodo como nodo de cola, debemos verificar si el siguiente puntero o el siguiente nodo es nulo o no. Después de eliminar la cola, necesitamos liberar memoria.

Esta operación también se conoce como “eliminación desde atrás”.

Estos son los pasos para hacer esto:

Paso 1) Atraviese hasta el nodo final de la lista doblemente enlazada.

Paso 2) Asigne una variable o puntero al nodo de cola.

Paso 3) Haga que el "siguiente" nodo sea NULL y libere la memoria del nodo de cola.

Aquí está el pseudocódigo para eliminar el nodo de cola:

function DeleteTail( ListHead ):
  head = ListHead
  while ListHead.next is not NULL:
	ListHead = ListHead.next
  Tail = ListHead.next
  ListHead.next = NULL
  free memory( Tail )
  return head

Buscar y eliminar un nodo de la Lista doblemente enlazada

Esta operación nos permite buscar datos de un nodo específico y eliminar ese nodo. Necesitamos realizar una búsqueda lineal ya que la lista vinculada es una estructura de datos lineal. Después de eliminar, también necesitamos liberar memoria.

Estos son los pasos para buscar y eliminar un nodo en la lista doblemente enlazada:

Paso 1) Recorra la lista vinculada desde el encabezado hasta que el valor del nodo sea igual al elemento de búsqueda.

Paso 2) Asigne una variable "deleteNode" al nodo coincidente.

Paso 3) Asigne el nodo anterior de "deleteNode" al siguiente nodo.

Paso 4) Liberar la memoria del “deleteNode”

Aquí está el pseudocódigo para buscar y eliminar un nodo de una lista enlazada:

function SearchAndDelete(ListHead, searchItem):
  head = ListHead
  while ListHead.next.value not equals searchItem:
	head = head.next
  deleteNode = head.next
  head.next = head.next.next
  head.next.prev = head
  deleteNode.next, deleteNode.next = NULL
  free memory(deleteNode)
  return ListHead

Recorrer una lista doblemente enlazada desde adelante

Para atravesar desde el nodo principal e iterar sobre el siguiente nodo hasta encontrar "NULL". Mientras atravesamos cada nodo, podemos imprimir el valor del nodo. Estos son los pasos para atravesar desde el frente (dirección de avance):

Paso 1) Asigne un puntero o variable al nodo principal actual.

Paso 2) Iterar hasta el siguiente nodo del encabezado hasta obtener "NULL"

Paso 3) Imprime los datos del nodo en cada iteración.

Paso 4) Devuelve el nodo principal.

Aquí está el pseudocódigo para recorrer una lista doblemente enlazada desde el frente:

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals to NULL:
	print head.data
	head = head.next
  return ListHead

Aquí la devolución no es obligatoria. Pero es una buena práctica devolver el nodo principal después de las operaciones.

Recorrer una lista doblemente enlazada desde atrás

Esta operación es la inversa de la transversal desde el frente. El enfoque es el mismo con una pequeña diferencia. Debemos atravesar hasta el nodo final y luego atravesar desde el nodo final hasta el nodo frontal.

Estos son los pasos para recorrer una lista doblemente enlazada desde la parte posterior:

Paso 1) Atraviesa hasta llegar al nodo de la cola.

Paso 2) Desde el nodo de cola, atravesaremos hasta obtener el nodo anterior como "NULL". El “prev” (puntero anterior) será nulo para el nodo principal

Paso 3) En cada iteración, imprimiremos los datos del nodo.

Aquí está el pseudocódigo para atravesar desde atrás:

function traverseFromBack(ListHead):
  head = ListHead
  while head not equals NULL:
	head = head.next
  tail = head
  while tail not equal to NULL:
	print tail.value
	tail = tail.prev
  return ListHead

Diferencia entre lista simple y doblemente enlazada

La principal diferencia entre la lista de enlaces individuales y doblemente enlazados es la cantidad de enlaces.

Aquí está la diferencia entre los nodos de una lista individualmente enlazada y la estructura de nodos de una lista doblemente enlazada:

Campo	Lista individualmente vinculada	Lista doblemente vinculada
Estructura	Lista individualmente vinculada tiene un campo de datos y un enlace al siguiente nodo.	La lista doblemente enlazada tiene un campo de datos y dos enlaces. Uno para el nodo anterior y otro para el siguiente nodo.
Travesía	Sólo puede atravesar de la cabeza a la cola.	Puede atravesar tanto hacia adelante como hacia atrás.
Salud Cerebral	Ocupa menos memoria.	Ocupa más memoria que una lista enlazada individualmente.
Accesibilidad	Las listas enlazadas individualmente son menos eficientes ya que utilizan solo un enlace al siguiente nodo. No hay ningún enlace para el nodo anterior.	Las listas doblemente enlazadas son más eficientes que las listas individualmente enlazadas.

Lista doblemente enlazada en C++

#include<iostream>
using namespace std;
  struct node{
  int data;
  struct node *next;
  struct node *prev;
  };
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead!=NULL)
  {
	listHead->prev = newNode;
  	newNode->next = listHead;
  }
  
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
  }
void insertEnd(node * &listHead, int value){
  if(listHead==NULL)
  {
  	insertFront(listHead,value);
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next!=NULL){
  head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
  }
void insertAfter(node * &listHead, int searchValue,int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;	
  newNode->next = NULL;
  node *head = listHead;	
  while(head->next!=NULL &&  head->data!=searchValue){	
  head = head->next;	
  }	
  newNode->next = head->next;	
  head->next = newNode;	
  newNode->prev = head;	
  if(newNode->next !=NULL){	
  newNode->next->prev = newNode;	
  }	
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
  }
void insertBefore(node * &listHead, int searchValue,int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;	
  newNode->next = NULL;	
  node *head = listHead;	
  while(head->next!=NULL &&  head->next->data!=searchValue){	
  head = head->next;	
  }	
  newNode->next = head->next;	
  head->next = newNode;	
  newNode->prev = head;	
  if(newNode->next !=NULL){	
  newNode->next->prev = newNode;	
  }	
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;	
  }
void traverseFromFront(node *listHead){
  node* head = new node();
  head = listHead;
  cout<<"Traversal from head:\t";	
  while(head!=NULL){	
  cout<<head->data<<"\t ";	
  head = head->next;	
  }	
  cout<<endl;
  }	
void traverseFromEnd(node *listHead){
  node* head = new node();
  head = listHead;	
  cout<<"Traversal from head:\t";	
  while(head->next!=NULL){	
  head = head->next;	
  }	
  node *tail = head;	
  while(tail!=NULL){	
  cout<<tail->data<<"\t";	
  tail = tail->prev;	
  }	
  cout<<endl;	
  }
void searchAndDelete(node **listHead, int searchItem){
  node* head = new node();
  head = (*listHead);
  while(head->next!=NULL &&  head->data!=searchItem){
  head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
  	*listHead = head->next;
  }
  if(head->next != NULL){
  	head->next->prev = head->prev;
  }
  
  if(head->prev != NULL){
  	head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
  }
int main(){
  node *head = NULL;
  insertFront(head,5);
  insertFront(head,6);
  insertFront(head,7);
  insertEnd(head,9);
  insertEnd(head,10);
  insertAfter(head,5,11);
  insertBefore(head,5,20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head,7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

Salida

Added 5 at the front
Added 6 at the front
Added 7 at the front
Aded 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7        6       20      5       11      9       10
Traversal from head:    10      9       11      5       20      6       7
Deleted Node    7
Traversal from head:    6        20      5       11      9       10
Traversal from head:    10      9       11      5       20      6

Lista doblemente enlazada en Python

class node:
  def __init__(self,data = None, prev=None, next = None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None

  def insertFront(self, val):
    newNode = node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))

  def insertEnd(self,val):
    newNode = node(data=val)
    if self.head is None:
      self.insertFront(val)
    
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))

  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t",end="")
    while temp:
      print("{}\t".format(temp.data),end="")
      temp = temp.next
    print()

  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from Tail:\t",end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data),end="")
      tail = tail.prev
    print()
  
  def insertAfter(self,searchItem, value):
    newNode = node(data=value)

    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp

    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value,searchItem))

  def insertBefore(self,searchItem, value):
    newNode = node(data=value)

    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp

    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value,searchItem))

  def searchAndDelete(self,searchItem):
    temp = self.head

    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    if self.head is None or temp is None:
      return

    if self.head.data is temp.data:
      self.head = temp.next

    if temp.next is not None:
      temp.next.prev = temp.prev
    
    if temp.prev is not None:
      temp.prev.next = temp.next
    
    print("Deleted Node\t{}".format(searchItem))
    return

doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

Salida

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7       6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6       7
Deleted Node    7
Traversing from head:   6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6

Complejidad de una lista doblemente enlazada

Generalmente, la complejidad del tiempo se divide en tres tipos.

Ellos son:

1. Mejores casos
2. Caso promedio
3. Peor de los casos

Complejidad temporal en el mejor caso para lista doblemente enlazada:

1. La inserción en el nodo de cabeza o de cola costará O(1), ya que no necesitamos recorrer el interior de la lista enlazada. El puntero de cabeza y de cola nos puede dar acceso al nodo de cabeza y de cola con una complejidad de tiempo O(1).
2. La eliminación al principio o al final costará O (1).
3. La búsqueda de un nodo tendrá una complejidad temporal de O(1), ya que el nodo de destino puede ser el nodo principal.

Complejidad temporal en el caso promedio de lista doblemente enlazada:

1. La inserción en la cabeza o en la cola tendrá una complejidad temporal de coste O(1).
2. La eliminación al principio o al final tendrá una complejidad temporal de coste O(1).
3. La búsqueda de un nodo tendrá una complejidad temporal de O(n), ya que el elemento de búsqueda puede estar en cualquier lugar de la lista enlazada. Aquí, “n” es el total de nodos presentes en la lista enlazada.

La complejidad temporal del peor caso de la lista doblemente enlazada será la misma que la del caso promedio.

Complejidad de memoria de una lista doblemente enlazada

La complejidad de la memoria es O(n), donde “n” es el número total de nodos. Al implementar la lista enlazada, debemos liberar la memoria que usamos. De lo contrario, para una lista enlazada más grande, se producirán fugas de memoria.

Resumen

• Una lista enlazada es una especie de estructura de datos lineal, una colección de datos representados de forma lineal.
• Una lista doblemente enlazada es un tipo de lista enlazada en la que un nodo tiene enlaces tanto con el nodo anterior como con el siguiente.
• La lista doblemente enlazada contiene todas las operaciones, como agregar un nodo, eliminar un nodo, insertar un nodo antes o después de otro nodo y recorrer la lista enlazada de principio a fin.
• La lista doblemente enlazada tiene un campo de datos y dos enlaces. Uno para el nodo anterior y otro para el siguiente nodo.
• Complejidad de la lista doblemente enlazada Caso Mejores, Caso Promedio
• Y el peor de los casos.