Motivación

Evitar la complejidad de pedir $O(n)$ posiciones de memoria (como necesitamos hacer con el Vector<T>).

Nos gustaría una implementación que solicite la memoria por demanda para que agregar un elemento sea $O(1)$.

Para lograr esto los elementos de la línea no pueden estar contiguos.

Nodos

Para poder relacionar elementos no contiguos entre sí vamos a usar nodos.

Los nodos son una estructura clásica de datos que alberga un dato y un puntero al siguiente elemento (también un nodo) de la lista.

Nodo es una estructura recursiva.

class Node {
	public: 
		Node* next;
		int data;
};

Linked List

Listas compuestas por nodos.

Vamos a implementar una lista de enteros primero, ya que aún no vimos Templates.

class LinkedList {
	public:
		int Length;
		Node* head;

		LinkedList();
		~LinkedList();
		void add(int data);
		void print();
};

LinkedList::LinkedList() 
	: length(0), head(NULL) {}
}

void LinkedList::add(int data) {
	Node* node = new Node();
// Guardamos el elemento a agregar en un nodo nuevo
	node -> data = data;
// Hacemos que el nuevo nodo apunte al
// comienzo de la lista
	node -> next = this -> head;
// Hacemos que el comienzo de la lista sea este nodo
	this -> head = node;
// Aumentamos la longitud en 1
	this -> length++;
}

LinkedList::~LinkedList() {
	Node<T>* temp = head;
// Creamos un nodo temp para iterar sobre la lista
	while (temp != NULL) {
		temp = temp -> next;
// Avanzo temp
		delete(head);
// Borro el heap que apunta a head 
// (la variable sigue existiendo porque está en el stack)
		head = temp;
// Actualizo head con la nueva posición de temp
	}
}