Listas Ligadas - Parte 1

Nesta nova série vou explicar o que são listas ligadas e apresentar os algorítmos envolvidos e algumas formas de implementação em C e C++.

Dê uma forma genérica poderíamos dizer que uma lista é um conjunto ordenado de um número variável de elementos, para a qual estão definidas funções de inserção e remoção de elementos. Para entendermos isto melhor, precisamos primeiro falar um pouco sobre estrutrua de dados.

Estrutura de Dados I

No nível mais baixo, as informações manipuladas por um computador consistem em conjuntos de itens elementares. As maneiras como estes item elementares se relacionam logicamente são as estruturas de dados. As formas como estas estruturas lógicas são implementadas fisicamente na memória de um computador são as estruturas de armazenamento.

Os itens elementares (ou estruturas primitivas de dados) são aqueles manipulados diretamente pelo computador ou linguagem de programação, tais como:

• números inteiros
• números reais (ponto fixo ou flutuante)
• caracteres
• valores lógicos
• ponteiros
  

Obs.: Na maioria dos computadores atuais, os itens elementares são armazenados na memória como sequências de bytes. A distinção entre eles é consequência das instruções utilizadas para manipulá-los e não do conteúdo dos bytes. Por exemplo, um byte contendo o valar hexadecimal 0x30 pode ser interpretado como o número decimal 48 ou o caracter ‘0’, dependendo do código que o manipula. A linguagem C segue esta filosofia, permitindo misturar e re-interpretar (via cast) os tipos quase que livremente. Se por um lado isto dá uma imensa flexibiidade, por outro potencializa erros catastróficos.

Ponteiros

Do ponto de vista teórico, um ponteiro é uma referência a uma estrutura de dados. Do ponto de vista prático, um ponteiro é uma variável cujo conteúdo é o endereço de uma outra variável.

Vamos considerar a seguinte sequência de código C:

int a, b;
int *p;

a = 1;
p = &a;
b = *p;
*p = 5;

Nas duas primeiras linhas declaramos 3 variáveis (dois inteiros e um ponteiro para inteiro). O compilador irá reservar posições na memória para estas variáveis. Suponto que tanto um inteiro como um ponteiro ocupem 4 bytes na memória, podemos ter algo como:

Endereço  Conteúdo
2000      valor de a
2004      valor de b
2008      valor de p

A instrução “a = 1” coloca o valor 1 no endereço 2000. Quando escrevemos “&a” obtemos o endereço de a, portanto “p = &a” coloca o valor 2000 no endereço 2008. A notação “*p” no lado direito de uma atribuição significa:

• pegue o valor da variavel p (2000 no nosso caso)
• considere este valor como um endereço e pegue o valor contido neste endereço (1 no nosso caso)

portanto, “b = *p” coloca o valor 1 no endereço 2004.

Por último, “*p” no lado esquerdo de uma atribuição significa:

• pegue o valor da variavel p (2000 no nosso caso)
• considere este valor como um endereço e coloque o resultado do lado direito neste endereço (5 no nosso caso)

portanto, “*p = 5” coloca o valor 5 no endereço 2000.


No próximo post vamos ver um pouco mais sobre estrutura de dados, examinando estruturas, vetores e matrizes.