Qué son y cómo usar LinkedList

Una LINKED LIST, o lista enlazada, es una colección de elementos donde cada uno de ellos está enlazado con otros elementos formando una secuencia.

Una LINKED LIST se compone de nodos enlazados entre sí. Cada uno de estos nodos se compone de un valor (el elemento) y enlace al siguiente nodo en la secuencia. El primer nodo de la lista se conoce como cabeza o head, mientras que el último nodo se denomina cola o tail.

Para recorrer una LINKED LIST, tenemos que ir “saltando” de nodo en nodo, a través de cada uno de los enlaces. No es posible acceder a través de un índice, por fuerza hay que recorrer toda la cadena.

Por su parte, la doble LinkedList es una versión mejorada de la linked list “sencilla”, donde cada nodo contiene un enlace al nodo siguiente y al anterior. Esto permite un recorrer de forma tanto hacia adelante como hacia atrás.

Las operaciones más comunes en una LINKED LIST son:

• Inserción: Permite agregar un nuevo nodo en cualquier posición de la lista.
• Eliminación: Permite eliminar un nodo de la lista, ajustando los enlaces adecuadamente.
• Acceso: Permite acceder a un elemento en una posición determinada de la lista.
• Búsqueda: Permite buscar un elemento específico en la lista recorriendo los nodos en orden.

Propiedades

Cuando usar una LinkedList

En primer lugar, salvo en ejercicios de clase, lo normal es que si tenéis que usar una LINKED LIST realmente siempre uséis una Double LinkedList. El sobre coste es muy pequeño, y proporciona la versatilidad de ir en ambas direcciones.

Por otro lado, el uso principal de un LINKED LIST (Double) es tener una colección en la que podemos añadir o eliminar rápidamente elementos en cualquier posición.

Una LINKED LIST (Double) es una serie de elementos formando “una cadeneta”. La gran ventaja que tiene es que en cualquier momento podemos “partir” la cadena, y meter añadir o quitar un elemento del medio.

Por contra, las LINKED LIST tienen la desventaja de no poder acceder por índice. Si queremos ir a la posición 237, tendremos que empezar por el primer elemento, e ir saltando hasta el nodo 237. Es decir, es muy lento el acceso aleatorio.

Ejemplo de LinkedList

La sintaxis para utilizar un LinkedList puede variar según el lenguaje de programación que se esté utilizando. A continuación, vamos a ver ejemplos en algunos lenguajes populares:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        LinkedList<int> linkedList = new LinkedList<int>();

        linkedList.AddLast(5);
        linkedList.AddLast(10);
        linkedList.AddLast(15);

        foreach (int item in linkedList)
        {
            Console.WriteLine(item);
        }
    }
}

:lang[C++]

#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> linkedList;

    linkedList.push_back(5);
    linkedList.push_back(10);
    linkedList.push_back(15);

    for (int item : linkedList)
    {
        cout << item << endl;
    }

    return 0;
}

class Node {
    constructor(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoubleLinkedList {
    constructor() {
        this.head = null;
    }

    addNode(data) {
        const newNode = new Node(data);
        if (this.head === null) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next !== null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.prev = current;
        }
    }
}

const list = new DoubleLinkedList();
list.addNode(1);
list.addNode(2);
list.addNode(3);

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoubleLinkedList:
    def __init__(self):
        self.head = None

    def addNode(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = new_node
            new_node.prev = current

# Uso de la Double Linked List
list = DoubleLinkedList()
list.addNode(1)
list.addNode(2)
list.addNode(3)

Funcionamiento interno Avanzado

Una LINKED LIST se compone de nodos. Cada uno de estos nodos dispone del elemento que contiene, y de una referencia al siguiente nodo.

Una LINKED LIST doblemente enlazada es similar a una LinkedList, pero cada nodo tiene una referencia tanto al nodo siguiente como al nodo anterior. Esto permite recorrer la lista en ambas direcciones, hacia adelante y hacia atrás.

Eficiencia

Una LINKED LIST es una estructura de datos enlazada donde cada nodo contiene un valor y una referencia al siguiente nodo.

La lectura de elementos en una LinkedList requiere recorrerlos secuencialmente, lo que tiene una complejidad de tiempo lineal O(n). La búsqueda en una LinkedList también requiere recorrerla secuencialmente, lo que tiene una complejidad de tiempo lineal O(n).

Sin embargo, la inserción y eliminación de elementos en una LinkedList son muy eficientes, ya que solo se requiere modificar los enlaces. Por lo que tiene una complejidad de tiempo constante O(1).