1.Выделить новый массив размером большим на 1 элемент чем прежний;
2.скопировать в начало старый массив;
3.удалить старый массив;
4.последнему элементу присвоить указатель на новую строку,
Первые 3 пункта выполняет realloc().
Если операция добавления нового элемента в массив регулярная, то стоит над этим поработать дополнительно. Обычно в таких случаях выделяют не на 1 элемент больше, а например в 2 раза больше. Отсюда возникают дополнительные потребности в хранении количества занятых элементов, количества всех элементов и т.п.
Операция динамического выделения памяти - достаточно затратная, поэтому стоит свести ее к минимуму.