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);
Your code works perfectly fine! You just need to tweak your traversal() method because the while loop breaks before it gets a chance to log the last node.
You can try something like this:
traverse(){
let aux = this.first;
while (true) {
console.log(aux.value);
aux = aux.next;
if (aux == this.first) {
break;
}
}
}
I will expand an attribute (count)
constructor() {
...
this.count = 0;
}
Calculate it when insert is called
insert(value) {
...
this.count = this.count + 1;
}
If there is an extension removal method later, remember to calculate it
remove() {
...
this.count = this.count - 1;
}
And adjust the conditional expression of traverse,
replace while (aux.next != this.first) with for (let i = this.count; i > 0; i--)
I prefer trincot's answer, my answer is aimed at a small scope of code changes.
In practice I will design it with a similar structure(trincot's answer).
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();