Nesta aula iniciamos o estudo das Listas Lineares, a primeira de diversas estruturas de dados que veremos ao longo da disciplina.

1. Listas Lineares

Uma lista linear é uma sequência de nodos com as seguintes características:

• Simples manipulação;
• Possui uma relação de ordem entre os nodos;
• É sequencial;
• A estrutura interna de cada nodo é abstraída (não importa, do ponto de vista da lista, o que cada nodo guarda);
• Todos os elementos são do mesmo tipo.

Podemos visualizar uma lista como uma sequência de nodos ligados por uma relação de ordem, onde cada nodo guarda um conjunto de informações:

(a) - (b) - (c) - (d) ... (z)

           |
           v

+--------+----+------+-------+-------+
| Número | RG | Nome | Nasc. | Cargo |
+--------+----+------+-------+-------+

2. Definição formal

Uma lista linear é uma coleção n >= 0 de nodos x[0], x[1], ..., x[n-1], cujas propriedades estruturais relevantes envolvem as posições relativas dos nodos:

• x[0] é o primeiro nodo e x[n-1] é o último nodo;
• x[k] é precedido por x[k-1] e sucedido por x[k+1];
• n = 0 representa a lista vazia.

3. Aplicações

• Notas de alunos;
• Cadastro de funcionários de uma empresa;
• Dias da semana;
• Letras de uma palavra;
• Cartas de baralho.

4. Operações

• Criação;
• Destruição;
• Inserção de um nodo na i-ésima posição;
• Exclusão do i-ésimo nodo;
• Acesso ao i-ésimo nodo;
• Alteração do i-ésimo nodo;
• Concatenação de duas listas;
• Cópia da lista;
• Localizar nodo a partir da informação (busca);
• Contar elementos da lista.

5. Relação com TAD

Uma lista linear é uma implementação concreta do TAD Lista (visto na Aula 2b, com seus dois papéis: dados + operações):

• O cliente não precisa saber como a lista é implementada internamente;
• O programador deve conhecer a estrutura interna para implementá-la corretamente.

Essa implementação pode ser feita de duas formas:

• Contiguidade física (assunto desta aula);
• Encadeamento (veremos em aulas futuras).

A partir dessas duas formas de implementação, surgem diversos tipos de listas que estudaremos ao longo da disciplina:

• Linear (estática/dinâmica);
• Linear circular (estática/dinâmica);
• Simplesmente encadeada;
• Duplamente encadeada;
• Circular encadeada;
• Pilhas;
• Filas;
• Deques.

6. Contiguidade física

• A representação utiliza a estrutura linear da memória para armazenar a lista;
• Um arranjo de uma dimensão (vetor) é usado;
• Nodos logicamente adjacentes são mantidos em posições de memória fisicamente adjacentes;
• A lista sempre começa no índice 0 do vetor — basta guardar quantos elementos estão ocupados (o tamanho da lista) para saber exatamente onde ela termina;
• A lista possui uma capacidade máxima estabelecida (tamanho do vetor);
• Pode ser estática (capacidade fixada em tempo de compilação) ou dinâmica (capacidade definida em tempo de execução, com malloc()) — veremos a estática nesta aula, que será o padrão adotado no restante da disciplina.

A ideia é manter os elementos sempre a partir da posição 0, ocupando as primeiras tamanho posições de um vetor de capacidade fixa:

índice:   0    1    2    3    4    5    6    7   ...  CAPACIDADE-1
dados:  [ L0 ][ L1 ][ L2 ][ L3 ][ L4 ][    ][    ]...[            ]
                                    ^
                                    |
                          tamanho = 5 (posições 0 a 4 ocupadas)

7. TAD Lista Linear (estática)

Vamos implementar uma lista de Produto, onde cada nodo guarda um código, um nome e um preço. Esse é o dado a ser armazenado em cada nodo da lista — poderia ser um simples int, float, ou qualquer outro tipo:

typedef struct {
    int cod;
    char nome[50];
    float preco;
} Produto;

E o tipo da lista propriamente dita, com o vetor de capacidade fixa e um único campo de controle, tamanho:

#define CAPACIDADE 50

typedef struct {
    int tamanho;
    Produto dados[CAPACIDADE];
} ListaContEst;

Operações

Inicialização — uma lista vazia é representada por tamanho = 0:

void inicializar(ListaContEst *l) {
    l->tamanho = 0;
}

Tamanho — número de elementos atualmente armazenados na lista. Como o próprio campo tamanho já guarda esse valor, a operação apenas o devolve — mas continua sendo uma função, e não um acesso direto ao campo, para que quem usa a lista (o cliente) não precise conhecer o nome do campo interno:

int tamanho(const ListaContEst *l) {
    return l->tamanho;
}

Acesso — retorna o produto armazenado na posição pos, sem removê-lo. Como a lista sempre começa no índice 0, a posição lógica é o índice físico no vetor:

Produto acessar(const ListaContEst *l, int pos) {
    Produto pAux;
    if (pos >= l->tamanho || pos < 0) // posição inválida
        pAux.cod = -1;
    else
        pAux = l->dados[pos];

    return pAux;
}

Inserção — a posição pos indica onde o novo produto deve entrar (0 é sempre o início da lista). Para abrir espaço, a função desloca todos os elementos a partir de pos uma posição para a direita:

int inserir(ListaContEst *l, Produto novo, int pos) {
    int i;

    if (l->tamanho == CAPACIDADE) return 0; // lista cheia
    if (pos > l->tamanho || pos < 0) return 0; // posição inválida

    for (i = l->tamanho; i > pos; i--) // abre espaço, empurrando para a direita
        l->dados[i] = l->dados[i - 1];

    l->dados[pos] = novo;
    l->tamanho++;
    return 1;
}

Remoção — remove o produto da posição pos, puxando os elementos seguintes uma posição para a esquerda:

int remover(ListaContEst *l, int pos) {
    int i;

    if (pos >= l->tamanho || pos < 0) return 0; // posição inválida

    for (i = pos; i < l->tamanho - 1; i++) // puxa elementos seguintes para a esquerda
        l->dados[i] = l->dados[i + 1];

    l->tamanho--;
    return 1;
}

Busca — diferente de acessar (que já sabe exatamente onde procurar), a busca recebe apenas um código e precisa encontrar a posição correspondente, comparando produto por produto até achar (ou até chegar ao fim da lista). É a mesma ideia da busca sequencial vista em aulas anteriores, aplicada agora sobre os elementos da lista:

int buscar(const ListaContEst *l, int cod) {
    int i;

    for (i = 0; i < l->tamanho; i++) {
        if (l->dados[i].cod == cod) {
            return i; // posição onde o produto foi encontrado
        }
    }

    return -1; // não encontrado
}

Destruição — para esta implementação (estática, sem alocação dinâmica), basta invalidar o tamanho:

void destruir(ListaContEst *l) {
    l->tamanho = 0;
}

8. Complexidade das operações

Retomando o que vimos na Aula 2a, podemos analisar o pior caso de cada operação em função do número de elementos n atualmente na lista:

Note a diferença entre acessar e buscar, apesar de ambas "lerem" elementos da lista: acessar já sabe exatamente qual índice acessar (recebido como parâmetro), então é sempre O(1); buscar não sabe onde está o elemento procurado, e por isso pode precisar examinar a lista inteira até encontrá-lo (ou concluir que ele não existe).

Já inserir e remover só são O(1) no melhor caso — quando a operação ocorre exatamente na última posição da lista (pos == tamanho(l) para inserir, pos == tamanho(l) - 1 para remover), caso em que nenhum elemento precisa ser deslocado.

Resumo

Exercícios

1. Explique, com suas próprias palavras, o que significa dizer que "a estrutura interna dos nodos é abstraída" em uma lista linear.
2. Considerando a definição formal vista em aula (x[0], x[1], ..., x[n-1]), o que caracteriza x[0] e x[n-1]? O que representa n = 0?
3. Na implementação por contiguidade física vista em aula, por que basta guardar o campo tamanho para saber quantos elementos a lista possui e onde ela termina, sem precisar de nenhuma outra variável de controle?
4. Na função inserir, por que o pior caso ocorre ao inserir na posição 0, e o melhor caso ocorre ao inserir na posição tamanho(l) (ou seja, no final da lista)?
5. Explique por que a operação acessar tem complexidade O(1), enquanto buscar tem complexidade O(n) no pior caso, mesmo as duas "lendo" elementos da lista.
6. Cite uma situação em que inserir sempre no final da lista (posição pos = tamanho(l)) evitaria o custo de deslocar elementos. Essa situação ainda seria vantajosa se também precisássemos remover elementos com frequência do início da lista?
7. A lista implementada nesta aula é chamada de "estática" (ListaContEst) porque sua capacidade (CAPACIDADE) é fixada em tempo de compilação. Reescreva a struct e a função inicializar para uma versão dinâmica, chamada ListaContDin, em que o vetor dados é alocado com malloc() (como visto nas Aulas 1b e 3), permitindo que a capacidade da lista seja definida em tempo de execução, através de um parâmetro. Lembre-se de também escrever uma função destruir que libere corretamente essa memória.
8. Implemente uma função void imprimir(ListaContEst *l) que percorra a lista e imprima o código, o nome e o preço de cada produto, um por linha.
9. Implemente uma função int buscarPorNome(ListaContEst *l, char *nome), análoga a buscar, mas que procure pelo campo nome (usando strcmp) em vez do campo cod. Qual é a complexidade dessa nova função?
10. Implemente uma função float precoMedio(ListaContEst *l) que retorne o preço médio dos produtos da lista. Tome cuidado com o caso da lista vazia.
11. Escreva um pequeno main() que: inicialize uma ListaContEst; insira três produtos (nas posições 0, 1 e 1, nessa ordem, como no exemplo de uso das aulas anteriores); e então chame imprimir para exibir o resultado. Qual é a ordem final dos produtos na lista?

Sugestões de Respostas dos Exercícios

typedef struct {
    int tamanho;
    int capacidade;
    Produto *dados; // vetor alocado dinamicamente, em vez de tamanho fixo
} ListaContDin;

void inicializar(ListaContDin *l, int capacidade) {
    l->tamanho = 0;
    l->capacidade = capacidade;
    l->dados = (Produto *) malloc(capacidade * sizeof(Produto));

    if (l->dados == NULL) {
        printf("Erro: memoria insuficiente.\n");
        exit(1);
    }
}

if (l->tamanho == l->capacidade) return 0; // lista cheia

void destruir(ListaContDin *l) {
    free(l->dados);
    l->dados = NULL;
    l->tamanho = 0;
}

void imprimir(ListaContEst *l) {
    int i;
    for (i = 0; i < tamanho(l); i++) {
        Produto p = acessar(l, i);
        printf("%d - %s - %.2f\n", p.cod, p.nome, p.preco);
    }
}

int buscarPorNome(ListaContEst *l, char *nome) {
    int i;
    for (i = 0; i < l->tamanho; i++) {
        if (strcmp(l->dados[i].nome, nome) == 0) {
            return i; // posição onde o produto foi encontrado
        }
    }
    return -1; // não encontrado
}

float precoMedio(ListaContEst *l) {
    int i;
    float soma = 0;

    if (tamanho(l) == 0) {
        return 0; // evita divisão por zero
    }

    for (i = 0; i < tamanho(l); i++) {
        Produto p = acessar(l, i);
        soma += p.preco;
    }

    return soma / tamanho(l);
}

int main() {
    ListaContEst l;
    Produto p1 = {1, "Caneta", 2.50};
    Produto p2 = {2, "Caderno", 15.90};
    Produto p3 = {3, "Lapis", 1.20};

    inicializar(&l);

    inserir(&l, p1, 0); // lista: [Caneta]
    inserir(&l, p2, 1); // lista: [Caneta, Caderno]
    inserir(&l, p3, 1); // lista: [Caneta, Lapis, Caderno]

    imprimir(&l);

    return 0;
}

Código para Download

O TAD ListaContEst completo, exatamente como visto nesta aula, dividido em interface (listaContEst.h) e implementação (listaContEst.c), junto com um main.c de exemplo: