TechTips

Introdução:

Pois bem, primeiro artigo aqui pro TechTips, serei breve(o quando for possível) e objetivo sobre o assunto em questão, e as dúvidas que surgirem envie-as na parte de comentários, okas?

Antes de começar, uma pequena explicação sobre as nomeclaturas: – Lista encadeada(Chained List) ou Lista ligada(Linked list) são a mesma coisa, em algums cursos um termo ou outro é usado mas o objetivo e estrutura não diferem.

Esse artigo está sendo escrito levando como base o desenvolvimento em Delphi 7, versões superiores a essa podem ter implementações nativas dessa estrutura ou mesmo disponibilizar facilitadores que fazem o código ser diferente.

Lista encadeada:

Algumas vezes quando precisamos guardar algumas informações picadas, como pacotes de dados de sockets ou audio, criamos uma lista encadeada que controla toda a informação sequencialmente e prove uma navegação nos dados guardados somente caminhando para frente ou para traz.

A estrutura de uma lista encadeada se divide em 2ª principais variáveis: Data(dados) e Next(ou Prior – Próximo ou Anterior – quando necessário), para cada item no seu encadeamento possue um dado(Ponteiro, valor ou alguma coisa que precisa guardar) e a referência para o próximo item ou anterior na lista. Lista encadeada não disponibiliza acesso direto os items, então você não poderá acessar um item sem navegar nos outros. Uma lista encadeada pode ser aperfeiçoada mas o principal objetivo é disponibilizar uma lista de capacidade quase infinita com a melhor performance do que outras técnicas.

Como você sabe, lista encadeadas não guardam indices para os itens(não tem acesso direto) e isso evita processos de reindexação(reorganização de indices) que consomem um grande tempo quando se tem uma lista grande de itens. Quando precisa-se remover um item de uma lista encadeada, você precisa de fazer a primeira melhoria na estrutura de encadeamento para segurar o item anterior e o próximo para cada item que tenha, e isso prove para você um caminho confortável para manipular os itens sem ter que escrever um monte de códigos e variáveis.

Escrevi a implementação abaixo para servir de base para criação de listas encadeadas com navegação frente-traz:

uses SysUtils;

type
  PPointer = ^Pointer;

  TChainedList = class
  private
    FFirst   : Pointer;
    FLast    : Pointer;
    FCurrent : Pointer;
    FCount   : Integer;
    function GetCurrent: PPointer;
  public
    constructor Create;
    destructor Destroy; override;

    function First : TChainedList;
    function Last  : TChainedList;
    function Prior : TChainedList;
    function Next  : TChainedList;

    function Add: TChainedList;
    function Remove: TChainedList; overload;
    function Remove(AChainedReleaser: Pointer): TChainedList; overload;

    property Current: PPointer read GetCurrent;
    property Count: Integer read FCount;
  end;

implementation

type
  PChainedItem = ^TChainedItem;
  TChainedItem = record
    Prior, Next: PChainedItem;
    Data: Pointer;
  end;

{ TChainedList }

constructor TChainedList.Create;
begin
  FCount := 0;
  FFirst := nil;
  FLast := nil;
  FCurrent := nil;
end;

destructor TChainedList.Destroy;
begin
  First;
  while Current <> nil do
    Remove;

  inherited;
end;

function TChainedList.GetCurrent: PPointer;
begin
  if FCurrent <> nil then
    Result := @PChainedItem(FCurrent).Data
  else
    Result := nil;
end;

function TChainedList.First: TChainedList;
begin
  FCurrent := FFirst;
  Result := Self;
end;

function TChainedList.Last: TChainedList;
begin
  FCurrent := FLast;
  Result := Self;
end;

function TChainedList.Prior: TChainedList;
begin
  if FCurrent <> nil then
    FCurrent := PChainedItem(FCurrent)^.Prior
  else
    FCurrent := nil;
  Result := Self;
end;

function TChainedList.Next: TChainedList;
begin
  if FCurrent <> nil then
    FCurrent := PChainedItem(FCurrent)^.Next
  else
    FCurrent := nil;
  Result := Self;
end;

function TChainedList.Add: TChainedList;
var
  pNew: PChainedItem;
begin
  New(pNew);
  pNew^.Prior := nil;
  pNew^.Next := nil;
  pNew^.Data := nil;

  if FFirst = nil then
  begin
    FFirst := pNew;
    FLast := pNew;
  end else
  begin
    pNew^.Prior := PChainedItem(FLast);
    PChainedItem(FLast)^.Next := pNew;
    FLast := pNew;
  end;

  FCurrent := FLast;
  Result := Self;
  Inc(FCount);
end;

function TChainedList.Remove: TChainedList;
var
  pCur: PChainedItem;
begin
  pCur := FCurrent;
  if pCur^.Data <> nil then
    raise Exception.Create('Current item memory leak detected.');

  if pCur^.Next <> nil then
    pCur^.Next^.Prior := pCur^.Prior;

  if pCur^.Prior <> nil then
    pCur^.Prior^.Next := pCur^.Next;

  if pCur = FFirst then
  begin
    FFirst := pCur^.Next;
    FCurrent := FFirst;
  end else if pCur = FLast then
  begin
    FLast := pCur^.Prior;
    FCurrent := FLast;
  end else
    FCurrent := pCur^.Next;

  Result := Self;
  Dispose(pCur);
  Dec(FCount);
end;

function TChainedList.Remove(AChainedReleaser: Pointer): TChainedList;
type
  TRelease = procedure(APointer: Pointer);
var
  PdrRelease: TRelease;
begin
  @PdrRelease := AChainedReleaser;
  PdrRelease(PChainedItem(FCurrent)^.Data);
  PChainedItem(FCurrent)^.Data := nil;
  Remove;
end;

O entendimento e utilização:

Fiz utilização de ^(circunflexo)s para evidenciar que o acesso é atravez de ponteiro(No caso desse código desde o Delphi 5 a optimização de código já consegue compilar corretamente sem necessidade de uso do ^).

Como vocês podem observar, a classe TChainedList é bastante robusta e prove um controle bem extenso sobre a lista criada, suas caracteristicas são:

1. Navegação Frente-Traz, Inicio e Fim
2. Acesso ao dados guardados no item atraves da propriedade Current
3. Controle de quantidade de items na lista
4. Métodos de adicão e remoção de items, sendo que a remoção disponibiliza um callback para liberação de memória dos dados guardados

Sendo assim, o que é possível fazer com a utilização da TChainedList?
- Vamos ao exemplo prático da utilização, veja abaixo:

O exemplo: Criar uma aplicação Win32 que o usuário escreva em um campo uma palavra e ao pressionar o botão “Adicionar” a palavra é adiciona à frase que eles está construindo e exibida em um local específico. Disponibilizar um botão “Limpar” para limpar a frase.

Passos para iniciar a utilização de teste:

1. Iniciar um projeto Win32 no Delphi
2. nomear o Form principal para frmMain
3. Adicionar um TEdit: edtWord
4. Adicionar um TButton: btnAdd – Caption = “Adicionar”
5. Adicionar um TLabel: lblPhrase
6. Adicionar um TButton: btnClean – Caption = “Limpar”
7. Criar uma variável tipo TChainedList de escopo publico em frmMain de nome Phrase
8. Criar um método chamado UpdateList de escopo publico em frmMain

Código:

uses ChainedListCtrl;

type
  TfrmMain = class(TForm)
    edtWord: TEdit;
    btnAdd: TButton;
    lblPhrase: TLabel;
    btnClean: TButton;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure btnAddClick(Sender: TObject);
    procedure btnCleanClick(Sender: TObject);
  private
    { Private declarations }
  public
    Phrase: TChainedList;
    procedure UpdateList;
  end;

var
  frmMain: TfrmMain;

implementation

{$R *.dfm}

Linkando o evento FormCreate do frmMain o Phrase deve ser criado:

{ Note: Create the Chain List Control Object
}
procedure TfrmMain.FormCreate(Sender: TObject);
begin
  Phrase := TChainedList.Create;
end;

Linkando o evento FormDestroydo frmMain o Phrase deve ser destruído:
OBS: A destruição do objeto Pharse não está associada a liberação de memória dos items, então caso a o aplicativo seja fechado e o Pharse destruido sem limpar a lista ocorrerá vazamento de memória(vide btnCleanClick para liberação dos items)

{ Note: Destroy the Chain Object
}
procedure TfrmMain.FormDestroy(Sender: TObject);
begin
  Phrase.Free;
end;

Codificando o método UpdateList. Esse método é o responsável por exibir a frase, listando as palavras adicionadas na lista.

{ Note: Update the Label to hold all the words
        included on the Chained list
}
procedure TfrmMain.UpdateList;
var
  sPhrase: string;
begin
  sPhrase := '';
  Phrase.First;
  while Phrase.Current <> nil do
  begin
    if sPhrase <> '' then
      sPhrase := sPhrase + ' ';

    sPhrase := sPhrase + PChar(Phrase.Current^);
    Phrase.Next;
  end;
  lblPhrase.Caption := sPhrase;
end;

Linkando o evento OnClick do btnAdd o texto escrito em edtWord deve ser adicionado a lista Phrase:

{ Note: Add the text on the Chain
   p.s: StrNew create a copy of the string that will be managed
        out of the garbage collector(str refcount structure)
}
procedure TfrmMain.btnAddClick(Sender: TObject);
begin
  Phrase.Add.Current^ := StrNew(PChar(edtWord.Text));
  UpdateList;
end;

Linkando o evento OnClick do btnClean a lista Phrase deve ser limpa e os items devem ser removidos para evitar vazamento memória.

{ Note: Clean the Chain list
   p.s: StrDispose release the memory of the create string
        to avoid memory leaks
}
procedure TfrmMain.btnCleanClick(Sender: TObject);
begin
  Phrase.Last;
  while Phrase.Current <> nil do
    Phrase.Remove(@StrDispose);
  UpdateList;
end;

Os comentários em inglês no código estão presentes porque o artigo é uma transcrição do artigo Delphi: Chained List juntamente com a publicação do Delphi: Utils :: TChainedList.

Entendendo a estrutura de uma Lista encadeada:

Estou complementando aqui o artigo, o que vai diferir do artigo em inglês será essa parte, pois agora explicarei a estrutura da lista encadeada de forma mais programática.

De acordo com os exemplos e explicações acima podemos concluir que a lista é criada através dos itens existentes e relacionados e não por um outro objeto que controla os items individualmente, ou seja, um item sabe que o(s) “vizinho(s)” existe(m) sem precisar sair do seu escopo.

O funcionamento disso em programação é a base de referências(ponteiro), pois assim a movimentação de memória e consumo da mesma fica estrito a modificações nos itens e não na gerência da lista. Mas o que isso quer dizer?
- Quer dizer que para se remover um item você precisa apenas avisar seu(s) vizinho(s) que ele não está mais na lista. Programaticamente falando o resultado disso é:

Lista:
    Item1
      Next -> Item2
                Next -> Item3
                          Next -> nil

Remoção do Item2
    Item1
      Next -> Item2.Next -> Item3
                              Next -> nil

              Item2(Removido)
                Next -> Item3

O que foi feito acima foi somente a assimilação do Next do Item1 com o Next do Item2, resultando em uma lista que caminha do Item1 para o Item3, sendo que o Item2 ficará fora da sequência.

Outro fato importante é que trabalhando com referências, você não terá objetos repetidos, ou seja, se você modificar o Item3 seja pelo Item2.Next ou seja depois da remoção pelo Item1.Next você estará acessando o mesmo ponto da memória. Mas essas explicações não serão contempladas nesse artigo para não estender muito o assunto e perder o foco. Mas vale a dica de entendimento de referências(Pointeiros) para todos que não compreendem bem o estrutura da memória.

Exemplo com descendência (mais código, menos dificuldade):

Para simplificar um pouco as coisas, deixar a utilização dos ponteiros centralizada, você pode estender a classe da forma que precisar em seu projeto, neste caso vou exemplificar como seria a extensão de TChainedList para o nosso exemplo:

type
  TPhraseChainedList = class(TChainedList)
  public
    procedure AddWord(const AWord: string);
    procedure RemoveWord;
    procedure Clear;
    function CurrWord: string;
  end;

{ TPhraseChainedList }

procedure TPhraseChainedList.AddWord(const AWord: string);
begin
  Add.Current^ := StrNew(PChar(AWord));
end;

procedure TPhraseChainedList.RemoveWord;
begin
  Remove(@StrDispose);
end;

procedure TPhraseChainedList.Clear;
begin
  Last;
  while Current <> nil do
    RemoveWord;
end;

function TPhraseChainedList.CurrWord: string;
begin
  Result := PChar(Current^);
end;

Assim, na hora de utilizar, 4 métodos do nosso exemplo anterior vão ser modificados: FormCreate, UpdateList, btnAddClick e btnCleanClick;

{ Note: Create the Chain List Control Object
}
procedure TfrmMain.FormCreate(Sender: TObject);
begin
  Phrase := TPhraseChainedList.Create;
end;

{ Note: Update the Label to hold all the words
        included on the Chained list
}
procedure TfrmMain.UpdateList;
var
  sPhrase: string;
begin
  sPhrase := '';
  Phrase.First;
  while Phrase.Current <> nil do
  begin
    if sPhrase <> '' then
      sPhrase := sPhrase + ' ';

    sPhrase := sPhrase + Phrase.CurrWord;
    Phrase.Next;
  end;
  lblPhrase.Caption := sPhrase;
end;

{ Note: Add the text on the Chain
}
procedure TfrmMain.btnAddClick(Sender: TObject);
begin
  Phrase.AddWord(edtWord.Text);
  UpdateList;
end;

{ Note: Clean the Chain list
}
procedure TfrmMain.btnCleanClick(Sender: TObject);
begin
  Phrase.Clear;
  UpdateList;
end;

Caso seja interessante podemos estender ainda mais, criando uma função que me retorna a frase, assim não teriamos que nos preocupar com a geração da frase quando for preciso pegar o valor em outro local.

  TPhraseChainedList = class(TChainedList)
  public
    ...
    function ThePhrase: string;
  end;

function TPhraseChainedList.ThePhrase: string;
begin
  Result := '';
  First;
  while Current <> nil do
  begin
    if Result <> '' then
      Result := Result + ' ';

    Result := Result + CurrWord;
    Next;
  end;
end;

O UpdateList ficaria assim, ou mesmo deixaria de existir porque não teria uma grande utilidade após a implementação acima:

{ Note: Update the Label to hold all the words
        included on the Chained list
}
procedure TForm1.UpdateList;
begin
  lblPhrase.Caption := Phrase.ThePhrase;
end;

Agradecimentos:

Quero aqui agradecer ao pessoal de bem que sempre está em contato comigo me dando apoio.
Ao Leonel que deixou eu escrever esse monte de coisas aqui.
Ao Itamar Bermond que fornece a hospedagem do meu site, porque sem isso talvez nem escreveria nada de útil na internet.
À meus punhos e cérebro.

E lembrando: Fé move montanhas e a programação move o futuro.

Abraços e agradeço a paciência.