Manipulação de listas em C

Tradicionalmente, listas em C são implementadas através de estruturas (associadas aos nós) armazenadas na memória dinâmica.

A estrutura que implementa um nó de uma lista ligada deve incluir, além do contéudo da informação do nó, um ponteiro para o próximo nó. Tipicamente, a definição da estrutura é da forma:

  typedef struct node {
     /* conteudo */
     ...
     /* proximo no */
     struct node* next;
  } Node;

É possível criar um conjunto de rotinas para a manipulação de listas genéricas se o conteúdo for um ponteiro para qualquer tipo de dado, void*, que pode referenciar até mesmo outras estruturas complexas. Uma variável ponteiro para void denota um endereço genérico, que pode ser atribuído a um ponteiro para qualquer outro tipo sem problemas de conversão.

A linguagem C permite que o programador utilize a área de memória dinâmica através de suas rotinas de alocação dinâmica de memória, que estão presentes na biblioteca padrão da linguagem. Há duas atividades básicas relacionadas à manipulação desta área:

1. o programa pode requisitar uma área de memória dentro do espaço livre disponível; ou

2. o programa pode liberar uma área de memória que tenha sido previamente requisitada do espaço livre e que não seja mais necessária.

Em C, a alocação de memória é suportada pela rotina malloc. Esta rotina recebe um argumento, que é a dimensão em bytes da área necessária. O valor de retorno é o endereço do início da área que o sistema operacional alocou para este pedido, um ponteiro para o tipo void. Por exemplo, para reservar o espaço necessário para o nó de uma lista, seria necessário ter inicialmente declarado a variável que receberá o ponteiro para um nó:

   Node *n;

A definição do valor do ponteiro dá-se através da invocação de malloc:

   n = malloc(sizeof(struct node));

O conteúdo inicial da área alocada é indefinido. Uma variante da rotina de alocação, chamada calloc, inicializa o conteúdo da área alocada para 0's. Esta rotina recebe dois argumentos ao invés de um: o primeiro argumento é o número de itens que será alocado, e o segundo é o tamanho em bytes de cada item. Por exemplo, o trecho de código para criar um nó do tipo Node em uma rotina CREATENODE poderia ser escrito usando calloc:

Para liberar uma área alocada por malloc ou calloc, a rotina free deve ser utilizada. Assim, o exemplo acima poderia ser complementado da seguinte forma:

O que a rotina free faz é retornar o espaço que havia sido pré-alocado dinamicamente para o serviço do sistema operacional que gerencia o espaço livre, que pode assim reutilizar esta área para atender a outras requisições.

Há ainda uma quarta rotina associada à gerência de espaço livre em C, realloc, que permite alterar a dimensão de uma área pré-alocada. Esta rotina recebe dois argumentos, o primeiro sendo o ponteiro para a área que já havia sido alocada e o segundo sendo a nova dimensão para esta área em bytes. O valor de retorno é o endereço (que pode eventualmente ser o mesmo que o original) para a área com a nova dimensão requisitada. Caso o endereço seja diferente, realloc se encarrega de copiar o conteúdo original para a nova área alocada.

Nesses exemplos, não se comentou o que aconteceria caso não houvesse espaço disponível em memória para atender à requisição de alocação dinâmica. Quando malloc (calloc, realloc) não consegue obter o espaço requisitado, o valor retornado pela função é o ponteiro nulo. Este é um comportamento típico em C para indicar erros em rotinas que retornam ponteiros.