program listaligada;
(* Antigamente, penso que não era possível fazer o que fiz aqui: utilizei um
tipo de dados dentro da sua própria definição (especificamente, o campo
`next` é um apontador para o record que estamos a definir.
Era necessário fazer algo como:
type
PNo = ^No;
No = record
...
next: PNo;
end;
Hoje em dia parece que não é preciso, ou então nunca foi, mas pronto, nunca
faz mal prevenir. *)
type
no = record
val: integer;
next: ^no;
end;
(* Essencial à compreensão de listas ligadas é perceber que um apontador é
apenas uma etiqueta, um número que representa um endereço de memória, e não
um objecto ou uma estrutura de dados por si só.
Por esse motivo, os apontadores são bastante leves, pois implicam uma
alocação de 4 ou 8 bytes (32 ou 64bits).
Nas listas ligadas, precisamos tipicamente de 3 apontadores (podemos fazer
isto com dois, mas é mais intuitivo com 3):
* head : aponta para o primeiro nó da lista)
* cur : funciona como "cursor", ou nó actual ("current")
* last : nó actual da iteração anterior (na prática, o valor anterior de cur)
Inicialmente, todos têm valor «nil» (representa a ausência de um endereço
válido).
Na primeira iteração, alocamos espaço para `cur` através de new(); agora,
`cur` contém o endereço de uma estrutura `no`:
+-----+------+
cur ---> | val | next |
+-----+------+
No entanto, como estamos na primeira iteração, também queremos marcar este nó
como sendo a cabeça da lista. Então dizemos que `head := cur`, copiando o
endereço contido em `cur` para `head` (atenção: apenas o endereço numérico é
copiado. a memória em si, onde reside o primeiro elemento da lista, não é
duplicada). Efectivamente, `cur` e `head` apontam agora para o mesmo bloco
de memória:
head
v
+-----+------+
cur ---> | val | next |
+-----+------+
Vamos agora passar à próxima iteração. Antes disso, temos que informar que
`cur` vai deixar de ser o nó actual, para passar a ser o anterior, de forma a
conseguirmos referir-nos a ele quando estivermos na iteração seguinte.
Para isso, `last := cur`, e os 3 apontadores apontam para o mesmo elemento:
head
v
+-----+------+
cur ---> | val | next |
+-----+------+
^
last
Na iteração seguinte, fazemos novamente `new(cur)`, o que aloca novamente
memória para um novo record `no` e coloca o seu endereço em `cur`:
head
v
+-----+------+ +-----+------+
| val | next | cur ---> | val | next |
+-----+------+ +-----+------+
^
last
Como podems ver, `head` e `last` apontam ambos para o primeiro elemento, mas
`cur` aponta para outro.
Qual o primeiro elemento da lista? Fácil, basta ver para onde `head` aponta.
Mas agora falta-nos ligar os elementos, para que seja uma verdadeira lista
ligada e não apenas um conjunto de records dispersos na memória.
Para isso, dizemos que o campo `next` do último nó da lista (apontado por
`last`) aponta para o novo nó que criámos, apontado por `cur`:
last^.next := cur;
head
v
+-----+------+ +-----+------+
| val | next---\ cur ---> | val | next |
+-----+------+ | +-----+------+
^ | ^
last \-----------------/
Agora, basta fazermos o que fizemos anteriormente: apontar `last` para o nó
actual, de forma a podermos repetir tudo na iteração seguinte:
head last
v v
+-----+------+ +-----+------+
| val | next---\ cur ---> | val | next |
+-----+------+ | +-----+------+
| ^
\-----------------/
*)
var
(* head: Cabeça da lista
* cur: Cursor, current, nó actual
* last: Elemento da iteração anterior
*)
head, cur, last: ^no;
i: integer;
begin
for i := 1 to 10 do begin
(* Alocamos memória para o nó actual *)
new(cur);
if i = 1 then
(* Se o nó for o primeiro, apontamos `head` para ele *)
head := cur
else
(* Senão, então dizemos que o `next` do anterior é o actual *)
last^.next := cur;
cur^.val := i * i;
(* O nó actual passa a ser o anterior da iteração seguinte *)
last := cur;
end;
(* Apontamos o nosso "cursor" à cabeça da lista, e iteramos... *)
cur := head;
(* Enquanto o cursor for diferente de nil (enquanto apontar para nó válido *)
while (cur <> nil) do begin
(* Escrevemos o seu valor *)
writeln(cur^.val);
(* Usamos `last` como variável auxiliar *)
last := cur;
(* Avançamos o cursor para o próximo elemento *)
cur := cur^.next;
(* E libertamos a memória do anterior *)
dispose(last);
end;
end.