どこがわからないのかがわからんのだけど、
1. doubly linked listを使ってるところなら、これはまったく本質とは関係なくて、
stackとして使うlistっぽいものを2つ用意すればいいだけ
key用とobject用

2. 問題は、huge array Hを元に、(small stack Sを補助として)小さなdictionaryを作れ
ということなので、イメージとしては、H: 英語辞典から、たとえば、
a-zのエントリのみの辞書をつくって、「他のキーに対してはNILを返す」ようにしてください
ということ
HのキーkとSのキーjに対して、S[H[k]]=kとH[S[j]=H[S[j]]=jが成立するようにSを作っていけばいいだけ
Sはキーの管理しかしてないので、同サイズのS'も作ってobjectの管理をすればよろし
これで問題ないことは、init, search, insert, deleteを具体的に示さないといかんのだけど、
簡単だし、たぶん上の解答にかいてあると思う