I would say a "shared secret" is not "security through obscurity." After all, the only cryptographic system you can mathematically prove to be unbreakable in theory given any advances in mathematics or physics and unlimited resources, involves the two parties sitting down together and sharing a secret beforehand. (OTP). Everything else is less secure, not more secure.
Security through obscurity would be if the "shared secret" was something about the design of the security mechanisms, and not about the shared key. (For example, if firefighters knew that pulling up on a doorknob quickly three times caused it to open. That's not a secure key, people would have already guessed it whenever they did so and doors just opened.)
Smushed list. Size O(1). The smushed list is a list of variables (of the same type), stored in a single variable of that type. To produce the smushed list, simply XOR all the elements of the list together, then store. To get a value back, simply XOR the smushed list by all the elements other than the one you want. Smushing is also embarrassingly parallel (you can smush two halves separately and then smush the results) so producing smushed lists is blazingly fast.
Unlinked list. O(n). This is slightly faster than a linked list, and acts as a "black box". Simply allocate nodes that are not linked to each other in any way. The data normally stays out of the way of your program, but in case of a core dump you can find it again. NOTE: If your language does reference-counting this will not work. Get a real language that does what you say.
Search-bush. Search trees are good at bisecting data, but they are not really conducive to a random walk for inspiration. Begin by constructing a binary search tree, keeping track of all the nodes you've added, and simply add a third, random, pointer to each node - have it point at a random node somewhere in the tree. In the search algorithm, either follow the left, right, or random node, depending on how much meandering you are interested in doing. The journey is the destination.
Security through obscurity would be if the "shared secret" was something about the design of the security mechanisms, and not about the shared key. (For example, if firefighters knew that pulling up on a doorknob quickly three times caused it to open. That's not a secure key, people would have already guessed it whenever they did so and doors just opened.)