Tema 3 - Listas

El TAD Lista, especificación informal, implementación y descripción gráfica. Operaciones explicadas de forma gráfica e implementadas. Otros tipos de TAD como Lista Ordenada y Multilistas también explicados.

TAD Lista

Nota

Esto es una especificación informal del TAD

Una lista es por definición un conjunto de cero o más elementos.

Los elementos están ordenados de forma lineal, no por su contenido, sino simplemente por la posición que ocupan relativos unos a otros.

---
title: TAD Lista enlazada simple
---
flowchart LR
    subgraph NODO1[NODO 1]
        CONTENIDO1[INFORMACIÓN]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NODO 2]
        CONTENIDO2[INFORMACIÓN]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 3]
        CONTENIDO3[INFORMACIÓN]
        SIGUIENTE3[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO2
    SIGUIENTE2 --> NODO3
    SIGUIENTE3 --> NULL

Por lo tanto, la lista está formada por nodos idénticos. Cada nodo está formado por dos elementos, la información del propio nodo y un puntero que apunta al siguiente. Además, el inicio de la lista está delimitado por un puntero Lista, y finaliza con el último nodo que apunta a NULL.

Operaciones

Siguiendo los pasos para la especificación de un TAD, definimos las operaciones del mismo clasificándolas en: constructoras, generadoras, modificadoras, observadoras y destructoras.

Nota

Para más información: Especificación de un TAD

Generadoras

• Objetivo: Crear una lista vacía y la inicializa

  Salida: Una lista vacía

  Poscondición: La lista sin datos

flowchart LR
    LISTA --> NULL

Mostrar implementación

createEmptyList.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

void createEmptyList(tList *lista) {
    lista->indice = LNULL;
}

Objetivo: Si la posición es nula, añade un elemento al final de la lista. En caso contrario, el elemento quedará insertado justo antes del que actualmente ocupa la posición indicada.

Entrada:

• Item: Contenido del elemento a insertar
• Position: Posición de referencia para la inserción
• List: Lista donde vamos a insertar

Salida: List: Lista con el elemento Item insertado y verdadero si se ha podido insertar, falso en caso contrario

Precondición: Position es una posición válida de la lista o es una posición nula

Postcondición: Las posiciones de los elementos de la lista posteriores a la del elemento insertado pueden haber variado

flowchart LR
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[INFORMACIÓN]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO3[NODO 2]
        CONTENIDO3[INFORMACIÓN]
        SIGUIENTE3[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO3
    SIGUIENTE3 --> NULL

flowchart LR
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[INFORMACIÓN]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NUEVO NODO]
        CONTENIDO2[INFORMACIÓN]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 2]
        CONTENIDO3[INFORMACIÓN]
        SIGUIENTE3[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 -.-> NODO2
    SIGUIENTE2 -.-> NODO3
    SIGUIENTE3 --> NULL

Mostrar implementación

insertItem.c

// SPDX-FileCopyrightText: 2023 Fernando Álvarez
//
// SPDX-License-Identifier: GPL-3.0-only

bool insertItem(tItemL item, tPosL pos, tList *lista) {

    tPosL posAux;
    if (!createNode(&posAux)) {

        return false;

    } else {

        posAux->data = item;
        posAux->next = LNULL; //por si acaso
    }
    if (isEmptyList(*lista)) {

        *lista = posAux;
    } else if (pos == LNULL) {

        last(*lista)->next = posAux;

    } else if (pos == *lista) {

        posAux->next = pos;
        *lista = posAux;

    } else {

        posAux->next = pos->next;
        pos->next = posAux;
        posAux->data = pos->data;
        pos->data = item;
    }
    return true;
}

Modificadores

Objetivo: Copia una lista en otra

Entrada: List_1: Lista que vamos a copiar

Salida: List_2: Copia de la lista original y verdadero si se ha podido copiar, falso en caso contrario

Precondición: La lista origen está inicializada

flowchart LR
    LISTA1[LISTA 1] --> NODO1 --> NODO2 --> NULL
    LISTA2[LISTA 2]

flowchart LR
    LISTA1[LISTA 1] --> NODO1[NODO 1] --> NODO2[NODO 2] --> NULL
    LISTA2[LISTA 2] --> NODO21[NUEVO NODO]
    LISTA2 -. X .-> NODO1[NODO 1]

flowchart LR
    LISTA1[LISTA 1] --> NODO1[NODO 1] --> NODO2[NODO 2] --> NULL
    LISTA2[LISTA 2] --> NODO21[NODO 1]
    NODO1 == copiar ==> NODO21[NODO 1]

flowchart LR
    LISTA1[LISTA 1] --> NODO1[NODO 1] --> NODO2[NODO 2] --> NULL
    LISTA2[LISTA 2] --> NODO21[NODO 1] --> NODO22[NUEVO NODO]
    NODO2 == copiar ==> NODO22[NUEVO NODO]

flowchart LR
    LISTA1[LISTA 1] --> NODO1[NODO 1] --> NODO2[NODO 2] --> NULL
    LISTA2[LISTA 2] --> NODO21[NODO 1] --> NODO22[NODO 2] --> NULL

Mostrar implementación

copyList.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

bool copyList(tlist listaDest, tList *listaOrig) {
    tPosl p, q, r;
    bool ret = true;

    createEmptyList(listaOrig);
    if (!isEmptyList(listaDest)) {
        p = listaDest;
        while ((p != LNULL) && createNode(&r)) {
            r->data = p->data;
            r->next = LNULL;
            if (p == listaDest) {
                *listaOrig = r;
                q = r;
            } else {
                q->next = r;
                q = r;
            }
            p = p->next;
        }
        if (p != LNULL) {
            deleteList(listaOrig);
            ret = false;
        }
    }
    return ret;
}

Objetivo: Modifica el contenido de un elemento de la lista

Entrada:

• Item: Nuevo contenido a asignar al elemento en Position
• Position: Posición del elemento que queremos modificar
• List: Lista a modificar

Salida: List: Lista con el contenido del elemento modificado

Precondición: Position es una posición válida de la lista

flowchart LR
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[INFORMACIÓN]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NODO A MODIFICAR]
        CONTENIDO2[INFORMACIÓN ANTIGUA]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 2]
        CONTENIDO3[INFORMACIÓN]
        SIGUIENTE3[SIGUIENTE]
    end
    subgraph MOD[_]
        INFO[NUEVA INFORMACIÓN]
        POS[POSICIÓN A MODIFICAR]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO2
    SIGUIENTE2 --> NODO3
    SIGUIENTE3 --> NULL
    INFO -.-> CONTENIDO3
    POS --> NODO3

Mostrar implementación

updateItem.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

void updateItem(tItem item, tPosL pos, tList *lista) {
    pos->data = item;
}

Destructoras

Objetivo: Elimina de la lista un elemento con cierta posición

Entrada:

Position: Posición del elemento a eliminar

List: Lista a modificar

Salida: List: Lista sin el elemento correspondiente a Position

Precondición: Position es una posición válida de la lista

Postcondición: Las posiciones de los elementos de la lista posteriores a la de la posición eliminada pueden haber variado

flowchart TB
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[INFORMACIÓN]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NODO A ELIMINAR]
        CONTENIDO2[INFORMACIÓN]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 2]
        CONTENIDO3[INFORMACIÓN]
        SIGUIENTE3[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 -.-> NODO2
    SIGUIENTE1 --> NODO3
    SIGUIENTE2 -.-> NODO3
    SIGUIENTE3 --> NULL

flowchart TB
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[INFORMACIÓN]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO3[NODO 2]
        CONTENIDO3[INFORMACIÓN]
        SIGUIENTE3[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO3
    SIGUIENTE3 --> NULL

Mostrar implementación

deleteAtPosition.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

void deleteAtPosition(tPosL pos, tList *lista) {
    tPosl posAux;

    if (pos == *lista)
        *lista = (*lista)->next;
    else {
        for (posAux = *lista; posAux->next != pos; posAux = posAux->next);
        posAux->next = pos->next;
    }

    free(pos);
}

Objetivo: Elimina todos los elementos de la lista

Entrada: List: Lista a borrar

Salida: Lista vacía

flowchart TB
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[INFORMACIÓN]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NODO 2]
        CONTENIDO2[INFORMACIÓN]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 3]
        CONTENIDO3[INFORMACIÓN]
        SIGUIENTE3[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO2
    SIGUIENTE2 --> NODO3
    SIGUIENTE3 -.-> NULL
    DELETE["FREE ()"] ==> NODO3

flowchart TB
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[INFORMACIÓN]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NODO 2]
        CONTENIDO2[INFORMACIÓN]
        SIGUIENTE2[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO2
    SIGUIENTE2 -.-> NODO3[ANTIGUA DIRECCIÓN DE NODO 3]
    NULL
    DELETE["FREE ()"] ==> NODO2

flowchart TB
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[INFORMACIÓN]
        SIGUIENTE1[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 -.-> NODO2[ANTIGUA DIRECCIÓN DE NODO 2]
    NULL
    DELETE["FREE ()"] ==> NODO1

flowchart LR
    LISTA --> NULL

Mostrar implementación

deleteList.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

void deleteList(tList *lista) {
    tPosL posAux;
    while (*lista != LNULL) {
        while (posAux->next != NULL)
            posAux = posAux->next;
        free(posAux);
    }
}

Observadoras

Objetivo: Busca el primer elemento con cierto contenido en la lista

Entrada:

• Item: Contenido del elemento buscado
• List: Lista donde realizar la búsqueda Salida: Position: Posición del elemento encontrado o nulo si no se encuentra

flowchart TB
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[USUARIO 1]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NODO 2]
        CONTENIDO2[USUARIO 2]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 3]
        CONTENIDO3[USUARIO 3]
        SIGUIENTE3[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO2
    SIGUIENTE2 --> NODO3
    SIGUIENTE3 --> NULL
    FIND["¿ERES EL USUARIO3?"] -- NO --> NODO1

flowchart TB
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[USUARIO 1]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NODO 2]
        CONTENIDO2[USUARIO 2]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 3]
        CONTENIDO3[USUARIO 3]
        SIGUIENTE3[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO2
    SIGUIENTE2 --> NODO3
    SIGUIENTE3 --> NULL
    FIND["¿ERES EL USUARIO3?"] -- NO --> NODO2

flowchart TB
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[USUARIO 1]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NODO 2]
        CONTENIDO2[USUARIO 2]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 3]
        CONTENIDO3[USUARIO 3]
        SIGUIENTE3[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO2
    SIGUIENTE2 --> NODO3
    SIGUIENTE3 --> NULL
    FIND["¿ERES EL USUARIO3?"] -- SI --> NODO3

Mostrar implementación

findItem.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

tPosL findItem(tItem item, tList lista) {
    tPosL posAux;
    for (posAux = lista; (posAux != LNULL) && (posAux->data != item); posAux = posAux->next);
    return posAux;
}

Objetivo: Determina si la lista está vacía

Entrada: List: Lista a comprobar

Salida: Verdadero si la lista está vacía, falso en caso contrario

Mostrar implementación

isEmptyList.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

bool isEmptyList(tLIst lista) {
    return lista == LNULL;
}

Objetivo: Recupera el contenido de un elemento de la lista

Entrada: Position: Posición del elemento buscado

List: Lista donde realizar la búsqueda

Salida: Item: Contenido del elemento que está en Position

Precondición: Position es una posición válida en la lista

Mostrar implementación

getItem.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

tItem getItem(tPosL pos, tList lista) {
    return pos->data;
}

Objetivo: Devuelve la posición del primer elemento de la lista

Entrada: List: Lista a manipular

Salida: Position: Posición del primer elemento

Precondición: La lista no está vacía

Mostrar implementación

first.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

tPosL first(tList lista) {
    return lista;
}

Objetivo: Devuelve la posición del último elemento de la lista

Entrada: List: Lista a manipular

Salida: Position: Posición del último elemento

Precondición: La lista no está vacía

Mostrar implementación

last.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

tPosL last(tList lista) {
    tPosL posAux;
    for (posAux = lista; posAux->next != LNULL; posAux->next);
    return posAux;
}

Objetivo: Devuelve la posición del elemento anterior al actual

Entrada: Position: Posición del elemento actual

List: Lista a manipular

Salida: Posición del elemento anterior o nulo si es el primero

Precondición: Position es una posición válida de la lista

Mostrar implementación

previous.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

tPosL previous(tPosL pos, tList L) {
    tPosL posAux;
    for (posAux = L; posAux->next != pos; posAux = posAux->next);
    return posAux;
}

Objetivo: Devuelve la posición del elemento siguiente al actual

Entrada:

• Position: Posición del elemento actual
• List: Lista a manipular

Salida: Position: Posición del elemento siguiente o nulo si es el último

Precondición: Position es una posición válida de la lista

Mostrar implementación

next.c

// SPDX-FileCopyrightText: 2024 Eliana Reigada
//
// SPDX-License-Identifier: GPL-3.0-only

tPosL next(tPosL pos, tList lista) {
    return pos->next;
}

TAD Lista ordenada

Nota

Esto es una especificación informal del TAD

Los elementos están ordenados de forma lineal por su contenido.

En caso de ordenación alfabética:

---
title: TAD Lista ordenada enlazada simple
---
flowchart LR
    subgraph NODO1[NODO 1]
        CONTENIDO1[AAAA]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NODO 2]
        CONTENIDO2[BBBB]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 3]
        CONTENIDO3[CCCC]
        SIGUIENTE3[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO2
    SIGUIENTE2 --> NODO3
    SIGUIENTE3 --> NULL

Operación a cambiar

Las operaciones del TAD lista ordenada es idéntico al TAD anterior, la única a modificar es la operación de inserción:

Objetivo: Inserta un elemento en la lista según el criterio de ordenación sobre el campo Item

Entrada:

• Item: Contenido del elemento a insertar
• List: Lista donde vamos a insertar

Salida: List: Lista con el elemento Item insertado en la posición correspondiente según su contenido y verdadero si se ha podido insertar, falso en caso contrario

Precondición: La lista está inicializada

Postcondición: Las posiciones de los elementos de la lista posteriores a la del elemento insertado pueden haber variado

flowchart TB
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[AAA]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NUEVO 2]
        CONTENIDO2[BBB]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 3]
        CONTENIDO3[DDD]
        SIGUIENTE3[SIGUIENTE]
    end
    subgraph NODO4[NUEVO NODO]
        CONTENIDO4[CCC]
        SIGUIENTE4[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO2
    SIGUIENTE2 --> NODO3
    SIGUIENTE3 --> NULL

flowchart TB
    LISTA
    subgraph NODO1[NODO 1]
        CONTENIDO1[AAA]
        SIGUIENTE1[SIGUIENTE]
    end
    subgraph NODO2[NUEVO 2]
        CONTENIDO2[BBB]
        SIGUIENTE2[SIGUIENTE]
    end
    subgraph NODO3[NODO 3]
        CONTENIDO3[DDD]
        SIGUIENTE3[SIGUIENTE]
    end
    subgraph NODO4[NUEVO NODO]
        CONTENIDO4[CCC]
        SIGUIENTE4[SIGUIENTE]
    end
    LISTA --> NODO1
    SIGUIENTE1 --> NODO2
    SIGUIENTE2 -.-> NODO4
    SIGUIENTE4 -.-> NODO3
    SIGUIENTE3 --> NULL

Mostrar implementación

insertItem_Ordenada.c

// SPDX-FileCopyrightText: 2023 Fernando Álvarez
//
// SPDX-License-Identifier: GPL-3.0-only

bool insertItem(tItemL item, tList *lista) {

    tPosL q,p;
    if (!createNode(&q)) {

        return false;

    } else {

        q->data = item;
        q->next = LNULL; //por si acaso
    }
    if (isEmptyList(*lista)) {

        *lista = q;
    }
    else if(item < (*lista)->data){

        q->next = *lista;
        *lista = q;

    }
    else{

        p = findPosition(*lista,item);
        q->next = p->next;
        p->next = q;


    }
    return true;
}

Nota

Al ser una lista ordenada, puede aprovecharse para volver más eficiente el algoritmo de búsqueda de findItem(Item,List).

Comparación entre TADs

	Estática	Simple Enlace	Doble Enlace
Necesidad de memoria	Mucha	Menos en promedio	Menos en promedio (+ que simple enlace)
Memoria contigua	✅	❌	❌
Acceso directo	✅	❌	❌
Ampliable	❌	✅	✅
Operaciones más costosas	insertItem, deleteAtPosition (excepto al final)	insertItem (final), deleteAtPosition (final), previous, last, deleteList, copyList	insertItem (final), last, deleteList, copyList
Seguridad	⚔️😡🛡️	😴🛡️	😴🛡️

Archivo de Cabecera TAD

#include <stdbool.h>

#define LNULL ...; //Constante que representa posiciones nulas

// Se define en funcion del problema
typedef ... tItemL;
typedef ... tPosL;
typedef ... tList;

// Generadoras
void createEmptyList(tList* L);
bool insertItem(tItemL d, tPosL p, tList* L);

// Modificadoras
bool copyList(tList L, tList* M);
void updateItem(tItemL d , tPosL p, tList* L);

// Destructoras
void deleteAtPosition(tPosL p, tList* L);
void deleteList(tList* L);

// Observadoras
tPosL findItem(tItemL d, tList L);
bool isEmptyList(tList L);
tItemL getItem(tPosL p, tList L);
tPosL first(tList L) ;
tPosL last(tList L);
tPosL previous(tPosL p, tList L);
tPosL next(tPosL p, tList L);

Multilistas

En problemas de programación reales hacen falta soluciones complejas. Es habitual combinar múltiples TAD simples para construir un TAD complejo.

En este caso el TAD multilistas es un ejemplo de combinación de TADs, en este caso, listas.

TAD Multilistas

La multilista consiste, en crear sublistas enlazadas a los nodos de una lista principal.

A una lista de usuarios podríamos enlazar, por ejemplo, una playlist para cada uno.

TAD Multiordenadas

Esta lista multiordenada consta de dos punteros, uno apunta al primer nodo ordenada por nombre, y el otro al primer DNI.

Los están enlazados entre ellos doblemente. Marcando el nodo anterior y siguiente, en dos categorías: Nombre y DNI.

Eliana Reigada Código - © 2024 licensed under CC BY-NC 4.0

Fernando Álvarez Código - © 2023

Pablo Portas López Apuntes - © 2024 licensed under CC BY-NC 4.0