/**
 * @file linked_list.h
 * @brief Doubly-linked list implementation.
 * @details This module provides a generic doubly-linked list data structure
 *          that can store pointers to any datatype.
 */

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

/**
 * @struct LinkedList
 * @brief A doubly-linked list container.
 * @details Maintains references to the first and last nodes in the list,
 *          as well as the current number of elements.
 */
typedef struct LinkedList LinkedList;

/**
 * @struct LinkedListNode
 * @brief A node within a doubly-linked list.
 * @details Each node contains pointers to the next and previous nodes,
 *          allowing bidirectional traversal, and a generic data pointer.
 */
typedef struct LinkedListNode LinkedListNode;

/**
 * @struct LinkedList
 * @brief A doubly-linked list container structure.
 */
struct LinkedList {
    /**
     * @brief Pointer to the first node in the list.
     * @details NULL if the list is empty.
     */
    LinkedListNode *head;

    /**
     * @brief Pointer to the last node in the list.
     * @details NULL if the list is empty.
     */
    LinkedListNode *tail;

    /**
     * @brief The number of nodes currently in the list.
     * @details Updated whenever nodes are added or removed.
     */
    int size;
};

/**
 * @struct LinkedListNode
 * @brief A single node in a doubly-linked list structure.
 */
struct LinkedListNode {
    /**
     * @brief Pointer to the next node in the list.
     * @details NULL if this is the last node.
     */
    LinkedListNode *next;

    /**
     * @brief Pointer to the previous node in the list.
     * @details NULL if this is the first node (head).
     */
    LinkedListNode *prev;

    /**
     * @brief Generic pointer to the node's data.
     * @details The caller is responsible for managing the memory
     *          pointed to by this pointer.
     */
    void *data;
};

/**
 * @brief Allocates and initializes an empty linked list.
 *
 * @return A pointer to the newly created linked list, or NULL if memory
 *         allocation fails.
 *
 * @note The caller is responsible for freeing the returned linked list
 *       using linked_list_delete().
 */
LinkedList *linked_list_new();

/**
 * @brief Deallocates the given linked list and all its nodes.
 *
 * @param ll Pointer to the linked list to delete.
 *
 * @note This function deallocates only the list structure and nodes, not
 *       the data they point to. The caller retains ownership of the data.
 */
void linked_list_delete(LinkedList *ll);

/**
 * @brief Appends an element to the end of the linked list.
 *
 * @param ll Pointer to the linked list.
 * @param elem Pointer to the element to append.
 *
 * @return A pointer to the newly created node containing the element,
 *         or NULL if memory allocation fails.
 *
 * @note The linked list does not take ownership of the element itself,
 *       only the node structure. The caller retains ownership of the
 *       data.
 */
LinkedListNode *linked_list_append(LinkedList *ll, void *elem);

/**
 * @brief Removes and returns the first element from the linked list.
 *
 * @param ll Pointer to the linked list.
 *
 * @return The data pointer of the removed first element, or NULL if empty.
 */
void *linked_list_popfront(LinkedList *ll);

/**
 * @brief Finds the linked list node containing the given element.
 *
 * @param ll Pointer to the linked list.
 * @param elem Pointer to the element to search for.
 *
 * @return A pointer to the node containing the element, or NULL if the
 *         element was not found in the list.
 */
LinkedListNode *linked_list_find(LinkedList *ll, void *elem);

/**
 * @brief Removes the given node from the linked list and deallocates it.
 *
 * @param ll Pointer to the linked list.
 * @param node Pointer to the node to remove.
 *
 * @return The data pointer stored in the removed node.
 *
 * @pre The node must belong to the linked list ll.
 *
 * @note The node structure is deallocated, but the data is not. The
 *       caller retains ownership of the returned data.
 */
void *linked_list_remove(LinkedList *ll, LinkedListNode *node);

#endif // !LINKED_LIST_H