Linked lists, a special form of trees, are one of the most typical data structures to
organize dynamic datasets.We’re assuming that you already have an understanding of
the structure, concept, and usage of linked lists, so we won’t go deeply into their
implementation here; we’d rather concentrate on the elemental do’s and don’ts.
As described in the previous sections, PHP 3.0 creates copies of object instances
rather than referring to them by using a pointer.This only enables a very limited,
WORM-like use of linked lists: write once, read multiple. Linked lists can be created,
but not modified.When you try to modify an element in the list, you lose the
reference to all following elements in the list. Regrouping of elements is impossible for
the same reason.
Similarly, double-linked lists can’t be realized in PHP 3.0 (at least, we haven’t
managed it, and we spent quite a few hours in debugging sessions before finally giving
up). Because each node would need a new copy of the list tail to which it’s linking,
you would have to create a multitude of redundant lists with the same content just to
enable the “go back one element” feature.
PHP 4.0, supporting true references, doesn’t impose these limits. Lists can be
created and regrouped randomly—even double-linked lists. Note, however, that it’s
very tricky to distinguish between references and actual copies of list elements.
Beware of dangling pointers—so say programmers of “conventional” languages.We’d
like to modify this for PHP: Beware of redundant copies.
As mentioned earlier, it’s a good idea to create a bulletproof library for your needs—
one that’s easily extensible and features everything related to the required task.We’d
like to present a real-life example here: a library that we’ve developed to handle trees,
and that also works with PHP 3.0.You can find the complete source code on the
CD-ROM.
The library is able to handle double-linked trees with two children per leaf node,
each node having one content container for mixed variables. Every action that can be
performed with the tree has been incorporated into the API, detaching the tree design
from the code that accesses it.
This is exactly the reason why this tree works with PHP 3.0 (seemingly
contradicting what we said earlier).The tree is based on arrays and not on pointers;
because PHP features dynamic arrays, with a little bit of effort it’s very easy to use
such arrays to implement a dynamic tree.
The idea is not new. It has its origins many years ago and is not hard to understand.
Instead of carrying a pointer with each node that addresses another place in memory
to the next node, each node contains indices into the array to each node it’s linked to.
This also has the advantage that PHP is able to warn you of invalid indices, and you
can copy your whole tree by just assigning the variable that contains the tree array to
another variable. On top of that, you can serialize the whole tree and save it “as is” to
any place you want.
To give another, more theoretical explanation:Think of the memory that’s available
to your program as one big array.The size of the elements would probably be bytes, in
the case of physical RAM, but the size of each element doesn’t really matter.The
important thing is that a pointer is simply a number indexing one of these elements
and thus pointing out the beginning of each structure you’re placing into your RAM.
Now, abstracting the whole thing into a language construct (a “real” array), you have
the same situation at a higher level:The PHP array now contains your “RAM,” and
each array element will represent one of the tree nodes. Pointers become indices into
this array, and referencing is done simply by retrieving the correct element from
the array.
Using arrays enables you to create a lot of “RAMs,” increasing and decreasing their
size, disposing of them as a whole or just a single element; overall, a very comfortable
method of memory management. Having all this integrated into a solid library gives
you a nice tool.
