Tengo un código de lista circular de un solo enlace:
class Node{ constructor(value){ this.value = value; this.next = null; } } class LinkdeList{ constructor(){ this.first = null; this.last = null; } empty(){ return this.first === null } insert(value){ let newest = new Node(value); if (this.empty()) { this.first = this.last = newest; this.last.next = this.first; }else{ newest.next = this.first; this.first = newest; this.last.next = this.first; } } traverse(){ let aux = this.first; while (aux.next != this.first) { console.log(aux.value); aux = aux.next; } } } let linked = new LinkdeList(); linked.insert("David"); linked.insert("John"); linked.insert("Adam") linked.insert("Bob"); linked.traverse();Y cuando traté de imprimir la lista, acabo de obtener en la consola 3 nombres:
Bob Adam John Y como puede ver, empujo 4 nombres en mi lista enlazada. Intenté imprimir los valores de mi lista en el método traverse , pero no funcionó porque no entro en la consola:
Bob Adam John DavidEl bucle se detiene un paso demasiado pronto. Este es un buen caso para un bucle do ... while while. También debe protegerlo para que no falle cuando la lista está vacía.
traverse() { if (this.empty()) return; // <--- let aux = this.first; do { console.log(aux.value); aux = aux.next; } while (aux != this.first); }Algunas otras observaciones sobre su código:
Como en una lista circular no vacía siempre es cierto que la cabeza sigue a la cola, en realidad no es necesario mantener una first referencia. Solo mantenga una last referencia, sabiendo que siempre puede obtener el encabezado de la lista a través de last.next .
console.log no debe usarse en un método de clase para otra cosa que no sea la depuración. Dé más flexibilidad a su método traverse convirtiéndolo en un generador. De esa manera, deja la decisión de qué hacer con los valores a la persona que llama a ese método.
Como en una lista circular, un nodo nunca debe tener una propiedad next con un valor null , no asigne null en el constructor de Node . En su lugar, dale una autorreferencia.
Nombre el método empty isEmpty ya que indica más claramente que esto no vaciará la lista, sino que devolverá si está vacía.
Corregir un error tipográfico en el nombre de la clase: LinkedList
class Node { constructor(value) { this.value = value; this.next = this; // self-reference } } class LinkedList { constructor() { this.last = null; // No need for a `first` } isEmpty() { return this.last === null; } insert(value) { const newest = new Node(value); if (!this.isEmpty()) { newest.next = this.last.next; this.last.next = newest; } this.last = newest; } *traverse() { // Generator if (this.isEmpty()) return; // Guard let aux = this.last; do { aux = aux.next; yield aux.value; // Don't print. Yield instead. } while (aux != this.last); } } const linked = new LinkedList(); linked.insert("David"); linked.insert("John"); linked.insert("Adam") linked.insert("Bob"); // Caller of traverse can decide what to do: we want to print: for (const name of linked.traverse()) console.log(name);¡Tu código funciona perfectamente bien! Solo necesita modificar su método traversal() porque el ciclo while se rompe antes de que tenga la oportunidad de registrar el último nodo.
Puedes intentar algo como esto:
traverse(){ let aux = this.first; while (true) { console.log(aux.value); aux = aux.next; if (aux == this.first) { break; } } }Expandiré un atributo ( count )
constructor() { ... this.count = 0; }Calcularlo cuando se llama insert
insert(value) { ... this.count = this.count + 1; }Si hay un método de eliminación de extensión más adelante, recuerde calcularlo
remove() { ... this.count = this.count - 1; }Y ajustar la expresión condicional de poligonal,
reemplace while (aux.next != this.first) con for (let i = this.count; i > 0; i--)
Prefiero la respuesta de Trincot, mi respuesta está dirigida a un pequeño alcance de los cambios de código.
En la práctica lo diseñaré con una estructura similar (respuesta de trincot).
class Node { constructor(value) { this.value = value; this.next = null; } } class LinkdeList { constructor() { this.count = 0; this.first = null; this.last = null; } empty() { return this.first === null } insert(value) { let newest = new Node(value); if (this.empty()) { this.first = this.last = newest; this.last.next = this.first; } else { newest.next = this.first; this.first = newest; this.last.next = this.first; } this.count = this.count + 1; } traverse() { let aux = this.first; for (let i = this.count; i > 0; i--) { console.log(aux.value); aux = aux.next; } } } let linked = new LinkdeList(); linked.insert("David"); linked.insert("John"); linked.insert("Adam") linked.insert("Bob"); linked.traverse();