user41750: I know this question has been asked before, however it was asked two years ago and I have some other constraints to add.
(Previous question here) : Is using malloc() and free() a really bad idea on Arduino?
I understand that dynamically allocating and freeing memory can cause fragmentation, and without an operating system to manage the memory, this fragmentation can reach a point where no memory can be allocated because the current memory is a mess.
That being said, the only memory allocation I plan to do is for a linked list that I am using as a stack. This means that I will only even be adding or removing from one end of the linked list. In the case that the arduino malloc() implementation is 'next fit', is it safe to assume that I can use this linked list safely, since the only element I'll be removing is the next one that fit, and everything else will stay where it is?
tl;dr the two questions I'm asking:
Is the arduino malloc implementation 'next fit'? Where can I read up on this in detail?
AND
A single stack running in a 'next fit' environment will never cause fragmentation, correct?

user31105: Probably it will not be a problem, since when you free memory, those memory sizes will be equal than the memory size you malloc. E.g. suppose one element of a linked list is 24 bytes, if this is freed, the next time when 24 bytes are requested by malloc, it will use that space.
So my assumption it works when you never use free or malloc, EXCEPT when using it for one single linked list with elements that are always equal size.
However, you have to make sure:

You do not free memory elsewhere (with different size)
You do not malloc memory elsewhere (with different size)
All libraries you use do not call a malloc/free under water.

Also, you can do an easy check by malloc/free and fill one item a lot of times one element (thus adding and removing it), and checking the memory usage is similar (or it does not crash to have a very simple test).
Btw, afaik Arduino pointers use 2 bytes, so this can cause quite some memory. If you use max. 256 elements, consider using indices, but in this case you have to write your own 'linked list' library (e.g. when removing, you have to move all subsequent indices).

user7508: On my answer to the question you are referencing, I state that “If
you use the heap like a stack (last in is first out), then it will
behave like a stack and not fragment.” This seems to be exactly your
usage pattern, thus you should not fear fragmentation. Of course, the
caveat written in Michel Keijzers’ answer applies: you should make sure
that no other part of your code, including libraries, is using
malloc() and free().
Just to give some evidence, the avr-lic documentation provides some
implementation details about malloc:

When allocating memory [...] If nothing could be found on the
  freelist, heap extension is attempted. [...] When deallocating the
  topmost chunk of memory, the size of the heap is reduced.

All this can be seen in action in the source code of malloc() and
free(), which is abundantly commented and quite readable.

Edit 1: From the same section of the avr-libc documentation, we learn
about how realloc() grows a memory chunk:

If [...] the old chunk is at the top of heap, and the above freelist
  walk did not reveal a large enough chunk on the freelist to satisfy
  the new request, an attempt is made to quickly extend this topmost
  chunk (and thus the heap), so no need arises to copy over the existing
  data.

Based on this, I would suggest you use an array, rather than a linked
list, and use realloc() to adjust the size of the array. A linked list
of n objects of size m has a memory cost n × (m+4):
each objects has an overhead of 2 bytes for the linking pointer, plus 2
bytes for malloc()'s internal bookkeeping. The cost of an array would
be only (n × m)+2.
In this case, however, it is essential that no other part of your code
uses malloc(), otherwise realloc() could end up allocating a whole
new array, which would be very costly.

Edit 2: I wrote a small test program that randomly grows and shrinks
a memory buffer. Running the test on an Uno shows that the allocated
memory chunk never changes address even though its size varies wildly.
void setup()
{
    Serial.begin(9600);
}

void loop()
{
    static void *p;
    static size_t sz;
    sz = random(max(sz, 22) - 20, min(sz + 20, 1536) + 1);
    p = realloc(p, sz);
    Serial.print((uintptr_t) p);
    Serial.print("  ");
    Serial.println(sz);
}


41750: <p>I know this question has been asked before, however it was asked two years ago and I have some other constraints to add.</p>

<p>(Previous question here) : <a href="https://arduino.stackexchange.com/questions/682/is-using-malloc-and-free-a-really-bad-idea-on-arduino">Is using malloc() and free() a really bad idea on Arduino?</a></p>

<p>I understand that dynamically allocating and freeing memory can cause fragmentation, and without an operating system to manage the memory, this fragmentation can reach a point where no memory can be allocated because the current memory is a mess.</p>

<p>That being said, the only memory allocation I plan to do is for a linked list that I am using as a stack. This means that I will only even be adding or removing from one end of the linked list. In the case that the arduino <code>malloc()</code> implementation is 'next fit', is it safe to assume that I can use this linked list safely, since the only element I'll be removing is the next one that fit, and everything else will stay where it is?</p>

<p>tl;dr the two questions I'm asking:</p>

<p>Is the arduino <code>malloc</code> implementation 'next fit'? Where can I read up on this in detail?</p>

<p>AND</p>

<p>A single stack running in a 'next fit' environment will never cause fragmentation, correct?</p>
 31105: <p>Probably it will not be a problem, since when you free memory, those memory sizes will be equal than the memory size you malloc. E.g. suppose one element of a linked list is 24 bytes, if this is freed, the next time when 24 bytes are requested by malloc, it will use that space.</p>

<p>So my assumption it works when you never use free or malloc, EXCEPT when using it for one single linked list with elements that are always equal size.</p>

<p>However, you have to make sure:</p>

<ul>
<li>You do not free memory elsewhere (with different size)</li>
<li>You do not malloc memory elsewhere (with different size)</li>
<li>All libraries you use do not call a malloc/free under water.</li>
</ul>

<p>Also, you can do an easy check by malloc/free and fill one item a lot of times one element (thus adding and removing it), and checking the memory usage is similar (or it does not crash to have a very simple test).</p>

<p>Btw, afaik Arduino pointers use 2 bytes, so this can cause quite some memory. If you use max. 256 elements, consider using indices, but in this case you have to write your own 'linked list' library (e.g. when removing, you have to move all subsequent indices).</p>
 7508: <p>On <a href="https://arduino.stackexchange.com/a/8947">my answer</a> to the question you are referencing, I state that “<em>If
you use the heap like a stack (last in is first out), then it will
behave like a stack and not fragment.</em>” This seems to be exactly your
usage pattern, thus you should not fear fragmentation. Of course, the
caveat written in Michel Keijzers’ answer applies: you should make sure
that no other part of your code, including libraries, is using
<code>malloc()</code> and <code>free()</code>.</p>

<p>Just to give some evidence, the avr-lic documentation provides some
<a href="http://www.nongnu.org/avr-libc/user-manual/malloc.html#malloc_impl" rel="nofollow noreferrer">implementation details about malloc</a>:</p>

<blockquote>
  <p>When allocating memory [...] If nothing could be found on the
  freelist, heap extension is attempted. [...] When deallocating the
  topmost chunk of memory, the size of the heap is reduced.</p>
</blockquote>

<p>All this can be seen in action in the <a href="http://svn.savannah.gnu.org/viewvc/avr-libc/trunk/avr-libc/libc/stdlib/malloc.c?revision=2149&amp;view=markup" rel="nofollow noreferrer">source code of malloc() and
free()</a>, which is abundantly commented and quite readable.</p>

<hr>

<p><strong>Edit 1</strong>: From the same section of the avr-libc documentation, we learn
about how <code>realloc()</code> grows a memory chunk:</p>

<blockquote>
  <p>If [...] the old chunk is at the top of heap, and the above freelist
  walk did not reveal a large enough chunk on the freelist to satisfy
  the new request, an attempt is made to quickly extend this topmost
  chunk (and thus the heap), so no need arises to copy over the existing
  data.</p>
</blockquote>

<p>Based on this, I would suggest you use an array, rather than a linked
list, and use <code>realloc()</code> to adjust the size of the array. A linked list
of <em>n</em> objects of size <em>m</em> has a memory cost <em>n</em>&nbsp;×&nbsp;(<em>m</em>+4):
each objects has an overhead of 2 bytes for the linking pointer, plus 2
bytes for <code>malloc()</code>'s internal bookkeeping. The cost of an array would
be only (<em>n</em>&nbsp;×&nbsp;<em>m</em>)+2.</p>

<p>In this case, however, it is essential that no other part of your code
uses <code>malloc()</code>, otherwise <code>realloc()</code> could end up allocating a whole
new array, which would be very costly.</p>

<hr>

<p><strong>Edit 2</strong>: I wrote a small test program that randomly grows and shrinks
a memory buffer. Running the test on an Uno shows that the allocated
memory chunk never changes address even though its size varies wildly.</p>

<pre class="lang-c++ prettyprint-override"><code>void setup()
{
    Serial.begin(9600);
}

void loop()
{
    static void *p;
    static size_t sz;
    sz = random(max(sz, 22) - 20, min(sz + 20, 1536) + 1);
    p = realloc(p, sz);
    Serial.print((uintptr_t) p);
    Serial.print("  ");
    Serial.println(sz);
}
</code></pre>
