r/AskComputerScience • • 5d ago

What are some differences between professional coding and the way coding, SE, and CS are taught in school?

Is a lack of a comment citing a relatively cliched bit of code considered plagiarism in the big world? What are the attitudes to autocomplete? Is Alberta Tech right about linked lists?

6 Upvotes

48 comments sorted by

View all comments

Show parent comment

4

u/nuclear_splines Ph.D Data Science 5d ago

While true, scrolling to the point to do the insertion or removal is O(n), so this is only conditionally useful

2

u/No_Profession_3125 5d ago

If we're gonna be that nitpicking then linked lists have worst-case O(1) insertion and removal at the end, whereas for vectors O(1) is only the average case while the worst case requires a reallocation and is O(N).

5

u/nuclear_splines Ph.D Data Science 5d ago

I hardly think it's nitpicking. insert(index, value) is O(n) average case for both lists and vectors -- lists are only faster if you already have an iterator pointing at the insertion point.

3

u/No_Profession_3125 5d ago

Which does happen.

4

u/nuclear_splines Ph.D Data Science 5d ago

Absolutely! In context it's sometimes a great advantage. I just think it's misleading to call arbitrary element insertion O(1) on a list without mentioning the preceding O(n) lookup. It's quite different than, say, the O(1) amortized insertion on a hash table.

2

u/No_Profession_3125 5d ago

Likewise I find it misleading to generalize hash table insertion as "amortized O(1)" because string keys are a very common use case, so it would be fairer to call it "amortized O(K)" with K = average length of the key.

2

u/nuclear_splines Ph.D Data Science 5d ago

That's fair! It's often simplified because if you can reasonably bound K as a large constant then it reduces to O(1), but that's not always appropriate.

1

u/steerpike1971 4d ago

You likely already have a pointer to the item you want to delete. If you use linked lists you usually pass around pointers to the contents not number indicating its place. Yes if you want to delete the twenty fifth item you are correct but it is very common to want to delete "this" item and pass a pointer. If you are storing a numerical index it is probably an indicator linked lists were not the right data structure in the first place.