Estructura Dinamica de Datos

Punteros: Son las celulas de memoria a las que podemos tener acceso por un identificador. Pero estas variables se guardan en lugares concretos de la memoria de la computadora. Para nuestros programas, la memoria de la computadora es solamente una sucesión de las células de 1 octeto (la talla mínima para un dato), cada una con una direccion única. La memoria de computadora puede ser comparada con una calle en una ciudad. En una calle todas las casas se numeran consecutivamente con un identificador único tal que si hablamos del número 27 de la calle Córdova, podremos encontrar el lugar sin pérdida, puesto que debe haber solamente una casa con ese número y, además, nosotros sabemos que la casa estará entre las casas 26 y 28.

Estructuras dinamicas 

Las estructuras dinámicas de datos son estructuras que cuya dimensión puede crecer o disminuir durante la ejecución del programa. Una estructura dinámica de datos es una colección de elementos llamados nodos. Al contrario que un array, que contiene espacio para almacenar un número fijo de elementos, una estructura dinámica de datos se amplía y contrae durante la ejecución del programa.
Las estructuras dinámicas de datos se pueden dividir en dos grandes grupos:
- Lineales: Listas enlazadas, pilas, colas
- No lineales: Arboles, grafos
Las estructuras dinámicas de datos son de gran utilidad para almacenar datos del mundo real, que están cambiando constantemente. Por ejemplo si tenemos almacenados en un array los datos de los alumnos de un curso, los cuales estan ordenados de acuerdo al promedio, para insertar un nuevo alumno seria necesario correr cada elemento un espacio: Si en su lugar se utilizara una estructura dinámica de datos, los nuevos datos del alumno se pueden insertar fácilmente.

Listas:

Listas Enlazadas: Una lista enlazada es un conjunto de elementos llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo.
El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista. El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.
La lista enlazada se muestra en la siguiente figura:
Cabecera
Las operaciones que normalmente se ejecutan con listas incluyen:

1. Recuperar informacion de un nodo específico.
2. Encontrar el nodo que contiene una información específica.
3. Insertar un nuevo nodo en un lugar específico.
4. Insertar un nuevo nodo en relación a una información particular.
5. Borrar un nodo existente.

Ejemplo basico de la creacion de una lista con tres nodos y luego su recorrido y su impresion. El algoritmo es muy sencillo y tiene como objetivo mostrar como se puede implementar estructuras de datos dinamicas con PHP, mas que la optimizacion o mejoramiento del mismo. Por lo tanto el algoritmo puede ser mejorado y adaptado a la necesidad requerida.

<?php
    // Definicion de la clase tipo NODO
    Class Nodo
    {
        public $Dato;
        public $Proximo;
        
        function __construct($Dato)
        {
            $this->Dato = $Dato;
        }
    }
    
    //Creacion del nodo cabeza de la lista con el dato 1
    $cabeza = new Nodo(1);
    
    //Creacion de un segundo nodo con el dato 2
    $aux = new Nodo(2);
    
    //Enlazar el campo proximo del nodo cabeza, con el nuevo nodo creado, apuntado por aux
    $cabeza->Proximo = $aux;
    
    // creacion de un tercer nodo con el dato 3
    $aux = new Nodo(3);
    
    //Enlazar el segundo nodo con el primero, esto puede mejorar claro
    $cabeza->Proximo->Proximo = $aux;

    //Asignar el valor null, al ultimo nodo, para identificar el final de la lista
    $aux->Proximo = 'null';
    
    // Llevo la direccion de la cabeza de la lista a una variable apuntador "aux"
    $aux = $cabeza;
    
    // Recorrer la lista mientras que al apuntador aux sea diferente de "null"
    while ( $aux != 'null' )
    {
        //Imprimir el dato contenido en el nodo apuntado por "aux"
        echo $aux->Dato, "<br />\n";
        
        //Pasar al siguiente nodo de la lista
        $aux = $aux->Proximo;    
    }
?>