Basic Linked List Implementation in JavaScript

Question

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 class for 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:

1. I implemented a generalized traverse() function and made each operation call it with a "mode" parameter. I'm not sure about this implementation.

2. 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.

3. 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.

4. 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!

5. 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.

6. 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);

Answer 1

Here's an eyeball review I'll expand on later with a rewrite suggestion if I have time.

Generally, avoid swallowing errors or printing inside of methods that perform logic. Throw errors to the client of your code and let them log the result of the failure, retry the operation with different values, or take whatever other programmatic action they want. Doing I/O is noisy, not useful programmatically and can't be easily suppressed by the client. Pretend you're writing code for the JS standard library--it runs totally silently and you give full control over logging to the client.

Similarly, avoid console.log for tests. Use the builtin assert module, console.assert, or a real testing framework like Jest or Mocha with Chai which provide diffs, readability, scalability, reporting and standardized structure. Tests should be in a separate file/module or function from the rest of the code, and the main linked list module should export its class.

Going a step further, remove console.log from all of your code, except during development. Except for extremely rare cases, PRs and production code should never use it--it's noisy, slow, poses a security risk, and pollutes the code. Most serious codebases I've worked on ban it in CI.

Use class LinkedList syntax instead of function linkedList. Note the casing. Even if you are writing old school-style JS, use new when creating your instance instead of returning a bare object and using function as a closure.

Consider making Node a full-fledged class instead of an ad-hoc plain object.

Personally, I don't love getFoo, getBar, getBaz, getQuux everywhere. My rule for function naming is: if it's a getter, make it a noun without the get prefix. Otherwise, make it a verb. Maybe this is OK in Java, but I find it to be unaesthetic and nonstandard, and wouldn't suggest it in JS. More normal is to use getter and setter syntax, which let the caller access a property without a function call, but without sacrificing encapsulation.

Autoformat with Prettier and align with the JS community instead of inventing your own style.

Always use braces for blocks instead of relying on indentation. If you do use indentation, Prettier will make it a one-liner.

Avoid magic literals like 'toString'. Pass real callback functions rather than strings that are later used to determine which function to call.

aList.pop; is a no-op. Functions need to be called to have an effect: aList.pop().

Your tests should be far more comprehensive than the few cursory calls shown here. I haven't run your code, but there are likely other bugs in it. I suggest at least 20 or 30 non-overlapping tests that exercise all aspects of the class. Code slowly and test each method thoroughly, one at a time. Be paranoid and don't trust your code until it's been thoroughly tested.

This is particularly important if you're relying on a custom linked list implementation to build other abstractions on. If you rush into building a hash map on top of this without tests, when a subtle bug shows up in the hash (and it will!), how do you know the bug isn't with the linked list library?

Make sure functions are honest and transparent about what they do. checkIfSizeIs1 actually checks if the list size is 0, then mutates state without telling the caller.

Avoid bare booleans: if (stopConditionMet === true) { should be if (!stopConditionMet) {.

evaluateCondition(conditionObject, mode, currentIndex, currentValue) { is a confusing an unnecessary function. If you have more than two parameters, the standard is to use a configuration object pattern. Avoid condition1, condition2-type variables which are unnecessary code smell. Give them non-numeric names, or use a predicate function for arbitrary condition tests.

Always use ===, never ==, which coerces values to be equal that should never be, like 0 == false and "42" == 42.

Link lists arguably should not offer O(n) at/find/insertAt/removeAt operations. I know these are in many standard library implementations, but if you're ever actually using these, you're probably using the wrong data structure.

If random access is important, use an array which will almost certainly be way more performant than a hand-rolled linked list. Removing these footgun operations solves your traverse and evaluateCondition design problems because you can throw them out entirely. If you do need to keep these, generators, iterators and callback functions will solve your design problems without resorting to ifs and string parameters to control what sort of traversal occurs.

Does append really need to return the value the caller just appended? The caller already has the value and all calls to it ignore the return, so this feels like a sloppy contract.

Consider using TypeScript, JSDocs with annotations that describe your methods, arguments and return values. Avoid inline comments--they usually indicate the code needs to be clarified or broken up.

Never use recursion with linked lists. JS has a call stack that can handle only a few thousand recursive calls. Linear data structures that can't be longer than ~3k elements are practically useless.

Only use recursion for logarithmic data structures like balanced trees, or in languages that natively support tail recursion. Otherwise, use iteration. The code will be easier to read and write and will run faster, without using unnecessary space.

Always use all variables you define. Some of the variables in "tests" were never logged, like const at, const contains and const find. Use ESLint to pick up these mistakes.

Taking a step back, link lists are pointless data structures in JS. I'd wager arrays are better for pretty much 99.9% of real use cases. Feel free to provide a counterexample--I'd be genuinely curious to see one used in a real project. I understand this is an educational exercise, though, but worth keeping in mind.

Answer 2

Great job on making a reproducible example.

My first concern is that linkedList does not appear to be a clean abstraction. Let's consider the C++ class std::unordered_map, which has a similar approach to The Odin Project:

1. A bucket is a (doubly) linked list of key-value pairs.
2. A hash table stores an array of buckets (resized on rehashing), the number of buckets, and the total number of elements (inserted key-value pairs).

It makes use of three abstractions:

1. The (doubly) linked list needs traversal, data insertion (insert), and node deletion (erase).
2. The bucket needs insert to achieve update-or-insertion (upsert) by key (returning whether the linked list grew due to not finding a key), delete to achieve deletion-or-nothing (remove) by key (returning whether the linked list shrank due to finding a key), and traversal to achieve value access (access) by key (returning the value). For all of the above, it needs to find a node by key.
3. The hash table needs to hash keys to corresponding buckets for access and keep a running count of element sizes by observing the return values of upsert and remove. If the number of elements divided by the number of buckets exceeds the load factor, it needs to rehash appropriately.

The code above doesn't quite work with these layers (although all abstractions leak somewhat). The data structure resembles a linked list, but find should be for buckets and size should be counted by hash tables. I don't think tail is necessary - if anything, insertion at the front rather than the back would take better advantage of temporal locality (more recently inserted values are more likely to be accessed).

The repeated use of traverse (recursive) is confusing to me and I think it can be made much simpler. Here is my best attempt at the bucket level:

function bucket() { let head = null; // [key, value, next, prev] // returns the first node with a key or null function find(key) { let node = head; while (node != null) { if (node.key == key) return node; node = node.next; } return null; } // updates or inserts the key / value, // returning whether insertion was needed function upsert(key, value) { let node = find(key); // not found? insert at front if (node == null) { const new_node = { key: key, value: value, next: head, prev: null }; if (head != null) head.prev = new_node; head = new_node; return true; } node.value = value; return false; } // removes all nodes with the given key, // returning whether erase was needed function remove(key) { let node = find(key); // not found? do nothing if (node == null) return false; if (node.prev == null) head = head.next; else node.prev.next = node.next; if (node.next != null) node.next.prev = node.prev; return true; } // returns the value at key or other if not found function access(key, other) { let node = find(key); if (node == null) return other; return node.value; } // converts to string form function toString() { if (head == null) return '{}'; let result = '{\n'; let node = head; while (node != null) { result += ` ${node.key}: ${node.value}\n`; node = node.next; } return result + '}'; } return { upsert, remove, access, toString }; } 

And here are some tests:

const test_list = bucket(); let insert = test_list.upsert(2, 'x'); console.log('test_list[2] = "x"', insert); console.log(test_list.toString()); insert = test_list.upsert(5, 140); console.log('test_list[5] = 140', insert); console.log(test_list.toString()); insert = test_list.upsert(4, 'hi!'); console.log('test_list[4] = "hi"', insert); console.log(test_list.toString()); insert = test_list.upsert(4, 'hello!'); console.log('test_list[4] = "hello!"', insert); console.log(test_list.toString()); insert = test_list.upsert(5, test_list.access(5, 0) + 1); console.log('test_list[5] += 1', insert); console.log(test_list.toString()); insert = test_list.upsert(16, test_list.access(16, 0) + 1); console.log('test_list[16] += 1', insert); console.log(test_list.toString()); insert = test_list.upsert(80, test_list.access(80, "") + "a"); console.log('test_list[80] += "a"', insert); console.log(test_list.toString()); let shrink = test_list.remove("abc"); console.log('test_list.remove("abc")', shrink); console.log(test_list.toString()); shrink = test_list.remove(80); console.log('test_list.remove(80)', shrink); console.log(test_list.toString()); shrink = test_list.remove(4); console.log('test_list.remove(4)', shrink); console.log(test_list.toString()); shrink = test_list.remove(16); console.log('test_list.remove(16)', shrink); console.log(test_list.toString()); shrink = test_list.remove(2); console.log('test_list.remove(2)', shrink); console.log(test_list.toString()); shrink = test_list.remove(5); console.log('test_list.remove(5)', shrink); console.log(test_list.toString()); shrink = test_list.remove(5); console.log('test_list.remove(5)', shrink); console.log(test_list.toString()); 

And here is a version separating the linked list / bucket functionality:

function doubly_linked_list() { let head = null; // [data, next, prev] // gets the head function get_head() { return head; } // front-inserts a node with data function insert(data) { const new_node = { data: data, next: head, prev: null }; if (head != null) head.prev = new_node; head = new_node; } // erases a node (assumed to be valid) function erase(node) { if (node.prev == null) head = head.next; else node.prev.next = node.next; if (node.next != null) node.next.prev = node.prev; } return { get_head, insert, erase }; } function bucket() { const data_list = doubly_linked_list(); // returns the first node with a key or null function find(key) { let node = data_list.get_head(); while (node != null) { if (node.data.key == key) return node; node = node.next; } return null; } // updates or inserts the key / value, // returning whether insertion was needed function upsert(key, value) { let node = find(key); // not found? insert at front if (node == null) { data_list.insert({ key: key, value: value }); return true; } node.data.value = value; return false; } // removes all nodes with the given key, // returning whether erase was needed function remove(key) { let node = find(key); // not found? do nothing if (node == null) return false; data_list.erase(node); return true; } // returns the value at key or other if not found function access(key, other) { let node = find(key); if (node == null) return other; return node.data.value; } // converts to string form function toString() { const head = data_list.get_head(); if (head == null) return '{}'; let result = '{\n'; let node = head; while (node != null) { result += ` ${node.data.key}: ${node.data.value}\n`; node = node.next; } return result + '}'; } return { upsert, remove, access, toString }; } 

Hope this helps!