In my opinion there is no need to store the list of contacts of a user on chain, I can't see the benefits and it costs fees.
Storing in the local storage might be enough (with an option of export/import even better)
PolkadotJS UI has this functionality: Address Account, and it uses the keyring (@polkadot/ui-keyring) to store them.
If you want to store it on chain anyway, Polkadot for example has the identiy_pallet that allows a user to register its identity on-chain. It makes easier among other things to identify people and send them balances.
You can think of building something similar (pallet or smart contracts) to store the list of contacts of a user.