Clarification of Intent
- Recursion here is used on purpose for practice - note that iteration is preferred in this case (I'll be more clear about where my intentions are!)
- Factory function was also used in place of
classfor practice - The project is educational, for the purposes of learning the ins and outs of Linked Lists
This is most likely used in my next project HashMap (as a part of The Odin Project https://www.theodinproject.com/lessons/javascript-hashmap-data-structure#growth-of-a-hash-table ) , and I wanted to ensure that the code is good.
Here are some of my concerns which I'd love to get some feedback on:
I implemented a generalized traverse() function and made each operation call it with a "mode" parameter. I'm not sure about this implementation.
I struggled to implement a generalized evaluateCondition function. Part of the evaluateCondition parameter is set indirectly by using "mode" + switch statements (condition2). The other part would be set by passing a conditionObject right when any linkedList operation calls traverse(). The challenge was that condition2 needed to be either value/index, which would change only within traverse(). I am not sure if my solution was okay. Concerned about passing too many parameters into traverse() as it is recursive.
is it good practice to track [head,tail,size] as variables inside my module? I'd decided the tradeoff is worth it, since the alternative would be to re-calculate all 3 using traverse() every time I need any one of these values.
I had some concerns about the space complexity. Articles such as this one https://www.geeksforgeeks.org/time-and-space-complexity-of-linked-list/ would claim O(1), but I have a feeling this is assuming a non-recursive solution. I'd imagine that height/depth would basically be the length of the linked list. So max space would be O(n), with a coefficient that correlates to the number and space complexity of the parameters being passed. This made me try and use the minimal # of arguments for traverse(). If anyone could clarify what the space complexity will be, and if it is a genuine concern in this case, that would be helpful!
I found that every time I made any changes / added new operations, I'd also have to alter traverse() and this bothered me - it made me think coupling was too tight.
Any other criticisms welcome!
function linkedList() {
let head;
let tail;
let size = 0;
function getTail() {
// MAYBE: I could traverse instead of storing tail in memory
return tail;
}
function getSize() {
return size;
}
function getHead() {
return head;
}
function checkIfSizeIs1(newNodeReference) {
if (getSize() === 0) {
head = newNodeReference;
tail = newNodeReference;
return true;
}
return false;
}
function traverse(
conditionObject,
mode = null,
currentNode = head,
currentIndex = 0,
resultString = '',
) {
// TODO: calculate big O for time & space
// MAYBE: use loop instead
let stopConditionMet = false;
const currentValue = currentNode.value;
stopConditionMet = evaluateCondition(conditionObject, mode, currentIndex, currentValue);
// BASE CASE
if (stopConditionMet === true) {
if (mode === 'find') {
return currentIndex;
}
if (mode === 'toString') {
return `${resultString}( ${currentNode.value} ) -> ` + ' null';
// return resultString + ' null';
}
return currentNode;
}
if (currentNode === tail) return currentNode;
// RECURSIVE CASE
resultString = resultString.concat(`( ${currentNode.value} )`, '->');
currentNode = currentNode.next;
return traverse(conditionObject, mode, currentNode, currentIndex + 1, resultString);
}
function evaluateCondition(conditionObject, mode, currentIndex, currentValue) {
// MAYBE: instead of using mode, assign "this" to static variable (which poiints to the caller function)
let {
condition1,
condition2
} = conditionObject;
let meetsCondition = false;
switch (mode) {
case 'at':
case 'pop':
case 'toString':
case 'insertAt':
case 'removeAt':
{
condition2 = currentIndex;
break;
}
case 'contains':
case 'find':
{
condition2 = currentValue;
break;
}
default:
}
meetsCondition = condition1 === condition2;
return meetsCondition;
}
function at(targetIndex) {
try {
isIndexValid(targetIndex);
const result = traverse({
condition1: targetIndex
}, 'at');
return result;
} catch (error) {
console.error(error);
}
}
function pop() {
try {
if (size <= 0) throw new Error('Cannot pop, size is 0');
const last = { ...tail
};
tail.value = null;
const secondToLast = traverse({
condition1: size - 2
}, 'pop'); // find 2nd to the last element
secondToLast.next = null;
// set new tail value
tail = secondToLast;
size -= 1;
return last;
} catch (error) {
console.error(error);
}
}
function contains(value) {
const currentNode = traverse({
condition1: value
}, 'contains');
return currentNode.value === value;
}
function find(value) {
const index = traverse({
condition1: value
}, 'find');
return Number.isInteger(index) ? index : undefined; // traverse will return currentNode (tail) if nothing is found. If found, it will return an index,
}
function toString() {
return traverse({
condition1: size - 1
}, 'toString');
}
function append(value) {
const newNodeReference = node(value);
checkIfSizeIs1(newNodeReference);
getTail().next = newNodeReference;
tail = newNodeReference;
size++;
return newNodeReference;
}
function prepend(value) {
const newNodeReference = node(value, head);
checkIfSizeIs1(newNodeReference);
head = newNodeReference;
size++;
return newNodeReference;
}
function insertAt(value, index) {
try {
isIndexValid(index);
if (index === 0) {
prepend(value);
return;
}
if (index === size - 1) {
append(value);
return;
}
const insertionPoint = traverse({
condition1: index
}, 'insertAt');
const newNode = node(value, insertionPoint.next);
insertionPoint.next = newNode;
size += 1;
return newNode;
} catch (error) {
console.error(error);
}
}
function removeAt(index) {
try {
isIndexValid(index);
if (index === 0) {
aList.pop;
return;
}
const nodeBeforeTarget = traverse({
condition1: index - 1
}, 'removeAt');
const removalTarget = { ...nodeBeforeTarget.next
};
nodeBeforeTarget.next = nodeBeforeTarget.next.next;
if (index === size - 1) {
tail = nodeBeforeTarget;
console.log('NEW tail:', tail);
}
size -= 1;
return removalTarget;
} catch (error) {
console.error(error);
}
}
function isIndexValid(targetIndex) {
if (targetIndex + 1 > size) {
throw new Error('Invalid Index');
}
}
return {
append,
prepend,
getHead,
getSize,
getTail,
at,
pop,
contains,
find,
toString,
insertAt,
removeAt,
};
}
// MAYBE: use undefined instead of null
function node(value = null, next = null) {
return {
value,
next
};
}
//TESTS
const aList = linkedList();
aList.append(2);
aList.append(5);
aList.append(4);
aList.prepend(10);
aList.prepend(7);
aList.prepend(8);
const at = aList.at(4);
const contains = aList.contains(8);
const find = aList.find(1000);
const toString = aList.toString();
console.log('toString:', toString);
const [head, tail, size] = [aList.getHead(), aList.getTail(), aList.getSize()];
console.log('head:', head);
console.log('tail:', tail);
console.log('size:', size);
