やあ子どもたち。おじさんはビーズを数珠（じゅず）状に繋げたいと思いました。いろんな感じにビーズを繋げたくて、輪っかとかも作りたいと思いました。好きな場所にビーズを挿入したり、取り除いたり、、そして繋げた個々のビーズたちが、互いに隣り合うビーズを相互に参照できるような処理を書きたいです。（図を参照）
しかし、おいそれと使えるようなテンプレートが標準ライブラリーにはなさそうなことがわかりました。
STLにはstd::listというものがあり、C++11あたりからは、std::next() std::prev() なんていう便利な隣接子参照の方法が定義されているにもかかわらず、何故おじさんが自分で双方向連結リストのテンプレートを作らなくてはならなかったのか、それは単純にループ環構造（循環ループ構造？呼び方いろいろ）を可能としたかったからです。ループ環構造を扱いたかっただけなのです。
ループ環構造といえどもメモリのどこかに始点と終点という形で格納されているわけですが、その場合にこの始点終点をまたぐ処理のところで特殊な分岐処理に入るのがとても受け入れられなかったためです。分岐処理の導入はプログラムの可読性を下げ、バグ混入の機会を増やすばかりかパフォーマンスも下げてしまいます。
ループ環構造の概念は世によく認知された内容であり、関連記事も「list 循環」「Circular doubly linked list」などで検索すればたくさん出てきますが、どういうわけか今だにというか、自前実装してるケースが多いようで、すぐに使えてしかも標準的な実装というものがなかなか見つからずでしたので、安直かも知れませんがあえて欲しいものを自作してみましたので以下そのメモというわけです。
《データ構造》
ビーズの連なりを双方向連結リストとして表現します。構造体も一つ両隣のビーズを覚えておくだけのとてもシンプルなものとなります。
class Node { public: Node( void ) :_next( 0 ) ,_prev( 0 ) {} Node* _next, *_prev; };
これだけなら日記に起こすほどでもないというほど簡単ですね。
《アルゴリズム》
ビーズの連なりの中、特定の場所に新しくビーズを挿入したり、すでにビーズの連なりの中にいる特定のビーズを、それだけ除去したりするための、挿入・除去のコードを考えました。ビーズの型は何でもよいので関数テンプレートにします。
class NodeAlgorithm { public: template< class T > // T::_next, T::_prev static void lc_node_cat(T* a, T* b) { // ノードの連結 // （aのnext側にbを連結します） if (a) a->_next = b; if (b) b->_prev = a; return; } template< class T > // T::_next, T::_prev static void lc_node_insert(T* p, T* x, T* n) { // 単位ノード挿入 // （pを_prev、nが_nextとなるようにxを挿入します） lc_node_cat(p, x); lc_node_cat(x, n); return; } template< class TNode > static void lc_node_remove(TNode* p) { // 単位ノード除去 //（pの登録を除去します。当然ですが、オブジェクトの削除はしません） if (p->_prev) p->_prev->_next = p->_next; if (p->_next) p->_next->_prev = p->_prev; return; } template< class TNode, class Func > static void lc_node_blooper(TNode* head, Func& func) { // ノード巡回用 TNode* inode = head; do { func(inode); inode = inode->_next; }// inode while (inode != head && inode != nullptr); return; } template< class TNode, class Func > static void lc_node_blooper2(TNode* head, Func& func) { // ノード巡回用（next保存） TNode* inode = head; do { TNode* next0 = inode->_next; func(inode); inode = next0; }// inode while (inode != head && inode != nullptr); return; } template< class TNode > static TNode* lc_reverse_nodes(TNode* head) { // ノードチェーンを反転し、 // 反転後の head を返します。 TNode* last; lc_node_blooper2(head, [&last](TNode* inode) { swap(inode->_next, inode->_prev); last = inode; }); return last; } template< class TNode > static TNode* lc_construct_doubly_linked_list (const vector< TNode* >& loop, const bool is_loop=false) { // ノード配列からループ双方向リスト構造を構築 TNode* head = loop.front(); TNode* last = head; auto it = loop.begin(); for (; it != loop.end(); ++it ) { lc_node_cat(last, *it); last = *it; }// i if( is_loop ) lc_node_cat(last, head);// 環構造に return head; } template< class TNode > static void lc_release_nodes(TNode* head) { // ノードのメモリ解放 if (head) // headが無効化されていた場合は何もしない { lc_node_blooper2(head, [](TNode* node) {delete node; }); } return; } template< class TNode > static void lc_splice(TNode* dst_begin, TNode* dst_end, TNode* src_head, TNode* src_tail) { // スプライシング // dst_begin |--->| dst_end の間に、[src_head, src_tail]を挿入します。 // 対象のdst区間にあったフラグメントは適切にケアされるべき。 lc_node_cat(dst_begin, src_head); lc_node_cat(src_tail, dst_end); return; } };
簡単だね。そして当然のことながら管理上、ループでない場合は端っこのノードをどっちか一つ、ループの場合はどれか一つ、ノードを覚えておく必要がありますよね。一つだけlc_release_nodesについて。ある双方向リストをスプライシングなどして、他のリスト構造にマージさせた場合、もとのリストは無効とし、マージ後のリストだけ有効となるが、このような場合はうっかりマージ前のリスト構造の解放をしてしまわないよう、どこか（通常はリスト構造を表現している構造体の中など）、で保持しているhead要素を無効化(nullptr化）しておこう。そのような使い方にこの関数は対応しているよ。
以上、双方向結合リストデータ構造について働く、単純な操作（連結・挿入・除去、、）と活用事例（環構造作成・メモリ解放）を見てきたが、いかがだったかな。2年後3年後の自分が見た時にも、すぐ使えるくらいのシンプルさには仕上がってると思っているよ。
《活用事例》
さて、上記のような道具を実際に活用していくプラクティカルな事例として、何か考えてみるよ。そのうち記事にします。
さて、今日はそういうわけでここまでだ。チャオ！
