循环链表是一种数据结构，其中最后一个节点的next连接回到第一个节点，形成一个循环。此结构允许连续遍历而不会中断。
循环链表对于日程安排和音乐播放列表等任务特别有用，这允许播放完毕后回到第一首继续播放。
在这小节中，我们将介绍循环链表的基础知识、如何使用它们、它们的优点和缺点以及它们的应用。

什么是循环链表？

循环链表是一种特殊类型的链表，其中所有节点都连接起来形成一个环。
与我们前面讲到的链表不同的是，循环链表中的最后一个节点的next指向第一个节点。这意味着当遍历到尾部时可以继续向头部遍历。

循环链表是从单链表和双链表扩展出来的，因此，循环链表基本只有这两种类型。

循环单链表

在循环单链表中，每个节点只有一个指针，称为next指针。最后一个节点的next指针指向第一个节点，这样就形成了一个环。在循环单链表中，我们只能沿一个方向遍历链表。

循环单链表结构

数据结构

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct LNode {
  int data;
  struct LNode* next;
} LNode, *LinkList;
LNode* pTemp = (LNode*)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = p->next; // 将新节点的next指向p的下一个节点
p->next = pTemp; // 更新p的next指向新节点，完成插入操
// 完整代码：https://totuma.cn

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

在上面的定义中，每个节点都有data数据域和next指针域，和普通的单链表结构一模一样，唯一区别就是当我们为循环链表创建多个节点时，我们只需要将最后一个节点连接回第一个节点即可。

循环单链表的基本操作实现

创建循环单链表

插入是链表中的基本操作。和普通单链表的唯一区别是将最后一个节点的next连接到第头结点。
插入大概可以分为以下三种情况

1.在空链表中插入新结点

在空链表中插入新结点

这里使用的是带头结点的单链表来实现循环链表，所以链表空的条件是头结点的next指向头结点，即头结点自己指向自己。
在空的循环链表中插入一个节点，需要创建一个新结点，将其next指针指向头结点，以达到循环的目的。

2.在链表中部插入新结点

在链表中部插入新结点

和普通单链表操作一样，在中部插入结点并没有改变尾结点next的指向。

3.在链表尾部插入新结点

在链表尾部插入新结点

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct LNode {
  int data;
  struct LNode* next;
} LNode, *LinkList;
LNode* pTemp = (LNode*)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = p->next; // 将新节点的next指向p的下一个节点
p->next = pTemp; // 更新p的next指向新节点，完成插入操
// 完整代码：https://totuma.cn

上面三种情况，都可以统一为同一操作：
1.找到待插入位置的前驱结点，即p；
2.创建新结点pTemp；
3.使pTemp的next指向p的next；
（如果是空链表，那么p的next指向头结点本身。如果是在末尾插入，p的next同样也是指向头结点）
4.使p的next指向pTemp；

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

2.4 Explicación detallada de la lista enlazada circular simple - Tutorial de Listas Lineales Visualiza tu código con animaciones

```html

Listas Enlazadas (Linked Lists): La Guía Definitiva para Estudiantes de Estructuras de Datos

Bienvenido, futuro ingeniero de software. Hoy vamos a explorar una de las estructuras de datos más fundamentales y elegantes: la lista enlazada (linked list). Si estás aprendiendo estructuras de datos y algoritmos, este artículo es para ti. Vamos a desglosar qué son, cómo funcionan, sus ventajas, desventajas, y cómo puedes visualizarlas paso a paso usando nuestra plataforma interactiva de visualización. Prepárate para dominar este concepto de una vez por todas.

¿Qué es una Lista Enlazada? (Definición Simple)

Imagina un tren. Un tren está formado por vagones. Cada vagón está conectado al siguiente mediante un enganche. En informática, una lista enlazada es exactamente eso: una secuencia de elementos llamados nodos. Cada nodo contiene dos cosas: el dato que queremos guardar (un número, un texto, etc.) y un puntero (o enlace) que apunta al siguiente nodo de la secuencia. A diferencia de un array (arreglo), los nodos no están uno al lado del otro en la memoria; pueden estar dispersos, pero los punteros los mantienen unidos en orden.

¿Por qué son importantes las Listas Enlazadas?

Las listas enlazadas son la base de muchas otras estructuras como pilas, colas y grafos. Entenderlas bien te dará una ventaja enorme. Su principal superpoder es la capacidad de insertar y eliminar elementos en cualquier posición sin tener que mover todos los demás elementos, algo que en un array es muy costoso. Sin embargo, tienen una debilidad: no puedes acceder directamente al elemento número 5; tienes que recorrer la lista desde el principio (acceso secuencial).

Componentes Clave de una Lista Enlazada Simple

Vamos a ver las piezas de este rompecabezas:

Nodo (Node): La unidad básica. En código, normalmente se representa como una clase o estructura con dos campos: data (el valor) y next (el puntero al siguiente nodo).

Cabeza (Head): Es el primer nodo de la lista. Si perdemos la cabeza, perdemos toda la lista. Es nuestra puerta de entrada.

Cola (Tail): El último nodo. Su puntero next apunta a null (nulo), indicando que no hay más nodos.

Puntero next: Es el "enganche" que conecta un vagón con el siguiente. Sin él, la lista se rompe.

Tipos de Listas Enlazadas (No todas son iguales)

Existen varias variantes. Aquí las más comunes que verás en tus cursos:

1. Lista Enlazada Simple (Singly Linked List)

Cada nodo solo apunta al siguiente. Solo puedes recorrerla hacia adelante. Es la más básica y eficiente en memoria.

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. Es más flexible, pero consume más memoria (por el puntero extra).

3. Lista Circular (Circular Linked List)

El último nodo apunta de nuevo al primero, formando un círculo. Puede ser simple o doble. Útil para aplicaciones donde necesitas ciclar continuamente, como en juegos de turnos.

Operaciones Principales (Algoritmos Esenciales)

Aquí están las operaciones que todo estudiante debe conocer. Te explicamos cómo funcionan y su complejidad.

Inserción al Inicio (Insert at Head)

Crear un nuevo nodo, hacer que su puntero next apunte a la cabeza actual, y luego actualizar la cabeza para que sea el nuevo nodo. Es una operación O(1) (tiempo constante).

Inserción al Final (Insert at Tail)

Si tienes un puntero a la cola, también es O(1). Si no, tienes que recorrer toda la lista hasta el final (O(n)) y luego enlazar el nuevo nodo.

Inserción en una Posición Específica

Necesitas recorrer la lista hasta la posición anterior a donde quieres insertar (O(n)). Luego ajustas los punteros.

Eliminación de un Nodo

Similar a la inserción. Debes encontrar el nodo anterior al que quieres eliminar y hacer que su puntero next salte por encima del nodo eliminado. Es O(n) en el peor caso.

Búsqueda de un Elemento

Recorres la lista desde la cabeza comparando cada nodo. Si lo encuentras, devuelves el nodo o su posición. Es O(n).

Ventajas y Desventajas (Cuándo usarlas)

Como toda herramienta, las listas enlazadas tienen su lugar. Aquí te damos un resumen claro:

Ventajas:

Inserción y eliminación eficientes en cualquier posición (si ya tienes la referencia al nodo).
Tamaño dinámico: no necesitas definir un tamaño fijo como en los arrays.
No hay desperdicio de memoria por espacios no utilizados (a diferencia de los arrays dinámicos que a veces se redimensionan).

Desventajas:

Acceso secuencial: no puedes acceder al elemento i-ésimo directamente. Tienes que recorrer desde el inicio.
Consumen más memoria por nodo debido al puntero(s).
La manipulación de punteros puede ser propensa a errores (como perder la lista si no tienes cuidado).

Aplicaciones Reales de las Listas Enlazadas

No son solo teoría. Las listas enlazadas se usan en:

1. Navegadores web: El botón de "atrás" y "adelante" se implementa con una lista doblemente enlazada de las páginas visitadas.

2. Sistemas de archivos: Algunos sistemas operativos usan listas enlazadas para gestionar los bloques de un archivo.

3. Música en streaming: Las listas de reproducción (playlists) son listas enlazadas. Puedes saltar a la siguiente canción o volver a la anterior fácilmente.

4. Memoria dinámica: Los administradores de memoria del sistema operativo a menudo usan listas enlazadas para llevar un registro de los bloques de memoria libres.

Visualización: La Clave para Entender (y cómo nuestra plataforma te ayuda)

Si solo lees teoría, es fácil confundirse. Por eso, en nuestra plataforma de visualización de estructuras de datos, hemos creado un entorno interactivo donde puedes ver cada operación en acción. No es magia, es código visualizado.

¿Qué ofrece nuestra plataforma?

Simulación paso a paso: Puedes ejecutar algoritmos como "insertar al inicio" o "eliminar el último nodo" y ver cómo los punteros cambian en tiempo real. Cada nodo se muestra como un cuadro con dos compartimentos: uno para el dato y otro para la flecha (puntero).

Control de velocidad: ¿Demasiado rápido? Puedes ralentizar la animación para analizar cada movimiento. ¿Aburrido? Acelera el proceso.

Editor de código integrado: Escribe tu propio código (en Python, Java, C++ o JavaScript) y la plataforma lo ejecutará visualmente. Verás cómo tu código manipula la memoria.

Pruebas de estrés: Crea listas de 1000 nodos y observa cómo se comportan las operaciones. Esto te dará una intuición real de la complejidad algorítmica.

Modo oscuro y claro: Para que estudiar sea más cómodo.

¿Cmo usar la plataforma para aprender listas enlazadas?

Es muy sencillo:

Paso 1: Ve a la sección "Listas Enlazadas" en el menú principal.

Paso 2: Elige el tipo de lista: simple, doble o circular.

Paso 3: Usa los botones "Insertar", "Eliminar", "Buscar" o escribe tu propio algoritmo en el panel de código.

Paso 4: Observa cómo los nodos se crean, enlazan o eliminan en el lienzo interactivo. Presta atención a los punteros que cambian de color.

Paso 5: Revisa el panel de "Estado de la memoria" para ver la dirección de cada nodo (simulada) y entender cómo se almacenan.

Ejemplo Visual: Insertando un nodo al inicio

Imagina que tienes una lista con tres números: 10 → 20 → 30. Quieres insertar el 5 al inicio. En la plataforma, verás:

1. Aparece un nuevo nodo (5) flotando.

2. Una flecha punteada muestra que el puntero next del nuevo nodo se dirige al nodo que actualmente es la cabeza (10).

3. La cabeza (Head) se mueve visualmente para apuntar al nuevo nodo (5).

4. La lista ahora es: 5 → 10 → 20 → 30.

Este tipo de retroalimentación visual hace que el concepto de "reconexión de punteros" sea imposible de olvidar.

Errores Comunes al Aprender Listas Enlazadas (y cómo evitarlos)

Hemos visto a miles de estudiantes cometer estos errores. Te los contamos para que no caigas en ellos:

Error 1: Perder la cabeza (Head). Si sobrescribes el puntero head sin guardar la referencia, pierdes toda la lista. Siempre usa una variable temporal.

Error 2: Olvidar actualizar el puntero del nodo anterior al eliminar. Si solo eliminas el nodo sin reconectar, la lista se rompe.

Error 3: Confundir el orden de las operaciones. Al insertar, primero enlaza el nuevo nodo al siguiente, y luego actualiza el puntero del nodo anterior. Si haces lo contrario, pierdes el resto de la lista.

En nuestra plataforma, puedes provocar estos errores a propósito en un entorno seguro (modo "sandbox") y ver exactamente qué sale mal.

Complejidad Algorítmica (Big O) Resumida

Para tu examen o entrevista técnica, memoriza esto:

Acceso (por índice): O(n) - tienes que recorrer.

Búsqueda (por valor): O(n) - en el peor caso, recorres toda la lista.

Inserción al inicio: O(1) - solo ajustas la cabeza.

Inserción al final (con cola): O(1) - si tienes puntero a la cola.

Inserción al final (sin cola): O(n) - tienes que recorrer.

Eliminación (con referencia al nodo anterior): O(1) - solo ajustas punteros.

Eliminación (sin referencia): O(n) - necesitas buscar el nodo anterior.

Listas Enlazadas vs Arrays: La Batalla Épica

Esta es una pregunta clásica en entrevistas. Aquí te damos la comparación definitiva:

Arrays: Acceso aleatorio O(1), inserción/eliminación O(n) por desplazamiento, tamaño fijo (o redimensionamiento costoso).

Listas Enlazadas: Acceso secuencial O(n), inserción/eliminación O(1) si tienes la posición, tamaño dinámico sin redimensionamiento.

¿Cuándo usar cada uno? Usa arrays cuando necesites acceso rápido por índice y sepas el tamaño de antemano. Usa listas enlazadas cuando necesites hacer muchas inserciones/eliminaciones en posiciones arbitrarias.

Preguntas Frecuentes (FAQ) de Estudiantes

P: ¿Qué pasa si el puntero next apunta a null?

R: Significa que es el último nodo de la lista. Es la condición de parada al recorrer.

P: ¿Puedo tener una lista enlazada vacía?

R: Sí. La cabeza (head) apunta a null. Es una lista sin nodos.

P: ¿Las listas enlazadas se usan en lenguajes modernos como Python?

R: Python no tiene una lista enlazada nativa, pero puedes implementarla fácilmente con clases. Las listas de Python son arrays dinámicos, no listas enlazadas.

P: ¿Qué es más difícil, lista simple o doble?

R: La doble tiene más punteros que manejar, pero facilita algunas operaciones como recorrer hacia atrás. Con la práctica, ambas se vuelven naturales.

Conclusión: Domina las Listas Enlazadas con Visualización

Las listas enlazadas son un pilar de la informática. No las aprendas solo de memoria; entiéndelas visualmente. Nuestra plataforma de visualización está diseñada para que puedas experimentar, equivocarte y aprender en un entorno interactivo. Te invitamos a crear tu primera lista enlazada ahora mismo. Verás que cuando los punteros cobran vida, todo tiene sentido.

Recuerda: la práctica constante y la visualización son las mejores herramientas para un estudiante de algoritmos. ¡Empieza hoy y conviértete en un experto en estructuras de datos!

Recursos Adicionales dentro de la Plataforma

Además de listas enlazadas, ofrecemos visualizaciones para:

Pilas (Stacks) y Colas (Queues)
Árboles Binarios y AVL
Grafos y algoritmos de búsqueda (BFS, DFS)
Algoritmos de ordenamiento (QuickSort, MergeSort)
Tablas Hash

Todos con el mismo enfoque interactivo. No solo leas, ¡visualiza!

Palabras clave relacionadas: lista enlazada, linked list, estructura de datos, algoritmo, visualización de algoritmos, aprender programación, nodo, puntero, cabeza, cola, inserción, eliminación, complejidad O(n), O(1), entrevistas técnicas, ciencias de la computación.

```

为什么要使用头插法创建，而不是尾插法创建？
如果我们要在链表末尾进行插入，那么需要先遍历整个链表找到尾结点，或者使用一个变量记录尾结点的。
而且每次都需要改变尾结点的next指向头结点，以达到循环。
而我们使用头插法，无论链表是否为空，代码都是统一不变，不需要做其他判断。

按位序删除结点

删除操作和普通单链表相同。主要区别在于我们需要确保删除后链表保持循环。

要从循环链表中删除特定的结点，首先需要检查删除的位序是否满足条件。
找到待删除结点的前驱结点即p结点
找到前驱结点p后，使用q记录为待删除结点
修改前驱结点p的next指向待删除结点q的next，即跳过q结点并将其删除

仅有一个结点时，循环指向头结点

删除尾部结点，更新链表循环

删除中间结点

💡 提示
对于带头结点的链表，上面三种情况都可以统一为同一种操作代码

按位序删除结点 | 可视化完整可视化