Encontrar corrupción en una lista vinculada

Question

Tuve una entrevista hoy para un puesto de desarrollador y me hicieron una pregunta técnica interesante que no sabía la respuesta. Lo preguntaré aquí para ver si alguien puede proporcionarme una solución para mi curiosidad. Es una pregunta de varias partes:

1) Se le proporciona una lista individualmente vinculada con 100 elementos (entero y un puntero al siguiente nodo), encuentre una manera de detectar si hay una ruptura o corrupción a mitad del enlace ¿lista? Puede hacer cualquier cosa con la lista vinculada. Tenga en cuenta que debe hacer esto en la lista ya que se está iterando y esto es una verificación antes de darse cuenta de que la lista tiene algún problema.

Suponiendo que la ruptura en la lista vinculada está en el 50º elemento, el entero o incluso el puntero al siguiente nodo (51º elemento) pueden estar apuntando a un valor basura que no es necesariamente una dirección no válida.

2) Tenga en cuenta que si hay una corrupción en la lista vinculada, ¿cómo minimizaría la pérdida de datos?

Answer 1

Para probar un entero "dañado", necesitaría saber cuál es el rango de valores válidos. De lo contrario, no hay forma de determinar que el valor en un entero dado (firmado) no es válido. Entonces, suponiendo que tienes una prueba de validez para el int, siempre verificas ese valor antes de iterar al siguiente elemento.

La prueba de un puntero dañado es más complicada; para empezar, lo que debe hacer es verificar el valor del puntero al siguiente elemento antes de intentar desviarlo y asegurarse de que sea una dirección de pila válida. Eso evitará una falla de segmentación. Lo siguiente es validar que lo que señala el puntero es, de hecho, un elemento de nodo de lista vinculado válido, ¿eso es un poco más complicado? Tal vez des-referenciar el puntero en una lista elemento clase/estructura, y probar la validez del int y el puntero "siguiente", si también son buenos, entonces puede estar bastante seguro de que el nodo anterior también era bueno.

En 2), habiendo descubierto un nodo dañado, [si el siguiente puntero está dañado] lo que debe hacer es establecer inmediatamente el "siguiente puntero" del nodo anterior como 'NULO', marcándolo como el final del lista, y registra tu error, etc.si la corrupción fue solo para el valor entero, pero no para el puntero del elemento "siguiente", entonces debe eliminar ese elemento de la lista y vincular los nodos anterior y siguiente juntos, ya que no es necesario descartar el resto de la lista ¡en ese caso!

Answer 2

Si en el momento del diseño sabe que la corrupción puede convertirse en un problema crítico, puede agregar un "valor mágico" como campo en la estructura de datos del nodo que le permite identificar si algunos datos son o no un nodo . O incluso para ejecutar la búsqueda de memoria de los nodos.

O duplique algo de información de enlace, es decir, almacene la dirección del nodo después del siguiente nodo en cada nodo, de forma que pueda recuperar si un enlace está roto.

El único problema que veo es que debe evitar las fallas de segmentación.

Answer 3

Dado que se conoce la cantidad de elementos (100), el 100º nodo debe contener un puntero nulo. Si lo hace, la lista con buena probabilidad es válida (esto no se puede garantizar, por ejemplo, si el nodo 99 está dañado y apunta a alguna ubicación de memoria con todos los ceros). De lo contrario, hay algún problema (esto puede devolverse como un hecho).

UPD: También, podría ser posible, una en cada paso, ver algunas estructuras delete usaría si se les da el puntero, pero ya que el uso delete sí mismo no es seguro en cualquier sentido, esto va a ser puesta en práctica -específico.

Answer 4

Para la primera parte: sobrecargue el nuevo operador. Cuando se asigna un nuevo nodo, asigne un espacio adicional antes y después del nodo y coloque allí algunos valores conocidos. En el recorrido, cada nodo se puede verificar si está entre los valores conocidos.

Answer 5

Si puede hacer algo en la lista vinculada, lo que puede hacer es calcular la suma de comprobación de cada elemento y almacenarla en el elemento en sí. De esta forma, podrá detectar la corrupción incluso si se trata de un error de bit único en el elemento.

Para minimizar la pérdida de datos, quizás pueda considerar el almacenamiento de nextPtr en el elemento anterior, de esa manera si su elemento actual está dañado, siempre puede encontrar la ubicación del siguiente elemento del anterior.

Answer 6

Esta es una pregunta fácil, y hay varias respuestas posibles. Cada uno intercambia robustez con eficiencia. Dado que una mayor solidez es un requisito previo de la pregunta, hay soluciones disponibles que sacrifican tanto el tiempo (listar la velocidad de cruce, así como la velocidad de inserción y la velocidad de eliminación de nodos) o alternativamente el espacio (información adicional almacenada con cada nodo). Ahora se ha indicado el problema de que esta es una lista fija de longitud 100, en cuyo caso la estructura de datos de una lista vinculada es la más inapropiada. ¿Por qué no hacer el rompecabezas un poco más desafiante y decir que el tamaño de la lista no se conoce a priori?