I hope im not overweighting this structure with adding new rows (i mean from memory side)
That's not really possible. Each of these structs is, what, eight bytes? 24 bytes a row is not a huge memory deal. I'm still betting on "messed up linked list of column headings".