Weitere Möglichkeit: Eine Stringlist, die nicht mit einem Array als Backend arbeitet, sondern mit einer doppelt verketteten Liste. Die verbraucht zwar letztendlich insgesamt etwas mehr Speicher - aber kommt mit Fragmentierung zurecht.
Das Array speichert aber auch nur Pointer auf die Strings. Der Speicher für alle Strings muss also auch nicht in einem Stück vorliegen.