Explicación de la estructura de datos: Listas Enlazadas

  

    
Definición
Las listas enlazadas son una estructura de datos que almacena una secuencia de elementos. A diferencia de los arreglos, no requieren que estén almacenados juntos, sino que cada elemento contenga un puntero que apunte al siguiente nodo de la lista.

Nodos
Cada elemento de la lista se llama nodo, y consta de dos partes: el valor del elemento y un puntero al siguiente nodo. El primer nodo de la lista se llama cabeza o head en inglés,  y si un nodo no tiene un siguiente nodo, su puntero apunta a null o nulo.

Punteros
Los punteros son variables que contienen la dirección de memoria de otra variable. 
En el contexto de las listas enlazadas, los punteros se utilizan para conectar los nodos entre sí. Cada nodo tiene un puntero que apunta al siguiente nodo en la lista. 

Ventajas
La ventaja principal de las listas enlazadas es que permiten la inserción y eliminación eficiente de elementos en cualquier posición de la lista, ya que solo necesitas modificar los punteros del nodo anterior y siguiente. Además, las listas enlazadas no tienen un tamaño fijo, por lo que pueden crecer o disminuir según sea necesario.

Desventajas
Sin embargo, las listas enlazadas también tienen algunas desventajas. Por ejemplo, no permiten el acceso aleatorio a los elementos de la lista, lo que significa que para acceder a un elemento específico, debes recorrer la lista desde la cabeza hasta ese elemento. Además, las listas enlazadas pueden requerir más memoria que los arreglos, ya que cada nodo debe almacenar tanto el valor del elemento como el puntero al siguiente nodo.

Operaciones Básicas- Inserción
1.- Se crea un nuevo nodo que contenga el valor del elemento que se desea insertar.
2.- El nuevo nodo debe ser conectado a la lista en la posición adecuada. Para ello, se deben modificar los punteros de los nodos adyacentes al nuevo nodo.
3.- Si se inserta el nuevo nodo al principio de la lista, se debe actualizar el puntero de la cabeza de la lista para que apunte al nuevo nodo y sea retornado

Operaciones Básicas - Búsqueda
1.- Se comienza a recorrer desde el primer nodo y se sigue avanzando por los nodos siguientes hasta llegar al final de la lista.
2.- Se compara el valor del elemento que buscas con el valor del nodo actual que se recorre. Si los valores son iguales, estos se encontraron, si no, se avanza en la lista enlazada.
3.- Si se  llega al final de la lista enlazada y no se ha encontrado el elemento que se busca, significa que el elemento no está en la lista.

Operaciones Básicas - Eliminación
1.- Primero verificamos que exista la lista, en caso de que no exista, retornar null.
2.- Verificar que el primer nodo sea el que se tenga que eliminar,  si es así, se elimina y se mueve el puntero head a su siguiente posición.
3.- Realizar un ciclo para encontrar un nodo que apunte a el siguiente nodo con el valor a eliminar: Si llega al final, es porque no consiguió el valor en la lista.
4.- En caso de que se encuentre un nodo con el valor a eliminar: se asigna a su siguiente posición, y se elimina el nodo con el valor.

¿Necesitas ayuda?
Si tienes dudas sobre listas enlazadas, te invito a que visites mi canal de YouTube Hermes Coder. Allí encontrarás vídeos y tutoriales gratuitos que te ayudarán a resolver ejercicios de algoritmo de maneras que capaz no habías pensado. También puedes ponerte en contacto conmigo a través de WhatsApp para obtener más información sobre consultorías.
           

Presentación

Código en php

<?php
 
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}
 
class Solution {
 
    function show($head){
        echo 'VALORES DE LAS LISTAS'."\n";
        while($head){
            echo $head->val."\n";
            $head=$head->next;
        }
    }
 
    function insercion($head,$val) {
        //Paso #1
        $newlistNode= new ListNode($val);
 
        //Paso #2
        $newlistNode->next = $head;
 
        //Paso #3
        $head=$newlistNode;
        return $head;
    }
 
    function busqueda($head,$val){
 
        $aux=$head;
 
        //Paso #1
        while($aux){
 
            //Paso #2
            if($aux->val==$val) {
                echo 'SE ENCONTRO EL VALOR '.$val.' EN LA LISTA'."\n";
                return true;
            }
            $aux=$aux->next;
        }
 
        //Paso #3
        echo 'NO SE ENCONTRO EL VALOR '.$val.' EN LA LISTA'."\n";
        return false;
    }
 
    function eliminar($head,$val){
 
        //Paso #1
        if($head==null) return null;
 
        $delete=$head;
 
        //Paso #2
        if($delete->val==$val){
            $head=$head->next;
            unset($delete);
            return $head; 
        }
 
 
        //Paso #3
        while($delete->next && $delete->next->val!=$val) $delete=$delete->next;
        if(!$delete->next) return $head;
 
        //Paso #4
        $aux=$delete->next;
        $delete->next=$aux->next;
        unset($aux);
 
        return $head;
 
    }
}
 
 
 
$head= null;
$solution = new Solution();
$head = $solution->insercion($head,5);
$head = $solution->insercion($head,4);
$head = $solution->insercion($head,3);
$head = $solution->insercion($head,2);
$head = $solution->insercion($head,1);
 
 
$solution->show($head);
 
$solution->busqueda($head,4);
$solution->busqueda($head,9);
 
 
$head =$solution->eliminar($head,3);
$head =$solution->eliminar($head,1);
 
$solution->show($head);