¿Cuál es el punto de la clase SplDoublyLinkedList de PHP y, lo que es más importante, las listas enlazadas en general?

data-structures linked-list

Question

En una búsqueda para ampliar mi destreza en programación, he profundizado muy ligeramente en la biblioteca estándar de PHP . Esto me llevó a descubrir la clase SplDoublyLinkedList . Desde allí, leo las descripciones de Listas vinculadas y Listas vinculadas de manera doble en Wikipedia.

Entiendo cómo funcionan ... Pero no puedo concebir una razón por la cual la necesitamos, o mejor aún, un ejemplo práctico de SplDoublyLinkedList ya que tenemos matrices indexadas y asociativas en PHP.

¿Cómo se usan normalmente las listas enlazadas dentro y fuera de PHP?

Answer 1

Como han mencionado otros, las listas son una alternativa a las matrices fijas que son comunes en otros idiomas. Pero un aspecto importante que a menudo se pasa por alto es que puede insertar o eliminar un elemento de cualquier lugar dentro de una lista de manera muy eficiente.

¿Por qué sería esto importante? Supongamos que tiene varios elementos que desea mantener ordenados en una matriz, quizás para no tener que ordenarlos más tarde o simplemente para minimizar el tiempo de búsqueda. En este caso, una lista puede ser una herramienta muy poderosa. Especialmente para conjuntos de datos muy grandes.

Answer 2

En primer lugar, SplDoublyLinkedList son objetos, como tales

• se pueden extender, por lo que puede anular sus métodos (por ejemplo, puede devolver todas las cadenas en mayúsculas, etc.)
• Las interfaces que implementan se pueden verificar como en myfunc( SplDoublyLinkedList $var ) ...
• Se pasan como referencia por defecto
• etc.

En segundo lugar, SplDoublyLinkedList acepta los modos de iteración, para que pueda eliminar sus elementos sobre la marcha y cambiar de dirección sin tener que volver a ordenar la matriz o complicar su código:

SplDoublyLinkedList :: IT_MODE_LIFO (estilo de pila)

SplDoublyLinkedList :: IT_MODE_FIFO (estilo de cola) El comportamiento del iterador (uno u otro)

SplDoublyLinkedList :: IT_MODE_DELETE (Los elementos son eliminados por el iterador)

SplDoublyLinkedList :: IT_MODE_KEEP (el iterador recorre los elementos)

La cita anterior es de http://simpletechinfo.com/SplDoublyLinkedList que contiene algunos ejemplos de código.

Hay otros beneficios (como foreach no tener que hacer una copia en memoria de todos los datos, etc.)

Answer 3

Están allí porque muchos programadores que vienen de otros lenguajes están acostumbrados a ellos, donde los arreglos tienen tamaños fijos y usted tiene que hacerse cargo de la gestión de la memoria.
Así que para PHP son solo otra herramienta. Se implementan porque muchos algoritmos y patrones se retransmiten en las listas y, por lo tanto, no es necesario cambiarlos a matrices de php.

Answer 4

Las estructuras de datos SPL reducen el consumo de memoria y mejoran el rendimiento. Buenas explicaciones:

Las estructuras de datos son inherentemente independientes del lenguaje y existen como un conjunto de conceptos lógicos basados ​​en las matemáticas. Estos contenedores utilizan diferentes algoritmos según sea apropiado para maximizar la eficiencia.

Por ejemplo, si no necesita las capacidades de mapa hash de una matriz asociativa, es decir, si no está usando la clave de matriz para un propósito específico y solo necesita una matriz enumerada: SplFixedArray (anteriormente SplFastArray, actualmente no documentada) ) Puede ser un reemplazo adecuado. La única advertencia es que el tamaño de la matriz es fijo, lo que significa que debe especificar el tamaño cuando cree una instancia de la clase y se producirá un error si intenta almacenar más de esa cantidad de elementos. Esta es la razón por la que, en promedio, se desempeña mejor que las matrices de PHP estándar.

http://web.archive.org/web/20130805120049/http://blueparabola.com/blog/spl-deserves-some-reiteration

Dentro del código C que compone el intérprete de PHP, las matrices se implementan como una estructura de datos denominada tabla hash o mapa hash. Cuando un valor contenido dentro de una matriz es referenciado por su índice, PHP usa una función de hashing para convertir ese índice en un hash único que representa la ubicación del valor correspondiente dentro de la matriz.

La implementación de este mapa hash permite que las matrices almacenen un número arbitrario de elementos y brinden acceso a todos esos elementos simultáneamente usando las teclas numéricas o de cadena. Las matrices son extremadamente rápidas para las capacidades que proporcionan y son una excelente estructura de datos de propósito general.

En informática, una lista se define como una colección ordenada de valores. Una lista vinculada es una estructura de datos en la que cada elemento de la lista incluye una referencia a uno o ambos elementos a cada lado dentro de la lista. El término "lista doblemente enlazada" se usa para referirse al último caso. En el SPL, esto toma la forma de la clase SplDoublyLinkedList ... Tiene sentido usar listas cuando no se conoce de antemano el número de elementos que se almacenarán y solo es necesario acceder a los elementos por posición secuencial.

http://matthewturland.com/2010/05/20/new-spl-features-in-php-5-3/

Answer 5

Probablemente tienes razón, y simplemente no es muy útil.

Hay muchos usos de las listas enlazadas en teoría (especialmente los enlaces de baile). Pero la mayoría de ellos implica almacenar y clonar sus iteradores en otro lugar, acceder al contenido en más de dos direcciones o dividir y fusionar las listas. SplDoublyLinkedList parecía no tener esos.

Si no es para algoritmos, un uso es permitir que un objeto elimine la referencia de sí mismo en alguna lista en un tiempo constante, liberando su memoria y sin barajar la lista (mediante el hashing o el intercambio con el último elemento) después de la inserción o eliminación. Pero esto requiere almacenar un iterador de la lista en esos objetos.

Sin esas funcionalidades, se comportan como dos deques. Si solo necesita acceder a los elementos utilizando el iterador, son como dos pilas. Una forma mejor en casos simples de un solo hilo, a menos que ya no esté envuelto en una clase, es usar dos pilas (tal vez arreglos arreglados, o ambos extremos del mismo arreglo). Pop de una pila y empuje a otra cuando quiera que el iterador se mueva, y la parte superior de una pila es el elemento actual. Si también necesita acceder a la cabeza y la cola, deberá reemplazar las pilas con deques.

Pero si desea implementar pilas o deques sin conocer el tamaño máximo, o incluso asignar nodos de listas enlazadas normales (en un lenguaje sin esas bibliotecas como en PHP), la mejor manera es encadenar algunas matrices fijas, usando doblemente Listas enlazadas sin esas características. De alguna manera todavía lo necesitarás.

La documentación de PHP en sí misma, como la de Java, sugiere que se supone que son solo una memoria que admite algunas características extra extrañas, ni siquiera dos deques (creo). No los uses si realmente necesitas listas doblemente enlazadas.

Answer 6

Según Wikipedia ,

El principal beneficio de una lista enlazada sobre una matriz convencional es que el orden de los elementos vinculados puede ser diferente del orden en que los elementos de datos se almacenan en la memoria o en el disco. Por esa razón, las listas vinculadas permiten la inserción y eliminación de nodos en cualquier punto de la lista, con un número constante de operaciones.

Por otro lado, las listas enlazadas por sí mismas no permiten el acceso aleatorio a los datos, o cualquier forma de indexación eficiente. Por lo tanto, muchas operaciones básicas, como obtener el último nodo de la lista, encontrar un nodo que contenga un dato determinado o ubicar el lugar donde se debe insertar un nuevo nodo, pueden requerir la exploración de la mayoría de los elementos de la lista.

Así que para responder a tu pregunta, no tengo ni idea. :)