arthurfurlan.org

Hoje eu estava conversando com o Diogo Menezes no messenger sobre como construir uma Lista Duplamente Encadeada em PHP, porque ele precisava criar uma para um trabalho dele da faculdade. Depois de algum tempo de conversa, eu acabei me empolgado com a discussão e resolvi implementar o algoritmo para ver como isso funcionava no PHP (que ao meu ver tem um suporte bem ruim à ponteiros).

Depois de algum tempo quebrando a cabeça para contornar algumas problemas do PHP (comentadas ao final do post) surgiu um primeiro protótipo funcional da lista, que segue abaixo:

Arquivo: Node.class.php

Estrutura utilizada para o armazenamento de valores. A lista na realidade é um grupo de objetos desta classe que apontam, de forma ordenada, para outros objetos desta mesma classe.

<?php
class Node {
    public $Next     = null;
    public $Previous = null;
    public $Data;

    function __construct($value) {
        $this->Data = $value;
    }
}
?>

Arquivo: DLinkedList.class.php

Classe que contém somente um atributo que é o nodo inicial da lista. Essa classe na realiade pode conter vários outros métodos que auxiliam na manutenção da sua lista.

<?php
require_once 'Node.class.php';

class DLinkedList {
    public $Head;

    function __construct($value) {
        $this->Head = new Node($value);
    }
}
?>

Arquivo: index.php

Exemplo de implementação da classe, apenas algoritmo bem simples para mostar o funcionamento.

<?php
require_once 'DLinkedList.class.php';

$List     = new DLinkedList(1);
$LastNode = &$List->Head;

for ($i=0;$i<10;$i++) {
    unset($Node);
    $Node           = new Node($i+2);
    $LastNode->Next = &$Node;
    $Node->Previous = &$LastNode;
    $LastNode       = &$Node;
}

$Node = &$List->Head;
do {
    echo "{$Node->Data}< br />";
    $Node = &$Node->Next;
} while(!is_null($Node->Next));
?>

Observações:

1. Se você é uma pessoa detalhista, deve ter notado no arquivo index.php, que o primeiro comando executado dentro do laço de criação dos nós da lista é o unset($Node); que segundo o manual oficial do PHP, Destrói a variável especificada. Ou seja, eu crio um novo nó, insiro ele na lista para logo em seguida destrui-lo!? Estranho não!? Pois é… Concordo em gênero, número e grau! Porém não é bem isso que acontece! Esse comando é realmente necessário, porque mesmo você alocando explicitamente um novo espaço de memória com new Node($i+2); o PHP não altera a referência na variável $Node e você acaba caindo um loop infinito, pois na segunda volta do laço $LastNodetem o mesmo valor de $Node e nós teremos um nó que aponta para ele mesmo.

2. Uma característica interessante do PHP neste caso, é o fato dele não ser tipado. Dessa forma é possível que essa sua lista guarda qualquer tipo de dados! Ela pode conter um inteiro no primeiro nodo, uma string no segundo, um objeto no terceiro e assim por diante…

3. Sim, eu sei que este código! Mas eu sempre tive vontade de ver como era uma implementação de lista em PHP.