LinkedList seems to have redundant code after refactoring

[pmario]

This discussion is related to PR: #8213

@flibbles -- There have been some issues lately, where ListLinks throws an RSOD for incoming undefined values, because of 3rd-party JS bugs.

So I did have a closer look at the code. I do like the "debuggability" of used list-structure.

---

There are several points I do want to ask:

Question 1: https://github.com/flibbles/TiddlyWiki5/blob/master/editions/test/tiddlers/tests/test-linked-list.js the comment says

[...] If you want to add new functionality, like 'shift' or 'unshift', you'll
probably need to deal with the fact that Linked List will insert undefined
as a first entry into an item's 'prev' array when it's at the front of
the list, [...]

I think that's not true anymore. I'm not able to see an "undefined" value in the prev structure. I used this code:

Can you check the test comments, if they are still true?

var results = new $tw.utils.LinkedList();
results.push("xx");
results

[pmario]

Question 2: There seems to be some array handling in internal structures eg_ _removeOne, _** . But the eg: prev.map only stores strings and no arrays.

I'm not 100% sure but for me it looks like, that there is some redundant code which can / should be removed. --

[flibbles]

I think that's not true anymore. I'm not able to see an "undefined" value in the prev structure. I used this code:

You're correct. That comment was an attempt to unobfuscate how the LinkedList works before I did a refactor and encapsulated the managing of the list's ends with the LLMap type. I can make a PR to remove that comment.

There seems to be some array handling in internal structures eg_ _removeOne, _** . But the eg: prev.map only stores strings and no arrays.

It's been a while since I've dealt with the LinkedList, but prev.map can store arrays. Try this:

var results = new $tw.utils.LinkedList();
results.push("cats", "dogs", "cats");
results

next.get(null) === "cats" Meaning the value that comes after the null ptr (i.e. the front of the list) points to "cats".
next.get("cats") === ["dogs", null] Meaning the value that comes after "cats" is "dogs" the first time, and the back of the list the second time.
next.get("dogs") === "cats" Meaning the value that comes after "dogs" is cats, but you'll only realize it's referring to the second instance of cats if you're iterating through the list and keeping track. LinkList is no good for random access.

So it can have arrays, but only when duplicate values are involved. It might have made a cleaner implementation if I had it only store arrays, but that had lists with thousands of unique values storing thousands of arrays of length 1, which was a noticeable performance hit. And since big lists of unique values makes 95%+ of the use cases, I opted for that.

I also opted for this strange system after first trying a traditional linked list (where each entry has a data object with its own prev and next), because that ended up making a hecking mess of garbage collection and slowed things way down. (Not as much as $tw.utils.pushTop, but enough that I changed to the current system).

Does this create a LinkedList that scales beautifully once thousands of entries are involved? Yes.
Does it create something that's a total chore to debug? Yes.
If it's causing you trouble, it might be worth our time to create a "debug" LinkedList which is simply just an array under the hood. It'd only be about 10 lines of code, and it could be swapped in with a flag perhaps.

[pmario]

Thanks for the information. I think it makes sense now.

If it's causing you trouble, it might be worth our time to create a "debug" LinkedList which is simply just an array under the hood. It'd only be about 10 lines of code, and it could be swapped in with a flag perhaps.

I think it's not needed to change it. I just could not create an internal array. But your explanation makes sense.

I think using a map to create a linked list for string values is a clever solution. I did read the whole "history" of all the PRs. So I knew about the performance and memory improvements, and why it looks as it looks now.

I did create a new issue #8216, which describes the RSOD problem, which for me seems to be unavoidable atm.

[linonetwo]

Why use

var results = new $tw.utils.LinkedList();

instead of

var results = [];

I was always using array in my plugins, but I find core filters are using $tw.utils.LinkedList(), what is the difference?

[pmario]

I was always using array in my plugins, but I find core filters are using $tw.utils.LinkedList(), what is the difference?

Performance. See the initial PR: #5206 and some optimizations: #6056 especially for .pushTop()

[linonetwo]

This is good, I will all use this.