5 ms·

Who says inserting into a linked list is faster than inserting things into an array? If the array is pre-allocated, or even crazier a c++ vector or c# list<> w

Who says inserting into a linked list is faster than inserting things into an array? If the array is pre-allocated, or even crazier a c++ vector or c# list<> with an amortizing growth function that only needs to be invoked once or twice, it'll be much faster than inserting a new node in a linked list. The array/list can be pre-allocated to the size you need and have good cache locality and minimal container overhead -- the linked list will have the overhead of the pointer to the next node (2x for a doubly-linked list) + the type descriptor (if you're using a language like c#, java, python, etc.) per node and data located all over the heap with cache misses everywhere. <sameCondescendingToneAsParent> If I was asked during an interview why inserting things in a linked list is faster that [sic] inserting things into an array, and I provided an answer that made him blankly stare back at me, would I want to take the job? </sameCondescendingToneAsParent> Perhaps you're getting a guy switching careers or fields of expertise (web -> system or accounting -> embedded), or someone that just has that gap in their knowledge, or someone that's just having a plain ol' brainfart at that point in time. No need to be as rude as I responded in my third paragraph.

10098 14y ago
> Who says inserting into a linked list is faster than inserting things into an array? If the array is pre-allocated, or even crazier a c++ vector or c# list<> with an amortizing growth function that only needs to be invoked once or twice, it'll be much faster than inserting a new node in a linked list. I said insert, not append. What made you assume the question was about inserting at the end? Even if you have a big pre-allocated array, inserting an element somewhere in the middle will still cost you the price of shifting the "tail" of the array to make space for the new element, while the list will not have that cost.
- anthonyb 14y ago
  Now you're just being an ass. What makes you think insert is important anyway? The typical use cases for an array/list are pop, append and indexing. Python's list implementation uses arrays, not linked lists, internally for exactly this reason: indexing being O[1] is more important for most purposes than fast inserts. (http://docs.python.org/faq/design.html#how-are-lists-implemented http://docs.python.org/faq/design.html#how-are-lists-impleme...)
  - 10098 14y ago
    The purpose of asking this question is to find whether the person who answers understands the subject matter well enough to reason about it and arrive at the correct answer. It doesn't even matter if insert is a typical use case or not; if the candidate knows data structures he won't even think about it. And what's with the name-calling? Aren't you capable of having a normal, polite discussion?
    - anthonyb 14y ago
      I know lots of really good programmers who wouldn't necessarily be able to describe the details of linked list algorithms or malloc. They're doing high level stuff with numpy/scipy, or working on web frameworks, and whether they know malloc or not is irrelevant. You keep talking about "the subject matter" and "programming" like it's one topic. It's not, hence the "you're an ass" comment - you're just repeating your argument ad nauseam and ignoring everything everyone else has to say. It's possible to be a good programmer without knowing how linked lists work in excruciating detail - get over it.
      - 10098 14y ago
        > * It's possible to be a good programmer without knowing how linked lists work in excruciating detail - get over it.* It looks like our definitions of "good" and "programmer" are somewhat different.
        anthonyb 14y ago
        People used to make similar arguments in favour of assembly language, ie. you can't be a programmer unless you can drill down to the bare metal and make it do backflips/squeeze every last bit of performance out. Now computers are faster, compilers are smarter at optimising and it's only really the case if you're doing hardcore kernel programming or writing a game engine. C, pointers and linked lists are going the same way as computers get faster still: they're not very relevant unless you're coding something in a specific niche. And I've seen people who were the opposite of what you're saying - people who knew lots about low level C/Assembly stuff, but who couldn't write clean, maintainable high level code to save their life. But to get back on the original topic - none of that is relevant to learning how to program. Loops, variables, data structures, managing state, functions and classes are more what you want to teach to start with, and are far more relevant to most programmers than malloc or linked lists.

10098 14y ago

> Who says inserting into a linked list is faster than inserting things into an array? If the array is pre-allocated, or even crazier a c++ vector or c# list<> with an amortizing growth function that only needs to be invoked once or twice, it'll be much faster than inserting a new node in a linked list. I said insert, not append. What made you assume the question was about inserting at the end? Even if you have a big pre-allocated array, inserting an element somewhere in the middle will still cost you the price of shifting the "tail" of the array to make space for the new element, while the list will not have that cost.

anthonyb 14y ago
Now you're just being an ass. What makes you think insert is important anyway? The typical use cases for an array/list are pop, append and indexing. Python's list implementation uses arrays, not linked lists, internally for exactly this reason: indexing being O[1] is more important for most purposes than fast inserts. (http://docs.python.org/faq/design.html#how-are-lists-implemented http://docs.python.org/faq/design.html#how-are-lists-impleme...)
- 10098 14y ago
  The purpose of asking this question is to find whether the person who answers understands the subject matter well enough to reason about it and arrive at the correct answer. It doesn't even matter if insert is a typical use case or not; if the candidate knows data structures he won't even think about it. And what's with the name-calling? Aren't you capable of having a normal, polite discussion?
  - anthonyb 14y ago
    I know lots of really good programmers who wouldn't necessarily be able to describe the details of linked list algorithms or malloc. They're doing high level stuff with numpy/scipy, or working on web frameworks, and whether they know malloc or not is irrelevant. You keep talking about "the subject matter" and "programming" like it's one topic. It's not, hence the "you're an ass" comment - you're just repeating your argument ad nauseam and ignoring everything everyone else has to say. It's possible to be a good programmer without knowing how linked lists work in excruciating detail - get over it.
    - 10098 14y ago
      > * It's possible to be a good programmer without knowing how linked lists work in excruciating detail - get over it.* It looks like our definitions of "good" and "programmer" are somewhat different.
      - anthonyb 14y ago
        People used to make similar arguments in favour of assembly language, ie. you can't be a programmer unless you can drill down to the bare metal and make it do backflips/squeeze every last bit of performance out. Now computers are faster, compilers are smarter at optimising and it's only really the case if you're doing hardcore kernel programming or writing a game engine. C, pointers and linked lists are going the same way as computers get faster still: they're not very relevant unless you're coding something in a specific niche. And I've seen people who were the opposite of what you're saying - people who knew lots about low level C/Assembly stuff, but who couldn't write clean, maintainable high level code to save their life. But to get back on the original topic - none of that is relevant to learning how to program. Loops, variables, data structures, managing state, functions and classes are more what you want to teach to start with, and are far more relevant to most programmers than malloc or linked lists.