When I change values of front and back inside of frontAndBackExist function, the changes won't be reflected outside of frontAndBackExist function. Thus when I call isEmpty function after adding and removing nodes, it returns false even though there aren't any nodes left. Is this because front and back are primitive values?
type DequeNode = {
value: any;
prev?: DequeNode;
next?: DequeNode;
};
type FrontBackTypes = DequeNode | undefined;
function Deque() {
let front: FrontBackTypes = undefined;
let back: FrontBackTypes = undefined;
let cnt = 0;
function addFront(value: any) {
if (!front) {
front = back = { value };
cnt ;
return null;
}
cnt ; // a new node just pushed!
const tempFront = front;
front = { value, prev: tempFront };
tempFront.next = front;
return;
}
function removeFront() {
if (!front) {
return null;
}
const value = peekFront();
if (frontAndBackExist(front, back)) {
front = undefined;
back = undefined;
cnt--;
return value;
}
cnt--;
front = front.prev;
delete front!.next;
return value;
}
function peekFront() {
return front?.value;
}
function addBack(value: any) {
if (!front) {
const backVal = { value };
front = backVal;
back = backVal;
cnt ;
return null;
}
cnt ;
const tempBack = back;
back = { value, next: tempBack };
tempBack!.prev = back;
return;
}
function removeBack() {
if (!back) {
return null;
}
const value = peekBack();
if (frontAndBackExist(front, back)) {
front = undefined;
back = undefined;
cnt--;
return value;
}
cnt--;
back = back.next;
delete back!.prev;
return value;
}
function peekBack() {
return back?.value;
}
function size() {
return cnt;
}
function isEmpty() {
return cnt === 0;
}
function clear() {
front = undefined;
back = undefined;
cnt = 0;
}
function frontAndBackExist(front: FrontBackTypes, back: FrontBackTypes) {
return front === back;
// if (front === back) {
// // if you change front and back value here, it won't be reflected outside of this function. thus the last isEmpty call returns false even though there is no node in deque.
// front = undefined;
// back = undefined;
// return true;
// } else {
// return false;
// }
}
return {
addFront,
removeFront,
peekFront,
addBack,
removeBack,
peekBack,
size,
isEmpty,
clear,
};
}
const deque = Deque();
console.log(deque.peekFront()); // undefined
console.log(deque.isEmpty(), "return if deque is empty or not");
console.log(deque.size(), "return length of deque");
deque.addFront(1);
console.log(deque.peekBack()); // 1
deque.addFront(2);
console.log(deque.size(), "return length of deque");
deque.clear();
console.log(deque.size(), "return length of deque");
console.log(deque.removeBack()); // 1
console.log(deque.isEmpty(), "return if deque is empty or not");
deque.addFront(3);
deque.addFront(4);
console.log(deque.size(), "return length of deque");
console.log(deque.size());
console.log(deque.peekBack()); // 2
deque.addBack(5);
deque.addBack(6);
console.log(deque.peekBack()); // 6
console.log(deque.removeFront()); // 4
console.log(deque.removeFront()); // 3
console.log(deque.removeFront()); // 2
console.log(deque.size(), "return length of deque");
console.log(deque.removeFront()); // 5
console.log(deque.isEmpty(), "return if deque is empty or not");
console.log(deque.removeFront()); // 6
console.log(deque.isEmpty(), "return if deque is empty or not");
console.log(deque.removeFront()); // undefined
console.log(deque.isEmpty(), "return if deque is empty or not");
Change front and back values inside helper function but those changes won't be reflected outside of the helper function.
CodePudding user response：
The problem with code like
function frontAndBackExist(front: FrontBackTypes, back: FrontBackTypes) {
if (front === back) {
front = undefined;
back = undefined;
return true;
} else {
return false;
}
}
is that front and back are parameters to the function, and are thus local variables inside the function body. So these variables only exist in the function scope.
When you assign front = undefined or back = undefined, all you are doing is assigning new values to these local variables, inside the function. It has no effect on whatever values were passed in as arguments to the function. JavaScript does not evaluate function calls by passing references to its arguments.
And the fact that you had some variables in an outer scope named front and back doesn't affect things; your function parameters are merely shadowing the same-named variables (see What is "Shadow Identifier Declaration" in JavaScript?) and therefore preventing your access of them inside the function.
JavaScript evaluates function calls by sharing, which is essentially the same as copying the value of the argument to the parameter, but with the wrinkle that objects are essentially references. When you call a function with a primitive argument, you are getting a copy of a primitive value. But when you call a function with an object as its argument, you are getting a copy of the object reference. So while reassigning the parameter's value has no external effects:
function foo(fb: FrontBackTypes) {
fb = { value: 1 };
}
const x = { value: 0 };
console.log(x.value) // 0
foo(x);
console.log(x.value) // 0, unchanged
you can have external effects if you don't reassign the parameter but instead act on its members:
function foo(fb: FrontBackTypes) {
if (fb) {
fb.value = 1;
}
}
const x = { value: 0 };
console.log(x.value) // 0
foo(x);
console.log(x.value) // 1, changed
So, one way you could fix your code is to refactor so front and back are members of an object and then pass that object as a function parameter. But this isn't how I'd recommend proceeding.
Instead, I'd suggest making frontAndBackExist() a closure with no parameters. You can access the external front and back variables inside such a closure because they were defined in an outer scope. That is, just stop shadowing front and back:
function frontAndBackExist() {
if (front === back) {
front = undefined;
back = undefined;
return true;
} else {
return false;
}
}
Now in the rest of your code, just call frontAndBackExist() with no arguments (and you don't have to write front = undefined; back = undefined; out there either):
function removeFront() {
if (!front) {
return null;
}
const value = peekFront();
if (frontAndBackExist()) {
cnt--;
return value;
}
cnt--;
front = front.prev;
delete front!.next;
return value;
}