C言語でのアルゴリズムの質問をさせて下さい。

現在以下のようなプログラムを作ろうと思っています。

0〜65535までの数字をIDとしてユーザに割当てる。
ユーザが割当てられたIDを使わなくなったときはそのIDを返却し、
返却されたIDは回収されて他のユーザに割当てられる。

最も簡単なやり方は、user_id[65536]などの大きな配列を作って、
使用状況を配列の中身の0か1で判断する、といったものかと思います。

しかしこのやり方よりもっと効率的なものはないでしょうか？
このような大きな配列を作るのは実装としてまずいのかな…と感じています。

初心者で申し訳ありませんがアドバイスよろしくお願いします。