JavaScript: Project: Linked Lists

[Mogoatlhe]

Describe your suggestion

In the Linked List lesson it is stated that the benefit of linked lists over arrays are:

1. linked list elements can be easily inserted or removed without reallocation of other elements
2. in some programming languages the array size can be problematic, e.g. if you want to add a 6th element to an array of size 5.

It is then later stated that Linked Lists aren't really necessary in JavaScript, because the array size is not a limitation in JavaScript

So if array size is not a limitation in Javascript, are linked lists really necessary? The short answer to that is no;

The reason above, although valid, only addresses the second point mentioned above. It doesn't address the first point (how insertion/removal in JavaScript arrays is possible without manual reallocation of other elements)

• Solution
  • also mention that native array methods, like array.splice, are also the reason why linked lists aren't really necessary in JavaScript.

Path

Node / JS

Lesson Url

https://www.theodinproject.com/lessons/javascript-linked-lists

Checks

• [X] I have thoroughly read and understand The Odin Project Contributing Guide
• [X] Would you like to work on this issue?

(Optional) Discord Name

mogoatlhe

(Optional) Additional Comments

No response

[Mclilzee]

LinkedList vs ArrayList performance is a rabithole, its a big subject to get to start looking at the details that do we need it or not. The comment says short answer no, because the big answer is too technical and its a subject of its own in CS community. What is important in this section was the project itself and not the technicality or performance.

The links provided explain LinkedLists in more details aswell. for the time being it is always recommended that people don't go deep into rabbit holes until later when they finish TOP, they can do research and start looking up the subject if they are still interested to learn more.

[Mogoatlhe]

Hi, thank you for response.

I do understand that the point of the lesson/project is an introduction to the LinkedList, and that people should do their own research if they are interested to learn more.

However; that is not my point, nor is it about LinkedList technicality or performance. My point is about the lecture itself: In the lesson two reasons are mentioned as to why LinkedList are beneficial over arrays (easy insertion/deletion (no need to move other elements around) and size not being a problem). But only one of the reasons (array size not being a limitation in JavaScript) is given as to why LinkedLists aren't really necessary in JavaScript. That has left me (the reader) thinking "wait... what about the other benefit you mentioned? does that benefit also not make a difference in JavaScript, and if so how?"

[CouchofTomato]

I'm not against a small update to clarify. Please remember though that changes need to also reflect in the Ruby CS course before we can merge a PR. Usually you can submit a PR for just the JS course then once the wording is approved you can make the same changes to the Ruby course and push them up

[Mogoatlhe]

Honestly I didn't even consider the Ruby course at first but I am open to doing as you've suggested.

[Mclilzee]

I don't think you quite graps the difference between LinkedList and Arrays. Simply being able to insert or delete at certain indexes, or at the begging / end of an array does not replace why LinkedList were created for.

With an array, while inserting or deleting items the array size will get bigger or smaller, and when the array gets to a certain size, the computer will have to allocate new memory for that array and copy all the elements from the old memory into the new memory, that's the problem in performance.

LinkedList however doesn't have that limitation, no matter how big or how small the LinkedList become, the computer will never have to copy elements to a new memory location, cos the elements themselves is scattered all over memory and they are not behind eachother in a sequence that can run out of space.

In reality tho LinkedLists weren't that practical to begin with, they take more memory, they require linear search everytime you want an element that is not at the beggining of the List, and copying elements from one place to another in an array isn't that big of a problem.

Saying we don't need LinkedList because we already can insert and delete items is not the go to option here, we need more clarification if we wanna be correct about it.

[CouchofTomato]

If you have any suggestions @Mclilzee then feel free to discuss on the PR https://github.com/TheOdinProject/curriculum/pull/25781

[Mogoatlhe]

Simply being able to insert or delete at certain indexes does not replace why LinkedList were created for.

Being able to insert at certain indexes might not be why linked lists were created but it's definitely a benefit as mentioned in the lesson. Think of this array of size 10 from a programming language like C++: [0, 1, 2, 3, 4, 6, 7, 8, 9, ]. If I want to insert the number five in the correct position, I would first have to manually move the numbers 6, 7, 8, 9 up an index. Same with deleting a number from the array, other numbers would have to be moved down after the deletion. This process has to happen with each and every insertion/deletion. This limitation does not exist with linked lists, as mentioned in the lesson.

Now If I were to insert 10 into the above array, after inserting 5, I would have to create a new array with a bigger size, copy old elements into it, insert 10 and delete the old array because I only have access to 10 contiguous memory locations and I needed more than that. This problem doesn't exist with linked lists because like you mentioned (and as mentioned in the lesson) linked list nodes are scattered around in memory.

In a programming language like C++ (or other compiled languages) both the problems above have to be coded in manually and it can be tedious. So at an implementation (not performance or space) level the introduction of linked lists helps avoid those problems.

In JavaScript linked lists aren't really necessary because:

1. insertion/deletion can be done trivially at any index
2. the array grows (or shrinks) automatically as you insert (or delete) so you don't have to worry about creating a new one manually when the current one's capacity has been reached.

Now introducing my point: The lesson, despite mentioning both the above listed benefits of linked lists, only 2. is listed as the reason why linked lists aren't really necessary in JavaScript.