0

Recently I was learning about the difference between Array and Linked-Lists. There I found that:

  • In Array memory is allocated in compile-time. In the case of Linked-List memory is allocated during the execution on runtime dynamically.

Then I saw a comparison video between array and linked-list made by Computerphile There I learned about some key differences in the runtime of an array and linked-list in machines having a cache memory and not having it.

Now I was wondering that,
In the case of allocating a large number of data (e.g: 10^7 integers) is there any difference between:

  • I allocate 10^7 blocks in the memory at the beginning of the program (e.g: int ar[10^7]; ~ Declaring array in C)
  • I allocate 10^7 blocks one by one while taking input dynamically (e.g: implementing linked-list)

If there are differences indeed, how significant is that?

codermehraj
  • 46
  • 5
  • 1
    The difference is memory fragmentation. – Barmar Nov 12 '20 at 17:28
  • 2
    Arrays and Linked list can be allocated at run time using `malloc`. – Krishna Kanth Yenumula Nov 12 '20 at 17:29
  • 1
    @Barmar: And memory use; the array has no real overhead, the linked list has per-node overhead for forward (and possibly reverse) pointers, and the allocator itself adds overhead and (often) alignment losses that increase the actual memory used. For a simple array vs. linked list of `int`s on a 64 bit machine, the memory required for the linked list is probably at least 4x the memory used by an array with the same contents, even if it's just a singly-linked list, not doubly-linked. – ShadowRanger Nov 12 '20 at 17:31
  • I was wondering about is there any **runtime** difference in allocating ` at the beginning (memory fragmentation) ` vs ` in runtime one by one (using malloc)` – codermehraj Nov 12 '20 at 17:38
  • Each call to `malloc()` and family make a request to the operating system, which in turn provisions your process with a contiguous block of memory at some address. Subsequent calls are not guaranteed to give you addresses anywhere close the prior calls. If you need a large block of contiguous memory, ask for it in one call. There are [several good discussions on this topic in this post](https://stackoverflow.com/q/64029219/645128). – ryyker Nov 12 '20 at 18:14
  • Linked lists can also be allocated just fine at compile time. Whoever taught you the distincion you believe is true was entirely wrong. – R.. GitHub STOP HELPING ICE Nov 12 '20 at 19:09

0 Answers0