A lista doblemente enlazada Es una estructura de datos que consta de un conjunto de nodos donde cada nodo tiene tres campos: a campo de valor para almacenar los datos, un siguiente puntero para apuntar al siguiente nodo, y un puntero anterior para apuntar al nodo anterior. La ventaja de una lista doblemente enlazada sobre una lista simplemente enlazada es que permite un recorrido eficiente de la lista tanto hacia adelante como hacia atrás.
Sin embargo, una desventaja de una lista doblemente enlazada es que requiere más memoria que una lista simplemente enlazada, debido a la `anterior` punteros. En situaciones donde la memoria es limitada o costosa, puede ser necesario implementar una lista doblemente enlazada con memoria eficiente.
Una forma de implementar un lista doblemente enlazada con memoria eficiente es utilizar un único puntero que sirva como “puntero siguiente” y como “puntero anterior”. Esto se conoce como un lista enlazada XOR, donde cada nodo almacena el XOR de las direcciones de sus nodos anterior y siguiente. Para recorrer la lista, debe realizar un seguimiento de la dirección del nodo anterior, que se puede calcular utilizando el XOR del siguiente puntero del nodo actual y la dirección del nodo anterior.
A continuación se muestra un ejemplo de implementación de una lista doblemente enlazada con eficiencia de memoria utilizando el enfoque de lista enlazada XOR en C++:
#incluir
clase Nodo {
público:
Nodo (valor int): valor (valor), ambos (NULL) {}
valor entero;
Nodo* ambos; // XOR de las direcciones de nodo anterior y siguiente
};
clase XorLinkedList {
público:
XorLinkedList() : cabeza(NULL), cola(NULL) {}
agregar vacío (valor int) {
Nodo* nodo = nuevo Nodo(valor);
si (cabeza == NULL) {
cabeza = cola = nodo;
} demás {
nodo->ambos = cola;
cola->ambos = (Nodo*)((uintptr_t)cola->ambos ^ (uintptr_t)nodo);
cola = nodo;
}
}
int get(índice int) {
Nodo* anterior = NULL;
Nodo* curr = cabeza;
para (int i = 0; i < índice; i++) {
Nodo* siguiente = (Nodo*)((uintptr_t)prev ^ (uintptr_t)curr->both);
anterior = actual;
actual = siguiente;
}
devolver valor actual->;
}
privado:
Cabeza de nodo*;
Cola del nodo*;
};
En esta implementación, se define una clase Nodo para representar un nodo en la lista vinculada. Cada nodo tiene un campo de valor y un campo ambos que almacena el XOR de las direcciones de sus nodos anterior y siguiente.
El XorListaEnlazada Luego se define la clase para representar la lista vinculada en sí. Tiene un puntero de cabeza y cola para realizar un seguimiento del primer y último nodo de la lista, respectivamente.
El método add se utiliza para agregar un nuevo nodo al final de la lista. Si la lista está vacía, los punteros de cabeza y cola se establecen en el nuevo nodo. De lo contrario, el XOR del puntero de cola y la dirección del nodo anterior se almacenan en el campo ambos del nuevo nodo, y el XOR del puntero de cola y la dirección del nuevo nodo se almacenan en el campo ambos del nodo anterior. Finalmente, el puntero de cola se actualiza para que apunte al nuevo nodo.
El método get se utiliza para recuperar el valor en un índice específico de la lista. Utiliza un bucle para recorrer la lista, comenzando desde el nodo principal. En cada iteración, calcula la dirección del siguiente nodo utilizando el XOR de la dirección del nodo anterior y el campo ambos del nodo actual, y actualiza los punteros prev y curr en consecuencia. Una vez que alcanza el índice deseado, devuelve el valor del nodo actual.
Otra forma de implementar un lista doblemente enlazada con memoria eficiente es utilizar un buffer circular. Un búfer circular es una matriz que se trata como si fuera circular, lo que significa que el primer y el último elemento de la matriz se consideran adyacentes. Para implementar un búfer circular como una lista doblemente enlazada, puede utilizar dos punteros para realizar un seguimiento del principio y el final de la lista. Para agregar un elemento a la lista, lo inserta al final de la lista y actualiza el puntero de la cola. Para eliminar un elemento de la lista, lo elimina del encabezado de la lista y actualiza el puntero del encabezado. Este enfoque tiene la ventaja de requerir sólo una cantidad fija de memoria, pero puede no ser tan eficiente para listas grandes o inserciones y eliminaciones frecuentes.
A continuación se muestra un ejemplo de implementación de una lista doblemente enlazada con eficiencia de memoria utilizando el enfoque de búfer circular en C++:
#incluir
constanteint MAX_SIZE = 100; // tamaño máximo de la lista
clase CircularBuffer {
público:
CircularBuffer() : cabeza(0), cola(0), tamaño(0) {}
agregar vacío (valor int) {
si (tamaño == MAX_SIZE) {
// la lista está llena, sobrescribe el elemento más antiguo
buffer[head] = valor;
cabeza = (cabeza + 1) % MAX_SIZE;
} demás {
buffer[tail] = valor;
cola = (cola + 1) % MAX_SIZE;
tamaño++;
}
}
int get(índice int) {
if (índice < 0 || índice >= tamaño) {
// Índice fuera de los límites
devolver -1;
} demás {
int i = (cabeza + índice) % MAX_SIZE;
buffer de retorno[i];
}
}
privado:
búfer int[MAX_SIZE];
cabeza interna;
cola interna;
tamaño entero;
};
En esta implementación, se define una clase CircularBuffer para representar la lista doblemente enlazada. Utiliza una matriz para almacenar los elementos de la lista y realiza un seguimiento del principio, el final y el tamaño de la lista.
El método add se utiliza para agregar un nuevo elemento a la lista. Si la lista está llena (es decir, el tamaño es igual al tamaño máximo), el elemento más antiguo se sobrescribe con el nuevo valor y el puntero principal se actualiza para apuntar al siguiente elemento. De lo contrario, el nuevo valor se agrega al final de la lista y el puntero de cola y el tamaño se actualizan en consecuencia.
El método get se utiliza para recuperar el valor en un índice específico de la lista. Primero comprueba si el índice está fuera de límites y devuelve -1 si lo está. De lo contrario, calcula el índice del elemento en el búfer circular utilizando el puntero principal y el índice, y devuelve el valor en ese índice.
Tenga en cuenta que esta implementación tiene un tamaño máximo fijo, lo que puede ser una limitación en algunas aplicaciones. Sin embargo, consume mucha memoria y puede ser una buena opción si le preocupa el uso de la memoria.
Las listas doblemente enlazadas con memoria eficiente tienen ventajas y desventajas en comparación con las listas doblemente enlazadas estándar. Éstos son algunos de los principales:
Ventajas:
Uso de memoria reducido: Las listas doblemente enlazadas con memoria eficiente utilizan menos memoria que las listas doblemente enlazadas estándar al almacenar solo un puntero por nodo, en lugar de dos. Esto puede ser una ventaja significativa en aplicaciones donde el uso de la memoria es una preocupación, como sistemas integrados o dispositivos móviles.Localidad de caché mejorada: Debido a que las listas doblemente enlazadas con memoria eficiente almacenan nodos consecutivos en un bloque contiguo de memoria, pueden tener una mejor localidad de caché que las listas doblemente enlazadas estándar, que pueden tener nodos dispersos por toda la memoria. Esto puede conducir a tiempos de acceso más rápidos y un mejor rendimiento.Implementación simplificada: Las listas doblemente enlazadas con memoria eficiente pueden ser más sencillas de implementar que las listas doblemente enlazadas estándar, ya que requieren menos administración de memoria y manipulación de punteros.
Desventajas:
Funcionalidad limitada: Es posible que las listas doblemente enlazadas con memoria eficiente no admitan todas las operaciones que realizan las listas doblemente enlazadas estándar. Por ejemplo, puede resultar difícil insertar o eliminar nodos en el medio de la lista, ya que el enlace XOR de los nodos puede romperse si no se accede a los nodos en el orden correcto.Legibilidad reducida: Las listas doblemente enlazadas con memoria eficiente pueden ser más difíciles de leer y depurar que las listas doblemente enlazadas estándar, ya que la vinculación XOR de nodos puede dificultar el seguimiento de los vínculos entre nodos.Mayor complejidad: Aunque las listas doblemente enlazadas con memoria eficiente pueden ser más sencillas de implementar en algunos casos, también pueden requerir algoritmos más complejos para ciertas operaciones, como buscar u ordenar la lista.
En general, las listas doblemente enlazadas con memoria eficiente pueden ser una buena opción en aplicaciones donde el uso de la memoria es una preocupación y la funcionalidad limitada y la legibilidad reducida no son inconvenientes importantes. Sin embargo, en aplicaciones donde el rendimiento o la facilidad de implementación son más importantes, las listas doblemente enlazadas estándar pueden ser una mejor opción.
Feliz aprendizaje.!!