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?
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?
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 called filter 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?
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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?
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?
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
searchfunction (often calledfilterin 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?