There are any number of different ways to skin this particular cat, some more efficient than others. Below is off the top of my head and meant to get you headed in the right general direction.
In addition to your $category_link
you need something that indexes your subcategories by category. Something like $subcategory_link
which might be an array of arrays, indexed first by the category id (or name), and then by an incrementing integer for each subcategory (or its id, or whatever). In addition to your existing query and while
loop, run a query that retrieves all of the subcategories, and then fills in $subcategory_link
with the relevant information in a second, similar while
loop.
$sc = array(
'id' => $subcategory['id'],
'subcategory' => $subcategory['subcategory'],
);
$subcategory_link[$subcategory['cat_id']][$j++] = $sc;
Note that this array is first indexed by the category id. Then in your template:
{foreach $category_link as $cat}
<div class="category">{$cat.catname}</div>
{foreach $subcategory_link[$cat.cat_id] as $subcat}
<div class="subcat">{$subcat.subcategory}</div>
{/foreach}
{/foreach}
Note: The above has not been checked for proper Smarty syntax. You should get the idea though.
It is left as an exercise for you to determine how to handle categories with no subcategories, and to improve efficiency.