单链表结点中只有一个指向其后继的指针，使得单链表只能从前往后依次遍历。要访问某个结点的前驱(插入、删除操作时)，只能从头开始遍历，访问前驱的时间复杂度为 O(n)。
为了克服单链表的这个缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其直接前驱和直接后继。

双链表的主要特性

双向遍历由于每个节点都有前后两个指针，因此可以在列表中双向遍历，无需像单链表那样只能从头节点开始向前遍历。
插入与删除的便捷性：在双链表中插入或删除一个节点时，只需改变相应节点的前后节点的指针指向即可，操作相对简单高效。

数据结构

data：数据域，也是节点的值
prior：指针域，指向前一个结点的指针
next：指针域，指向下一个结点的指针

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct DNode {
  int data; // 数据
  struct DNode *prior, *next; // 前驱和后继指针
} DNode, *DLinkList;
pTemp = (DNode *)malloc(sizeof(DNode));
pTemp->data = x;
pTemp->next = pHead->next;
pTemp->prior = pHea
// 完整代码：https://totuma.cn

链表结构

💡双链表在单链表结点中增加了一个指向其前驱的指针prior ，因此双链表的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为“链”变化时也需要对指针 prior 做出修改，其关键是保证在修改的过程中不断链。 此外,双链表可以很方便地找到当前结点的前驱，因此，插入、除操作的时间复杂度仅为 O(1)。

双链表的基本操作实现

单链表的节点在需要时动态分配内存，这意味着不需要像数组那样在创建时预先分配一大片连续内存。因此，单链表在内存使用上更加灵活，可以有效应对内存碎片和动态增长的问题。

由于链表节点是在需要时分配的，可以避免数组因初始化大小不确定而造成的内存浪费。例如，如果数组大小初始化过大，未使用的部分将浪费内存；若初始化过小，则可能需要频繁重新分配和复制。

每个节点需要一个指针域来存储对下一个节点的引用，这意味着相比于数组，单链表在每个节点上都会有额外的内存开销。对于存储小数据的场景，这个开销相对较大，可能导致内存利用率下降。

按位序插入结点

该函数用于在双向链表中按指定位置插入一个新元素。(注意区分位置和下标：位置从1开始，下标从0开始)

在位置 i 插入元素 e，其中 i=1 表示插入到表头，i=length+1 表示插入到表尾。

重点注意下链表为空和不为空时的处理逻辑

插入时链表空和不空时的区别

按位序插入结点 | 可视化完整可视化

2.3 Explicación detallada de la lista enlazada doble - Tutorial de Listas Lineales Visualiza tu código con animaciones

```html

Listas Enlazadas: La Guía Completa para Entender y Visualizar esta Estructura de Datos

Bienvenido al mundo de las estructuras de datos. Si estás aprendiendo algoritmos y programación, seguramente te has encontrado con el concepto de "lista enlazada" (linked list). Este artículo está diseñado especialmente para estudiantes de habla hispana que quieren dominar esta estructura de datos fundamental. Vamos a explicar de forma clara y sencilla qué es, cómo funciona, sus ventajas, desventajas y, lo más importante, cómo puedes usar un plataforma de visualización de algoritmos para entenderla de manera interactiva.

¿Qué es una Lista Enlazada? (Linked List)

Una lista enlazada es una estructura de datos lineal, similar a un array, pero con una diferencia clave: los elementos no se almacenan en posiciones contiguas de memoria. En lugar de eso, cada elemento (llamado "nodo") contiene dos partes: el dato que queremos guardar y un puntero (o enlace) que apunta al siguiente nodo de la secuencia. Esta conexión forma una cadena, de ahí el nombre "lista enlazada".

Imagina una fila de vagones de tren. Cada vagón está enganchado al siguiente. Si quieres añadir un vagón en medio, no necesitas mover todos los vagones, solo ajustar los enganches. Eso es exactamente lo que hace una lista enlazada: permite inserciones y eliminaciones eficientes sin reorganizar toda la estructura.

Tipos de Listas Enlazadas

Existen varias variantes, cada una con sus propias reglas:

1. Lista Simplemente Enlazada (Singly Linked List)

Cada nodo tiene un solo puntero que apunta al siguiente nodo. El último nodo apunta a null (o None). Solo puedes recorrer la lista hacia adelante.

2. Lista Doblemente Enlazada (Doubly Linked List)

Cada nodo tiene dos punteros: uno al siguiente nodo y otro al nodo anterior. Esto permite recorrer la lista en ambas direcciones (adelante y atrás). Es más flexible pero ocupa más memoria.

3. Lista Circular Enlazada (Circular Linked List)

El último nodo apunta de vuelta al primer nodo, formando un círculo. Puede ser simplemente enlazada o doblemente enlazada. Es útil para aplicaciones como el round-robin scheduling.

Principios Fundamentales de Funcionamiento

Para entender cómo funciona una lista enlazada, debes conocer tres operaciones básicas:

Inserción

Para insertar un nuevo nodo al inicio, solo necesitas crear el nodo y hacer que su puntero apunte al antiguo primer nodo. Luego actualizas la cabeza de la lista. Si insertas al final, recorres toda la lista hasta el último nodo y haces que su puntero apunte al nuevo nodo. Insertar en medio requiere ajustar los punteros de los nodos adyacentes.

Eliminación

Para eliminar un nodo, ajustas el puntero del nodo anterior para que "salte" el nodo eliminado y apunte al siguiente. Si el nodo es el primero, actualizas la cabeza. En una lista doblemente enlazada, también debes actualizar el puntero anterior del nodo siguiente.

Búsqueda

Para buscar un valor, debes recorrer la lista desde la cabeza, nodo por nodo, hasta encontrar el dato deseado o llegar al final. Esto se llama "recorrido lineal" y tiene complejidad O(n) en el peor caso.

Ventajas y Desventajas de las Listas Enlazadas

Ventajas

Inserción y eliminación eficientes: No necesitas desplazar elementos como en un array. Especialmente al inicio o en medio (si tienes una referencia al nodo anterior).
Tamaño dinámico: No tienes que definir un tamaño fijo. La lista crece y se reduce según sea necesario.
Utilización flexible de memoria: Los nodos pueden estar dispersos en la memoria, no requieren un bloque contiguo.

Desventajas

Acceso secuencial: No puedes acceder directamente al elemento en la posición i (como en un array). Debes recorrer la lista desde el principio.
Mayor consumo de memoria: Cada nodo almacena punteros adicionales, lo que aumenta el uso de memoria.
Dificultad de depuración: Los punteros pueden causar errores difíciles de rastrear, como bucles infinitos o pérdidas de memoria.

Aplicaciones Comunes de las Listas Enlazadas

Las listas enlazadas no son solo un concepto teórico. Se usan en muchos sistemas reales:

Implementación de pilas y colas: Las listas enlazadas son ideales para estructuras de datos LIFO (pilas) y FIFO (colas) porque permiten inserciones y eliminaciones rápidas en los extremos.
Sistemas de archivos: Algunos sistemas operativos usan listas enlazadas para gestionar bloques de archivos fragmentados.
Navegación web: Los botones "adelante" y "atrás" en un navegador se implementan con listas doblemente enlazadas.
Reproducción de música: Las listas de reproducción (playlists) suelen ser listas circulares o doblemente enlazadas para permitir saltar a la siguiente o anterior canción.
Tablas hash: Para manejar colisiones, muchas implementaciones usan listas enlazadas en cada bucket.

¿Por Qué es Difícil Aprender Listas Enlazadas?

Muchos estudiantes encuentran confuso el concepto de punteros y la manipulación de enlaces. Es fácil perderse cuando tratas de visualizar cómo se conectan los nodos. Aquí es donde una plataforma de visualización de algoritmos se convierte en tu mejor aliada.

Plataforma de Visualización: Tu Laboratorio Interactivo

Nuestra plataforma de visualización de estructuras de datos y algoritmos está diseñada para que puedas ver exactamente qué sucede en cada operación. No más dibujos abstractos en papel. Ahora puedes ejecutar paso a paso las inserciones, eliminaciones y búsquedas en una lista enlazada, y observar cómo cambian los punteros en tiempo real.

Funcionalidades Clave de la Plataforma

Visualización en vivo: Cada nodo se muestra como un cuadro con su valor y punteros. Las flechas se actualizan instantáneamente al realizar operaciones.
Control paso a paso: Puedes avanzar y retroceder en la ejecución de un algoritmo, viendo el estado de la lista en cada momento.
Simulación de varios tipos: Practica con listas simplemente enlazadas, doblemente enlazadas y circulares.
Editor de código integrado: Escribe tu propio código en Python, Java, C++ o JavaScript y mira cómo se comporta la lista.
Ejemplos predefinidos: Carga ejercicios comunes como "invertir una lista", "detectar ciclos" o "fusionar dos listas ordenadas".
Estadísticas de rendimiento: Observa la complejidad temporal y espacial de tus operaciones.

¿Cómo Usar la Plataforma para Aprender Listas Enlazadas?

Sigue estos pasos para aprovechar al máximo la herramienta:

Selecciona "Lista Enlazada" en el menú de estructuras.
Elige el tipo: Simplemente enlazada, doblemente enlazada o circular.
Inicia con una lista vacía o carga un ejemplo predeterminado.
Usa los botones de operación: "Insertar al inicio", "Insertar al final", "Eliminar nodo", "Buscar valor".
Observa los cambios: Cada vez que realices una operación, los nodos y punteros se actualizarán gráficamente.
Activa el modo "Paso a paso": Para algoritmos más complejos, como invertir la lista, puedes ejecutar una línea de código a la vez.
Revisa el código: La plataforma te mostrará el código equivalente en el lenguaje que elijas, para que puedas relacionar la lógica con la visualización.

Beneficios de Aprender con Visualización

Estudios en ciencia cognitiva demuestran que la visualización mejora la comprensión y retención de conceptos abstractos. Al ver cómo los punteros se reasignan, internalizas el mecanismo mucho más rápido que solo leyendo texto. Además, la plataforma te permite experimentar sin miedo a equivocarte: puedes romper la lista, crear ciclos accidentales y aprender de tus errores en un entorno seguro.

Ejemplo Práctico: Inserción en una Lista Simplemente Enlazada

Supongamos que tienes una lista con los valores [3, 7, 9] y quieres insertar el valor 5 después del 7. Sin visualización, tendrías que imaginarte los punteros. Con nuestra plataforma, verás cómo:

Se crea un nuevo nodo con valor 5.
El puntero del nodo 7 (que actualmente apunta a 9) se cambia para que apunte al nuevo nodo.
El nuevo nodo apunta al nodo 9.
La lista queda [3, 7, 5, 9].

Este proceso, que parece simple, es la base de muchas operaciones avanzadas. Al verlo gráficamente, entiendes por qué la inserción es O(1) si ya tienes el nodo anterior.

Depuración de Errores Comunes con la Ayuda de la Visualización

Uno de los errores más frecuentes al programar listas enlazadas es perder la referencia a un nodo. Por ejemplo, al eliminar un nodo, si no actualizas correctamente el puntero anterior, puedes crear una "fuga de memoria" o una lista rota. La plataforma te muestra gráficamente si algún nodo queda inaccesible, ayudándote a detectar el error de inmediato.

Otro error clásico es crear un ciclo accidental (una lista circular no deseada). Con la visualización, verás aparecer una flecha que vuelve a un nodo anterior, y podrás detener la ejecución antes de que el programa entre en un bucle infinito.

Más Allá de lo Básico: Algoritmos Avanzados

Una vez que domines las operaciones básicas, la plataforma te permite explorar algoritmos más complejos:

Invertir una lista enlazada: Visualiza cómo los punteros cambian de dirección.
Detección de ciclos (Algoritmo de Floyd): Usa dos punteros (lento y rápido) y mira cómo se encuentran si hay un ciclo.
Ordenamiento de listas enlazadas: Implementa Merge Sort o Quick Sort visualmente.
Intersección de dos listas: Encuentra el nodo común.

¿Por Qué Elegir Nuestra Plataforma?

Existen muchas herramientas de visualización, pero la nuestra está diseñada específicamente para estudiantes de habla hispana. La interfaz está completamente en español, con explicaciones claras y ejemplos adaptados al contexto de aprendizaje. Además, ofrecemos:

Gratuidad: Acceso sin costo a todas las funcionalidades básicas.
Multiplataforma: Funciona en cualquier navegador moderno, sin necesidad de instalar nada.
Comunidad: Foros de discusión donde puedes compartir tus dudas y soluciones.
Actualizaciones constantes: Nuevos algoritmos y estructuras se añaden regularmente.

Conclusión: El Poder de Ver para Creer

Las listas enlazadas son una estructura de datos esencial en el mundo de la programación. Aunque al principio pueden parecer abstractas, con la ayuda de una plataforma de visualización interactiva, cualquier estudiante puede dominarlas. No se trata solo de memorizar código, sino de entender la lógica detrás de los punteros y las conexiones.

Te invitamos a explorar nuestra plataforma de visualización de algoritmos. Comienza con una lista simplemente enlazada, juega con las inserciones y eliminaciones, y gradualmente avanza a problemas más complejos. Verás cómo tu comprensión se profundiza y cómo se vuelve más fácil escribir tu propio código sin errores.

Recuerda: en el aprendizaje de estructuras de datos, la visualización no es un lujo, es una necesidad. ¡Empieza hoy y transforma tu manera de estudiar algoritmos!

Recursos Adicionales

Para complementar tu estudio, aquí tienes algunos temas relacionados que puedes explorar en nuestra plataforma:

No olvides compartir este artículo con otros estudiantes que estén luchando con las listas enlazadas. La mejor forma de aprender es enseñar, y con nuestra plataforma, todos pueden visualizar el conocimiento.

```

按位序删除结点

该函数用于按位序删除节点的功能。具体来说，当参数 i 为 1 时，删除链表的 头节点；当 i 等于链表长度时，删除链表的 尾节点。