LinkedList AddFirst / Last / AddBefore / After returning void

[Ralf71]

I noticed the methods mentioned above do return void instead of the newly created LinkedListNode. I am to "new" to say this is intended and by design, or simply forgotten. I am also to new to change this myself (but I am happy to try and commit back if wanted!)

Thanks for the project so far, looks very very well!

[electricessence]

In this library there are 2 different LinkedLists... One is an unsafe version the other is a protected one.

Unsafe: https://github.com/electricessence/TypeScript.NET/blob/master/source/System/Collections/LinkedNodeList.ts Protected: https://github.com/electricessence/TypeScript.NET/blob/master/source/System/Collections/LinkedList.ts

The LinkedNodeList is unsafe but lower memory and better performance for those who know what they are doing and won't make mistakes like overwriting a node's prev/next references. It's basically a very classical JS linked list. But because JS doesn't have any real protection, another more public version of a LinkedList is needed. One that could be offered to a consumer of the code without worrying if they would arbitrarily break it.

The LinkedList is protected in that it generates public 'wrappers' when requested for the internal nodes in order to: 1) prevent silly mistakes. 2) extend functionality.

These public 'nodes' are not automatically created. The internal nodes are shielded from contact with the user. If a node is explicitly requested by a user, then the LinkedList generates a LinkedListNode for the user to interact with but it doesn't expose the internal node directly to the user to prevent the LinkedList from arbitrarily being broken.

Not returning a LinkedListNode from addLast or any method as such, will prevent the generation of an additional object and therefore limiting the memory overhead. This way, the consumer is effectively forced to consider the impact of what they are doing.

That said, if it was desirable to expose an addLast/addFirst method that does return the node, then we could definitely do that. It could even be an overload.

[electricessence]

Would love feedback. Let me know if that answers your question, or if you feel it best to extend the LinkedList version. I suggest if you are only using the LinkedList internally (not exposing it to a consumer), then just use LinkedNodeList instead.

[Ralf71]

I'll try to give my opinion on this since you invited me for feedback in your other mail - please be aware that I am just hours old in typescript experience. For .NET, I am commercially developing since 1.0, so at least there I hope I know what I am talking about.

 

Also, I spend just a couple of minutes with this wonderful pack of functions, so I will have not understood most (or any?) of it yet.

 

For some reason, I expected I could just use them 1:1 like C#, but a tiny bit of work needs to be done (which is fine!). I just did not really think what to expect from the port, and settled my mind on "it must be exactly the same".

 

 

Ok, here we go:

1) I did not notice the separation into two type of lists myself, this was a bit unexpected but it makes sense the way you explain

2) For the unsafe version, can't the setters for last / next just be private to make them safe? I do not know if typescript can do public getters and private setters.

3) If 2) would be possible, would both lists still needed? I think not. However, if it would be so easy, you would not have done it the way you did!

 

I think, to duplicate the behaviour of the .NET Linked List, I would create the node myself, and add it to the appropriate place (thereby holding a reference for further addition at this spot) without having it gotten back through the add call!

 

 

The following is just something I noticed but not really a problem - it is just different for the .NET class. Of course these methods can exist on the class, the just look "out of place" to me

4) The add method (without any indication to where to add) seems not necessary, with the other options available. Isn't this "AddLast", if not otherwise specified?

5) Access through index number seems wrong in a double linked list. Of course this is possible, but it invites thinking of index numbers. This would be an O(n)-Access, I think?

 

 

So, TL/DR : There is no need to change anything. I am totally happy with this excellent piece of code you provided, I am totally confident it will do all I need it to for my little project, and thanks for taking the time to respond!

 

All the best

Thanks again!

Ralf

 

Gesendet: Mittwoch, 10. Mai 2017 um 23:39 Uhr Von: electricessence notifications@github.com An: "electricessence/TypeScript.NET" TypeScript.NET@noreply.github.com Cc: Ralf71 ralf.hermanns@gmx.de, Author author@noreply.github.com Betreff: Re: [electricessence/TypeScript.NET] LinkedList AddFirst / Last / AddBefore / After returning void (#62)

In this library there are 2 different LinkedLists... One is an unsafe version the other is a protected one.

Unsafe: https://github.com/electricessence/TypeScript.NET/blob/master/source/System/Collections/LinkedNodeList.ts Protected: https://github.com/electricessence/TypeScript.NET/blob/master/source/System/Collections/LinkedList.ts

The LinkedNodeList is unsafe but lower memory and better performance for those who know what they are doing and won't make mistakes like overwriting a node's prev/next references.

The LinkedList is protected in that it generates public 'wrappers' when requested for the internal nodes in order to:

prevent silly mistakes.
extend functionality.

These public 'nodes' are not automatically created. The internal nodes are shielded from contact with the user. If a node is explicitly requested by a user, then the LinkedList generates a LinkedListNode for the user to interact with but it doesn't expose the internal node directly to the user to prevent the LinkedList from arbitrarily being broken.

Not returning a LinkedListNode from addLast or any method as such, will prevent the generation of an additional object and therefore limiting the memory overhead.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.

 

[electricessence]

I definitely get where you're coming from. The original intent was (and for the most part still is) to maintain parity with the .NET Framework. For more detail about the method to my madness, I'd suggest reading the readme in its entirety.

2) For the unsafe version, can't the setters for last / next just be private to make them safe? I do not know if typescript can do public getters and private setters.

The thing you have to keep in mind here:

1. TypeScript is JavaScript in the end. And JavaScript isn't C#.
2. JavaScript code is public unless you use scope to hide references which can have the effect of bloating memory since private scope is difficult to tie back to prototype without again exposing your code as public.
3. JavaScript doesn't conform the way C# does and as I mentioned before, I'm coding for things that reflect the underlying intent, but simply can't be done in the same way. In the C# LinkedList, you don't have to worry at all about destroying the underlying chain because it's properly protected. You don't have to worry about performance because you're not producing protected wrappers.

Consumers of this library can be and are commonly JavaScript coders. So it's possible to consume the lib and use the code without TypeScript. Maybe only as a 3rd/4th party, but it is possible and I don't want to produce code that is inherently fragile. One of the great things about the .NET Framework is that it is so robust and exception friendly. JavaScript is only now getting into the practice of fail fast and fail early where common practice used to simply be 'fail silent'.

And also consider that LinkedList.ts does use LinkedNodeList.ts under the hood.

addLast or addFirst, only requires calling .last or .first after that to get those references and is only an O1 operation which is pretty much exactly what would need to happen under the hood.

In the end. I get what you're saying. It has been an evolution writing this because if I did expose that same API, it would be producing 2x the amount of instances than C# would for the same effect. Especially when calling .addLast is so common.

JavaScript is super optimized to use JavaScript Arrays. And it will be for the most part difficult to find an instance where a JS Array does not out perform the simplest unprotected linked list. But, there is the edge case of insertion and deletion that a linked list will mostly outperform.

Here's a video of my first attempt of a LinkedList (before I created the unsafe LinkedNodeList): https://www.youtube.com/watch?v=73lqzno-BVE

Here's a video I did on JS Performance with LinkedList vs Array: https://www.youtube.com/watch?v=rgY03jwhtoY

I could definitely an overload that allows for this that won't break the existing API and comes with a caveat for people to read. Lemme look into it. I do understand the value.

[electricessence]

Oh and BTW, if you are looking for exact parity with .NET, I'd check out JSIL.

[electricessence]

Ok can you give me an actual use case where you are calling .addLast(value) but need the node after? Honestly I'm more inclined to return this instead of void because then it adds more value allowing for chained statements like in an expressive language. Simliar to how LINQ works.

So instead of:

list.addLast(value); // If a user doesn't care about getting actual node, there isn't a protected wrapper generated here.
var node = list.last;

You can have:

var node = list.addLast(value).last;

This example not only does not break the existing API but does not degrade performance and allows for statement chaining.

[electricessence]

This is the result: https://github.com/electricessence/TypeScript.NET/commit/59e28050b3c13fc37456cbd7aaaf5c3a9f3a0b87

I think this is the right way to go. It's a broader change that affects all collections in a positive way and doesn't go against what I was originally trying to do.

In your case, you'll just have to use the chaining to your advantage going forward instead of getting back the actual node right away.

[electricessence]

Updated release in NPM to 4.9.1

[electricessence]

Gonna go ahead and close but feel free to comment more.