Когда вы говорите «списки», вы имеете в виду связанные списки?
Массив некоторого вида элемента занимает память одного элемента на слот, независимо от того, заполнен этот слот или нет. Связанный список занимает только память для элементов, которые он фактически содержит, но для каждого он занимает память одного элемента, плюс размер одного указателя (два, если это список с двойной связью, если только Вы можете использовать трюк XOR, чтобы перекрыть их).
Если вы храните указатели и используете односвязный список, то каждая ссылка на список в два раза больше размера каждого слота массива. Это означает, что если список заполнен не наполовину, связанный список будет использовать больше памяти, а не меньше.
Если вы используете язык, у которого во время выполнения есть накладные расходы для каждого объекта (например, Java и C, если вы сами не распределяете память), то вам также придется платить за эти издержки по каждой ссылке в списке, но только один раз в массиве, а соотношение еще хуже.
Я бы предложил, чтобы ваш алгоритм балансировки оставлял узлы дерева как минимум наполовину заполненными. Если вы разделите узел, когда он полон, вы создадите два наполовину полных узла. Затем вам нужно объединить соседние узлы, когда они заполнены менее чем наполовину. Затем вы можете использовать массив, будучи уверенным в том, что он более эффективен, чем связанный список.
Понятия не имею о деталях удаления, извините!