Linked lists. Where to allocate and how to cope with fragmentation?

Question

• Location
  • in the heap, fragmented (malloc for every node) -inefficient in several different ways (slow allocation, slow access, memory fragmentation)
  • in the heap, in one large chunk - all the flexibility, gained by the data structure is lost, when needing to realloc
  • in the stack - the stack tends to be rather limited in size, so allocating large structures on it is not recommended at all

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.

---

EDIT to clarify:
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.

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?

Answer 1

This sounds like premature optimization. I think the correct way to go about it is to:

1. use the simplest implementation possible;
2. profile the entire program.
3. if profiling shows that there is a performance issue with the list, consider alternative implementations (including alternative allocators).