c++ - 2つの値を持つ二重リンクリストノード

Question

したがって、二重リンクリストがあり、名前と年齢を追加して、両方を個別に検索できるようにするには、どうすればよいでしょうか。

Answer 1

あなたが尋ねる、

「それで、二重リンクリストがあり、名前と年齢を追加して、両方を別々に検索できるようにしたいとしたら、どうすればよいでしょうか？」

実際問題として、そのような目的のために二重にリンクされたリストを実装することはありません。代わりに、などの標準ライブラリコンテナを使用しますstd::vector。またはstd::map。

しかし、これが学習のためであることを考えると、問題は問題が何であるかです…

どうすれば各ノードを2つのリンクリストに同時に参加させることができるのでしょうか。

これを行う簡単な方法の1つは、リストノードにデータノードへのポインタを含めることです。ことわざにあるように、コンピュータサイエンスの問題の解決策は、間接参照の1つの余分な層です。もちろん、これは間接参照が多すぎるという問題の解決策でもあります。:-p

Answer 2

リンクリストは、複数のキーで並べ替えるのに適しています。

 item0:   age=1             item1:    age=99;
          name='z'                    name='a';
          next_age=item1              next_age=NULL;
          next_name=NULL              next_name=item0

基本的に考慮すべき唯一の追加事項は、リストトラバースアルゴリズムを共有し、次/前のリンクの場所を知らないようにする方法です。

1つの解決策は、リスト構造を次のようにラップすることです。

 struct list_s {
        struct list_s *next;
        struct list_s *prev;
        void *key_ptr;
        struct master_struct_s *parent;
 }

 struct master_struct_s {
        struct list_s key1;
        struct list_s key2;
        struct list_s key3;
        int other_data;
 }

これで、リストの並べ替えアルゴリズムは＆key1、＆key2、または＆key3で機能し、各リスト構造体が「親」構造体または独自のコンテナを参照するため、other_dataのコンテンツを参照できるようになりました。