En una entrevista en TED 2016 (2:10 pm), Linus Torvalds habla sobre un buen estilo de codificación. Como ejemplo, ofrece dos opciones para eliminar elementos de listas vinculadas individualmente (ver más abajo). La primera opción tiene un caso especial, mientras que la otra no. Linus prefiere lo último.

Su comentario:

[...] No hay necesidad de pensar por qué no hay una declaración if aquí. Es importante ver el problema desde una perspectiva diferente y reescribirlo para que el caso especial desaparezca y se convierta en un caso normal, y ese es un buen código . - L. Torvalds

Linus muestra un pseudocódigo de estilo C bastante simple como ejemplo. Pero no proporciona una explicación conceptual. Por lo tanto, no está claro de inmediato cómo funciona un puntero indirecto.

Echemos un vistazo más de cerca a esta solución y sus ventajas. Como beneficio adicional, no solo se muestra la eliminación, sino también la inserción de un elemento mediante direccionamiento indirecto.

El código

La estructura de datos básica para una lista de números enteros enlazados individualmente se muestra en la Fig. 1.

Fig. 1. Una lista de números enteros enlazados individualmente Los

números son valores enteros seleccionados aleatoriamente y las flechas corresponden a punteros: head

este es un puntero de tipo IntListItem*

, todos los bloques son instancias de una estructura IntListItem

, cada uno con su propia variable ( next

en el código) del tipo IntListItem*

, que apunta al siguiente elemento.

Implementación de la estructura de datos en C:

struct IntListItem {
    int value;
    struct IntListItem* next;
};
typedef struct IntListItem IntListItem;

struct IntList {
    IntListItem* head;
};
typedef struct IntList IntList;

También la API (mínima):

/* The textbook version */
void remove_cs101(IntList* l, IntListItem* target);
/* A more elegant solution */
void remove_elegant(IntList* l, IntListItem* target);

Ahora veamos las implementaciones remove_cs101()

y remove_elegant()

. El código de los ejemplos no contradice el pseudocódigo del ejemplo de Linus, pero se compila y se ejecuta.

Versión básica

Figura: 2. Modelo conceptual de la estructura de datos de la lista en el algoritmo básico

void remove_cs101(IntList *l, IntListItem *target)
{
    IntListItem *cur = l->head, *prev = NULL;
    while (cur != target) {
        prev = cur;
        cur = cur->next;
    }
    if (prev) {
        prev->next = cur->next;
    } else {
        l->head = cur->next;
    }
}

En el enfoque estándar, hay dos punteros de recorrido cur

y prev

, que marcan la posición de recorrido actual y anterior en la lista, respectivamente. cur

comienza al principio de la lista head

y avanza hasta que se encuentra el objetivo. A su vez, prev

comienza con NULL

y posteriormente se actualiza al valor anterior cur

cada vez que avanza. Cuando se encuentra el objetivo, el algoritmo comprueba si no es prev

cero. Si es así, cur

apunta al primer elemento de la lista, en cuyo caso eliminar significa mover el encabezado de la lista hacia adelante.

Una solución más elegante

La versión más elegante tiene menos código y no requiere una rama separada para eliminar el primer elemento de la lista.

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) != target) {
        p = &(*p)->next;
    }
    *p = target->next;
}

El código usa un puntero indirecto p

que contiene la dirección del puntero al elemento de la lista, comenzando en la dirección head

. En cada iteración, este puntero se expande para incluir la dirección del puntero al siguiente elemento de la lista, es decir, la dirección del elemento next

en el actual IntListItem

. Cuando el puntero al elemento de la lista (*p)

es igual target

, salimos del ciclo de búsqueda y eliminamos el elemento de la lista.

¿Cómo funciona?

Un puntero indirecto tiene p

dos ventajas conceptuales:

Le permite interpretar una lista enlazada de tal manera que el puntero se head

convierta en una parte integral de la estructura de datos. Esto elimina la necesidad de un estuche especial para quitar el primer artículo.
También le permite evaluar el estado del bucle while

sin tener que soltar el puntero que apunta target

. Esto le permite cambiar el puntero ay target

arreglárselas con un solo iterador, a diferencia de prev

y cur

.

Echemos un vistazo a cada elemento por turno.

Integración de puntero de cabeza

El modelo estándar interpreta una lista vinculada como una secuencia de instancias IntListItem

. El inicio de la secuencia se puede obtener mediante un puntero head

. Esto conduce al modelo conceptual que se muestra en la Fig. 2. El puntero se head

trata simplemente como un identificador para acceder al principio de la lista. prev

y cur

son punteros de tipo IntListItem*

y siempre apuntan a o NULL

.

La implementación elegante utiliza un esquema de direccionamiento indirecto, que brinda una vista diferente de la estructura de datos:

Fig. 3. Modelo conceptual de la estructura de datos de la lista en una solución más elegante

Aquí se p

representa el tipoIntListItem**

y contiene la dirección del puntero al elemento de la lista actual. Cuando el puntero avanza, su dirección cambia al siguiente elemento.

En código, se ve así p = &(*p)->next

:

(*p)

: elimina la referencia de la dirección del puntero al elemento de la lista actual.
->next

: elimine la referencia de este puntero nuevamente y seleccione el campo con la dirección del siguiente elemento.
&

: tome la dirección de este campo (es decir, obtenga un puntero).

Esto corresponde a la interpretación de una estructura de datos, donde una lista es una secuencia de punteros a elementos IntListItem

(Figura 3).

Toque final

Una ventaja adicional de esta interpretación particular es que permite editar el puntero next

para el predecesor del elemento actual durante todo el recorrido .

Si p

contiene la dirección de un puntero a un elemento de la lista, la comparación en el ciclo de búsqueda se convierte en:

while ((*p) != target) {
    ...
}

El ciclo de búsqueda terminará si (*p)

es igual target

, y tan pronto como esto suceda, aún podemos cambiar (*p)

, ya que mantenemos su dirección p

. Por lo tanto, aunque el bucle se repita hasta el final, se almacena un descriptor (dirección de campo next

o puntero head

) que se puede utilizar para cambiar directamente el puntero a un elemento.

Es por eso que podemos cambiar la entrada al puntero del elemento para que apunte a una ubicación diferente, utilizando *p = target->next

, y por lo tanto, no necesitamos omitir punteros prev

y cur

eliminar el elemento.

Nueva aplicación

Resulta que la misma idea se puede aplicar a una implementación extremadamente lacónica de otra función más en listas enlazadas: insert_before()

es decir, insertar este elemento antes que otro.

Inserción antes del elemento existente

Primero, agreguemos la siguiente declaración a list.h

:

void insert_before(IntList *l, IntListItem *before, IntListItem *item);

La función llevará un puntero a la lista l, un puntero antes de un elemento en esta lista y un puntero a un nuevo elemento de la lista que la función insertará antes.

Refactorización rápida

Antes de continuar, hagamos del ciclo de búsqueda una función separada:

static inline IntListItem **find_indirect(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) && (*p) != target) {
        p = &(*p)->next;
    }
    return p;
}

y usarlo en remove_elegant()

:

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = find_indirect(l, target);
    *p = target->next;
}

Implementación de Insert_before ()

Usarlo find_indirect()

es fácil de implementar insert_before()

:

void insert_before(IntList *l, IntListItem *before, IntListItem *item)
{
    IntListItem **p = find_indirect(l, before);
    *p = item;
    item->next = before;
}

Particularmente agradable es la semántica sólida para casos extremos: si before

apunta al encabezado de la lista, se insertará un nuevo elemento al principio, si before

es nulo o inválido (es decir, no existe en l

), se agregará un nuevo elemento al final.

Conclusión

El requisito previo para una solución más elegante para eliminar elementos es un cambio simple: un puntero indirecto IntListItem**

para iterar sobre punteros para listar elementos. Todo lo demás sigue de ahí: no hay necesidad de casos especiales o sucursales. Un iterador es suficiente para encontrar y eliminar el elemento de destino. Y resulta que el mismo enfoque proporciona una solución elegante para la inserción en general y la inserción frente a un elemento existente en particular.

Entonces, volviendo al comentario inicial de Linus, ¿es esto un indicador de buen gusto? Difícil de decir. Pero es evidente que existe una solución creativa y muy elegante para un problema conocido.

Listas enlazadas, trucos de puntero y buen gusto