There are a few 'tricks' that you can use here ...

1. A "struct" is fundamentally an associative-array structure.  So, if you've got an "id" field of any sort, a struct can locate any "id" almost instantly.  This is much faster than searching an array (which has a hidden cost created by virtual-memory paging over a large "footprint").
2. When you add a struct to another struct or to an array, you are actually moving a reference to the structure.  You should find that (afaik!), if the struct is present both in an array and in a struct, both of these are references to one-and-the-same memory block.
3. Use the most-convenient data structure when building the original set of records.  This is probably going to be a "struct."  If you then need to have an array of elements sorted in a particular way, build that array last, by using a "sort" operation to arrange the records in whatever order you want.  Since you'are actually (afaik...) moving references, you're not stomping on too much RAM.

"Sorting" is what I call an "unexpectedly fast and efficient" operation, because it's one of the most heavily-studied operations in all of data processing ... and has been since the days of Herman Hollerith.

You would need to search the array each time you appended a structure. Then append the structure, only if did not already exist in the array. But that raises the question, is an array really the right type of object to be using in the case?  A structure, which does not allow duplicates, would seem more appropriate.