双方向循环リスト

Feb 28, 20150 likes1,672 views

Masaki Kaga

双方向循环リストについて自分の理解をまとめてみた。データ構造の中で一番好きかもしれない。

はじめに
効率的なプログラムを書くには？
?データを適切なデータ構造に保存する
?適切なアルゴリズムを実行する

データ構造とリスト
基本的なデータ構造(Wikipedia参照)
?配列
?連想配列
?線形リスト←これ
?木構造
?グラフ

線形リストの特徴（一部）
?ランダムアクセスができない
→a番目を参照するときは前からa回見ていく
→通常の配列ならO(1),data[a]でok
?途中での挿入?削除ができる
→例：{1,2,4,5}を{1,2,3,4,5}にするのがO(1)※
→通常の配列なら1つずつずらすのでO(n)

つまり
?操作をするからランダムアクセスができない
→挿入?削除で要素数が変化
?どこでも操作できるわけではない
→今見てる場所でのみ操作できるO(1)※
※2ページ前のO(1)も場所による

双方向循环リスト
?任意のノードと隣接している両方のリンクを持つ
→双方向に移動可能
?先頭と末尾がリンク
→面倒な処理なしに循環する

双方向循环リストの強み
?円の上をぐるぐる回るような処理に強い
?要素が死んだり生まれたりする処理に強い
例
順番にキャラクターが行動するが、死ぬこともある
死んだキャラを削除することで処理速度を上げる

実装方法
C++なら#include <list>
でok！（少しややこしい）
要素が削除される一方
なら→のような書き方
もアリ

実践
AOJ 0301 （PCK2014予選7問目）
問題概要（超意訳）
?N(≦200000)人が輪になって座っている
?ある人に死神が憑りついている
?数a(≦100)が宣言さる
?奇数なら反時計回りに、偶数なら反時計周りにa人分死神が移動
?移動した先の人は死んで、時計周りに隣の人に憑りつく
?これをM(<N)回行う
?その後Q(<1000)回生存確認が行われるので、生死を答える

実践?解答例
流れ
?配列は要素数が多いのでmainの外
?入力を受け取る
?双方向循环リストを構築
?m回の殺戮（移動と削除）
?q回の出力
（ランダムアクセスができる）
計算量はO(Ma)=O(20000000)
間に合う

補足
?循環しているので、移動回数をmodで減らせることもある
?配列を使って構築するのも限度があるので、STLも学んでおく
?Wikipediaを読む

ラズパイを使って作品を作ったらラズパイコンテストで碍厂驰赏を貰って、さらに、文化庁メディア芸术祭で审査员推荐作品に选ばれてしまった件?自作チップでラズパイ...Industrial Technology Research Institute (ITRI)(工業技術研究院, 工研院)

【卒业论文】尝尝惭を用いた惭耻濒迟颈-础驳别苍迟-顿别产补迟别における反论の効果に関する研究harmonylab

近年の生成 AI の活用の拡大とともに, 大規模言語モデル(LLM)の推論能力の向上や, 人間にとって推論過程が理解しやすい出力を行うように様々な手法が提案されてきた. 本研究では, LLM の推論能力向上手法としての MAD に着目し, 既存の MAD フレームワークに対して人間の議論では一般的に使用される反論を導入することを提案した. 本研究の反論の導入により, フィードバック内容の多様化や推論過程を明確にすることができることを示した.

【卒业论文】深层学习によるログ异常検知モデルを用いたサイバー攻撃検知に関する研究harmonylab

测距センサと滨惭鲍センサを用いた指轮型デバイスにおける颜认証システムの提案sugiuralab

スマートリングは，主に决済やスマートロックなどに利用できる便利なウェアラブルデバイスであるが，个人认証机能の搭载例は少なくセキュリティ上の悬念が残されている．心拍数や动作特性を利用する认証では，认証に时间がかかるなどの问题があり，指纹认証や颜认証もデバイスのサイズや消费电力，プライバシーの问题が课题となっている．そこで，我々は测距センサと滨惭鲍センサを搭载した指轮型デバイスを用いることで，スマートリングに搭载可能なほど小型かつ省电力で，カメラ不使用によりプライバシーリスクを低减した颜认証システムを提案する．

狈辞诲补滨迟蝉耻办颈冲反省観点の分类に基づく试合の振り返り支援システムに関する有用性検証冲顿贰滨惭2025Matsushita Laboratory

本研究の目的は，チームスポーツの選手が試合後に行う振り返りを支援することである．試合内容を振り返り反省点を認識することは，ミスの繰り返しを防いだり，プレー中の判断精度を向上させたりする上で重要である．しかし，チームスポーツでは，個人の行動だけでなく，展開に応じた位置取りや選手間の連携などチーム全体の状況を意識する必要があり，考慮すべき項目が多く反省点を系統立てて言語化することは容易ではない．そこで，反省内容をタイプ分けし，項目ごとに反省点を言語化できるように支援することで，この解決を試みた．提案システムの有用性を検証するため，選手の動きが複雑化している傾向にあるスポーツであるサッカーを対象とし，サッカー経験者12名を対象に，システムを利用して試合内容を振り返る様子を観察した．その結果，反省観点の提示が反省内容の具体化や，多角的な視点からの反省の促進に寄与することが示唆された．

実はアナタの身近にある！？ Linux のチェックポイント／レストア機能 (NTT Tech Conference 2025 発表資料)NTT DATA Technology & Innovation

空间オーディオを用いたヘッドパスワードの提案と音源提示手法の最适化sugiuralab

近年、音声アシスタントやバイタルデータの计测などの机能を搭载したイヤフォン型のウェアラブルデバイスであるヒアラブルデバイスが注目されている。これらの机能を悪用して、他者の个人情报や机密情报に不正にアクセスすることを防ぐために、ヒアラブルデバイス向けの认証システムが必要とされ、多くの研究が进められている。しかし、既存の研究は、生体情报を用いたものが多く、生体情报の変化や保存への悬念などの问题を抱えている。そこで、我々は、空间音响技术とヘッドジェスチャを用いた知识ベースの认証システムを提案する。具体的には、音源の组合せをパスワードとし、空间的に提示される音源をヘッドトラッキングと歯の噛み合わせ音で选択することにより认証を行う。