title: optimizing segregated list organization for malloc implementation
body: <p>I'm working on the <code>cs:app malloc lab</code> (I'm not looking for implemented answers, just high level processes), which if you're not familiar, asks for an implementation of <code>malloc()</code>. </p>
  
  <p>I have heap blocks with size, status <code>in_use</code>, and a pointer to the next/previous free block (if the block is not alloc'ed), which lends itself best to a <em>linked list</em> of free blocks (explicit free list). 
  Since we've been given that the max size for our heap is 2^32, I'm thinking about switching this to a <em>segregated list</em> in a BST, where the root node defines the size class and has a pointer to its free list (e.g. an object of size 2^n gets stored in a node's list where <code>node-&gt;class == n</code>). </p>
  
  <p>Intuition tells me using an AVL tree would speed up look-up for free blocks and insertion of new size classes, and using segregated lists helps mitigate fragmentation, but I'm still relatively new to thinking about these kinds of systems. Can someone confirm/deny my reasoning? (hope this isn't too vague a question!)   </p>