I have a circular singly linked list code:
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();
And when I tried to print the list, I just get in console 3 names:
Bob
Adam
John
And as you can see I push 4 names in my linked list. I tried to print the values of my list in the traverse
method, but It didn´t work because I don´t get in console:
Bob
Adam
John
David
The loop stops one step too early. This is a good case for a do ... while
loop. You should also protect it from failing when the list is empty
traverse() {
if (this.empty()) return; // <---
let aux = this.first;
do {
console.log(aux.value);
aux = aux.next;
} while (aux != this.first);
}
Some other remarks on your code:
As in a non-empty circular list it is always true that the head follows after the tail, it is actually not needed to maintain a first
reference. Just keep a last
reference, knowing that you can always get the head of the list via last.next
.
console.log
should not be used in a class method for anything else than debugging. Give your traverse
method more flexibility by making it a generator. That way you leave the decision of what to do with the values to the caller of that method.
As in a circular list a node should never have a next
property with a null
value, don't assign null
in the Node
constructor. Instead give it a self-reference.
Name the empty
method isEmpty
as it more clearly indicates that this will not empty the list, but will return whether it is empty.
Fix a typo in the class name: 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);