What does "overhead" memory refer to in the case of Linked Lists?
<p>I understand that a node is usually 8 bytes, 4 for a value, 4 for a pointer in a singly linked list.</p>

<p>Does this mean that a doubly linked list node is 12 bytes in memory with two pointers?</p>

<p>Also this book I'm reading talks about how theres 8 bytes of "overhead" for every 12 byte node, what does this refer to?</p>

<p>First, you're evidently talking about a 32-bit machine since your pointers and values are 4 bytes.  Obviously, that's different for a 64-bit machine.</p>

<p>Second, the value needn't be 4 bytes.  Frequently the value is a pointer or an int, in which case it is 4 bytes (on your 32-bit machine).  But if it was a double, for example, it would be 8 bytes.  In fact, the payload could be any type at all, and have that type's size.</p>

<p>Third, your book probably is referring to the two pointers - the links - as the "overhead'.</p>

<p>Fourth, your book is omitting the impact of the memory manager ("heap manager").  Frequently, because of alignment issues and heap management issues, heap elements are larger than actually requested.  Most heap implementations on a 32-bit machine won't allocate 12 bytes when you ask for 12.  They'll allocate 16 bytes. (The last 4 bytes are not used by your program.)  Because for many machines, 8-byte alignment of certain values (e.g., doubles) is either required by the machine architecture or desirable for performance reasons. You have to investigate yourself, for your particular heap implementation (that is, the compiler's run-time's heap implementation) what kind of overhead it imposes.  Additionally, some heap implementations (many?) actually use memory inside the allocated object for its own bookkeeping purposes.  In this case, that header amount is sometimes as small as 4 bytes, but typically, for most machines which require 8 byte alignment for doubles, is 8 bytes.  So in this usual case, if you ask for 12 bytes you'll <em>actually</em> use up <em>24</em> bytes:  8 bytes of heap overhead and 12 bytes for your data, and that's only 20, so an additional 4 bytes just for alignment!</p>

python memory-management linked-list