In today's episode of Typescript 101, we continue talking about data structures and their implementation in Typescript. Our today's patient is the ...
For further actions, you may consider blocking this person and/or reporting abuse
Hi Gleb, nice and clear article :)
Could you elaborate on "Recursive functions are a great substitute of while loops for the tasks like traversing when we don't know the size of the list before we start iterating."?
I don't see what prior knowledge of the list size has to do with substituting while loop for a recursive call.
Traverse method could be easily implemented with while loop and it has an advantage of not worrying about exceeding a call stack.
Also traverse method is a good candidate for using a technique called "tail recursion", but for JavaScript tail call is currently supported only by Safari/WebKit.
Hey Mateusz, thanks for your feedback! Probably, the sentence is not very well structured. What I meant is that in the traverse example we donβt have prior knowledge of the size and therefore we cannot use for loops. However we can use a while loop or alternatively a recursive function.
Itβs a great input regarding the call stack overflow πππ, I definitely missed it out of sight, since I alway tend to be biased toward functional approaches.
Here's the thing with double linked lists: they are just shitty vectors/"arraylists"/you-name-it. With double linked lists, you throw away all advantages you get with single linked lists, which is being able to add elements to the list at pretty much zero cost and having it be immutable on top of it, at the cost of random access being expensive.
With double linked lists, you still have the high cost of random access, but you are going to modify the list when adding elements.
It is definitely a neat idea in theory if what you want is a single linked list that is, well, linked in both directions, but other than that, I always felt a double-linked list is not something to be used in real-world scenarios (maybe except some fringe scenarios?).
And linked lists are definitely a very good example when making one's first steps in functional programming, and this blog post neatly demonstrates that. It is, I'd say, the data structure where even an object-oriented programmer will likely naturally resort to functional "patterns".
Good post, I just wanted to chime in with some considerations for real-world use.
Hey Daniel thanks for your feedback! Actually writing those articles about data structures is a way to research on that topics. I also must admit, I donβt have any real scenarios where I would need a linked list, so I would be curious to know if you are using it in production and how.
Could you also elaborate on the idea of βimmutable listsβ I find it very interesting, but I am not quite sure how it is supposed to work. Donβt you have to mutate at least the βnextβ field?
So the way this immutability works in a single linked list is that when you have a list B-C-D, B points to C, and C points to D. C doesn't know about B at all, all it knows is its own value, and where C is! So when you want to "add" to the list you simply create a "cell" that contains the value of A and has "next" point to B. The original list doesn't know anything about being longer now. It is the simplest extensible immutable data structure possible.
As you can see, a major downside of this is that you can only prepend to the list, and not append. Doing the latter would mean that either the list has to be mutable and you can change the last cell to point to the new value instead of to nothing; or to copy the entire list with a different last cell; or do some "black magic" with complicated-but-fast tree structures that make it seem like you copied the entire collection without actually doing the full thing (Clojure does the latter with all its collections).
A good use case - and the only one I can think of off the top of my head - of single linked lists are lazy sequences. Many functional programming languages make use of that. To make an example from your post, the
search
function (often calledfilter
in functional programming). It would return a lazy sequence and only continue to search/filter as you continue to consume the sequence. Accessing the "next" field then just triggers the next filtering step. That only really works with single-linked lists because they don't have true random access.Daniel, thanks for the detailed response! That was very insightful. Do you think one could achieve a behaviour similar to the lazy sequence by using JS generators, that yield next item from the list, when called?
As guess you can keep track of the tail instead of the head and linking new items to prev, so that the added ones remain unchanged. Reverse linking, is it something you had in mind?
Delete method should look like this
I think your delete method is missing some steps.
Hi Gleb , article was clear and so useful :)
May I know how can I use the deleteNode function ? Because I can see , you did not use on end of the whole code with example. How can I call that function I mean which arguments should I use with that deleteNode(node) function? May I know what is a sample node ?
Thanks :)
Hey Cihat! Thank you for the feedback.
deleteNode
as you can see from the type definition requires reference to the node stored in the list. Here is an example of searching and deleting a particular node:Thanks @glebirovich for quick answer :)
Hi, great article.
I don't get it, why on insertToBegin of a double linked list,
if the list is empty you're using :
this.head = new Node(),
and on the same condition when insertAtEnd, you're using:
this.head = node.
or maybe it's just an example you can do it both ways?
Thought I got it at first but then I got a little confused, would like to clear this up!
Thanks.
Hey Sapir,
Thanks for pointing out this method. You are right, I should have assigned
node
, instead of instantiating a new class in the if clause:It's a correct way because it also ensures that we return a reference to the node, which is assigned to the
head
. Thanks, I updated the code!Got it! thank you.
Nice article ππ
Thanks Alex!
Hi Gleb,
Thanks for the article. I like the recursive function in the insertAtEnd. Shouldn't the recursive call to getLast(node) be getLast(node.next)? So that the next node will be checked?
Hey! You are totally right, nice catch. I will update the code!
Created an account just to thank you for posting this. Fantastic stuff.
Hey Frederick! Thank you a lot!