title: Linked lists. Where to allocate and how to cope with fragmentation?
body: <ul>
  <li>Location 
  <ul>
  <li>in the heap, fragmented (malloc for every node) -inefficient in several different ways (slow allocation, slow access, memory fragmentation)</li>
  <li>in the heap, in one large chunk - all the flexibility, gained by the data structure is lost, when needing to realloc</li>
  <li>in the stack - the stack tends to be rather limited in size, so allocating large structures on it is not recommended at all</li>
  </ul></li>
  </ul>
  
  <p>Their big advantage, insert O(1), seems rather useless in the environment of fragmented memory and thousands of calls to the memory allocator to give us another 10 bytes.</p>
  
  <hr>
  
  <p>EDIT to clarify:<br>
  This question was asked on an interview. It is not a workplace question and so the usual heuristics of hoping to stumble blindly on the correct decision out of a small set of standard algorithms is not applicable.</p>
  
  <p>The existing answers and comments mention that "malloc is not so slow", "malloc partially fights fragmentation". OK, if we use another data structure, for example a C port of the C++ vector (that is - allocate sequential memory of sufficient size, if data expands, reallocate to a twice larger chunk) all problems are solved, but we loose the fast insert/remove. Any scenarios where a linked list (allocated where?) has vast superiority to a vector?</p>