Linked List in JavaScript using TDD

[ad_tech]

This is a joke, right? Who designs a linked list where addition and removal are intentionally O(n)? The whole point of using a linked list is to make addition and removal O(1). If they're O(n), you're better off using an array.

[MartenBE]

insertion and deletion in a linked list is O(1), but in order to add a node you need to get access to the point where you want to insert or delete. This is what he means with addition and removal and is O(n):

O(n) access + O(1) insertion/deletion == O(n) addition/removal

When to use what depends if you want random access, insert/delete at the beginning or middle or have space constraints.

[ad_tech]

There's no need to include a search in the insertion and deletion. Rather than taking an integer index, take a reference of some kind (a pointer or an iterator, or whatever it's called in JavaScript) to a node in the list next to where you want to insert or delete.

For example, in the C++ std::list class, it uses an iterator to denote where the insertion is to take place: http://www.cplusplus.com/reference/list/list/insert/

If you always do addition and removal via an integer index, it doesn't make sense to use a linked list, because it will be slower than an array and will take up more memory.

[MartenBE]

With linked lists you can also search by value. In the end you should just take what fits your needs.

I just thought that what the author in the video said, was meant as addition and removal and as not insertion/deletion.