/*
 * doubly_linked_list.h - Lista Doblemente Enlazada
 * (incluye variante Circular)
 *
 * Inspirado en "Data Structures and Algorithms Made Easy"
 * por Narasimha Karumanchi.
 *
 * Define un TAD de lista doblemente enlazada con operaciones
 * fundamentales y sus versiones recursivas para fines didácticos.
 * Incluye una sección opcional para listas doblemente enlazadas circulares.
 */

#ifndef DOUBLY_LINKED_LIST_H
#define DOUBLY_LINKED_LIST_H

#include <stdbool.h>

/* ===== ESTRUCTURA DE NODO ===== */
typedef struct _dlist_node {
  int data;
  struct _dlist_node *prev;
  struct _dlist_node *next;
} DListNode;

/* ===== CREACIÓN ===== */

/* Crea un nuevo nodo con el dato especificado */
DListNode *create_dnode(int data);

/* ===== INSERCIÓN ===== */

/* Inserta un nodo al inicio de la lista (iterativo) */
DListNode *insert_front(DListNode *head, int data);

/* Inserta un nodo al final de la lista (iterativo) */
DListNode *insert_back(DListNode *head, int data);
/* Inserta un nodo al final de la lista (recursivo) */
DListNode *insert_back_rec(DListNode *head, int data);

/* Inserta un nodo en la posición dada (0 = inicio, iterativo).
 * Retorna el nuevo head. */
DListNode *insert_at(DListNode *head, int position, int data);
/* Inserta un nodo en la posición dada (0 = inicio, recursivo).
 * Retorna el nuevo head. */
DListNode *insert_at_rec(DListNode *head, int position, int data);

/* ===== ELIMINACIÓN ===== */

/* Elimina el primer nodo con el valor dado (iterativo).
 * Retorna el nuevo head. */
DListNode *delete_value(DListNode *head, int data);
/* Elimina el primer nodo con el valor dado (recursivo).
 * Retorna el nuevo head. */
DListNode *delete_value_rec(DListNode *head, int data);

/* Elimina el nodo en la posición dada (0 = inicio, iterativo).
 * Retorna el nuevo head. */
DListNode *delete_at(DListNode *head, int position);

/* ===== BÚSQUEDA ===== */

/* Busca un valor en la lista (iterativo).
 * Retorna true si se encontró, false si no. */
bool search_dlist(DListNode *head, int data);
/* Busca un valor en la lista (recursivo).
 * Retorna true si se encontró, false si no. */
bool search_dlist_rec(DListNode *head, int data);

/* ===== TAMAÑO ===== */

/* Devuelve el número de elementos en la lista (iterativo) */
int size_dlist(DListNode *head);
/* Devuelve el número de elementos en la lista (recursivo) */
int size_dlist_rec(DListNode *head);

/* ===== DESTRUCCIÓN ===== */

/* Libera toda la memoria asociada a la lista (iterativo) */
void destroy_dlist(DListNode *head);
/* Libera toda la memoria de la lista (recursivo) */
void destroy_dlist_rec(DListNode *head);

/* ===== IMPRESIÓN ===== */

/* Imprime los elementos de la lista de inicio a fin (iterativo) */
void print_dlist_forward(DListNode *head);
/* Imprime los elementos de la lista de inicio a fin (recursivo) */
void print_dlist_forward_rec(DListNode *head);

/* Imprime los elementos de la lista de fin a inicio (iterativo) */
void print_dlist_backward(DListNode *tail);
/* Imprime los elementos de la lista de fin a inicio (recursivo) */
void print_dlist_backward_rec(DListNode *tail);

/* ===== OPERACIONES AVANZADAS ===== */

/* Invierte la lista (recursivo).
 * Retorna el nuevo head. */
DListNode *invert_dlist_rec(DListNode *head);

/* Compara dos listas nodo a nodo (recursivo).
 * Retorna true si son idénticas. */
bool compare_dlists_rec(DListNode *l1, DListNode *l2);

/* =========================================================
 *      LISTA DOBLEMENTE ENLAZADA CIRCULAR (CDLL)
 * ========================================================= */

/* Crea una lista circular con un único nodo */
DListNode *create_cdll(int data);

/* Inserta un nodo al inicio de la lista circular */
DListNode *insert_front_cdll(DListNode *head, int data);

/* Inserta un nodo al final de la lista circular */
DListNode *insert_back_cdll(DListNode *head, int data);

/* Elimina el primer nodo con el valor dado en la lista circular.
 * Retorna el nuevo head. */
DListNode *delete_value_cdll(DListNode *head, int data);

/* Busca un valor en la lista circular.
 * Retorna true si se encontró, false si no. */
bool search_cdll(DListNode *head, int data);

/* Devuelve el número de elementos en la lista circular */
int size_cdll(DListNode *head);

/* Libera toda la memoria de la lista circular */
void destroy_cdll(DListNode *head);

/* Imprime los elementos de la lista circular en orden (head → next) */
void print_cdll_forward(DListNode *head);

/* Imprime los elementos de la lista circular en orden inverso (head → prev) */
void print_cdll_backward(DListNode *head);

#endif // DOUBLY_LINKED_LIST_H