# 機能設計書 43-lists

## 概要

本ドキュメントは、Nim標準ライブラリの`lists`モジュールの機能設計について記述する。`lists`は、単方向連結リスト、双方向連結リスト、およびそれらの循環リスト（リング）を提供する包括的な連結リストライブラリである。

### 本機能の処理概要

**業務上の目的・背景**：連結リストは、要素の挿入・削除が頻繁に行われるシナリオで効率的なデータ構造である。配列ベースのコレクション（seq、Deque等）と異なり、要素の挿入・削除時にメモリの再配置が不要であり、特定の位置への操作がO(1)で実行可能。本モジュールは効率性を重視し、`next`/`prev`ポインタを公開APIとして直接操作を許可している。

**機能の利用シーン**：
- 頻繁な挿入・削除操作：任意位置への要素追加・削除が多い場合
- LRUキャッシュ：最近使用された要素の追跡と古い要素の削除
- undo/redo機能：操作履歴の管理（双方向リスト）
- 循環バッファ：一定周期で繰り返すデータ構造（リング）
- イベントリスナー管理：動的な登録・解除が必要なコールバック管理

**主要な処理内容**：
1. リスト初期化（init*）：空のリストを作成
2. ノード生成（newSinglyLinkedNode, newDoublyLinkedNode）：値を持つノードを作成
3. 末尾追加（add/append）：リストの末尾に要素を追加
4. 先頭追加（prepend）：リストの先頭に要素を追加
5. 要素削除（remove）：指定ノードをリストから削除
6. 検索（find, contains）：値の検索と存在確認
7. イテレーション（items, mitems, nodes）：全要素の走査
8. リスト結合（addMoved, prependMoved）：2つのリストを結合
9. シャローコピー（copy）：リストの浅いコピーを作成
10. 配列変換（toSinglyLinkedList等）：openArrayからリストへの変換

**関連システム・外部連携**：本モジュールは純粋なデータ構造ライブラリであり、外部システムとの直接連携はない。`std/deques`モジュールとは相補的な関係にある。

**権限による制御**：該当なし（ライブラリモジュールのため）

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 本モジュールはCLIライブラリのため画面関連なし |

## 機能種別

データ構造ライブラリ / コレクション操作 / 連結リスト

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| value | T | Yes（追加時） | 追加する値 | - |
| n | SomeLinkedNode[T] | Yes（ノード追加時） | 追加するノード | - |
| elems | openArray[T] | Yes（変換時） | 変換元の配列 | - |

### 入力データソース

- プログラム内で生成されたリストインスタンス
- openArray（toSinglyLinkedList等使用時）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | SinglyLinkedList[T] / DoublyLinkedList[T] | 単方向/双方向リスト |
| result | SinglyLinkedRing[T] / DoublyLinkedRing[T] | 単方向/双方向リング |
| result | SinglyLinkedNode[T] / DoublyLinkedNode[T] | ノード参照 |
| result | bool | 検索結果（contains）、削除結果（SinglyLinkedList.remove） |
| result | string | 文字列表現（$） |

### 出力先

呼び出し元プログラムへの戻り値として返却

## 処理フロー

### 処理シーケンス

```
1. リスト初期化
   └─ init*: デフォルト値でリストを作成（head/tail = nil）

2. ノード生成
   └─ newSinglyLinkedNode/newDoublyLinkedNode: 値を持つノードを生成

3. 要素追加
   └─ add: 末尾に追加（tailを更新）
   └─ prepend: 先頭に追加（headを更新）

4. 要素削除
   └─ SinglyLinkedList.remove: O(n)で前ノードを探索して削除
   └─ DoublyLinkedList.remove: O(1)でprevポインタを使用して削除

5. リスト結合
   └─ addMoved: bをaの末尾に移動（bは空になる）
   └─ prependMoved: bをaの先頭に移動
```

### フローチャート

```mermaid
flowchart TD
    A[リスト操作] --> B{リスト種別}
    B -->|SinglyLinked| C[単方向リスト]
    B -->|DoublyLinked| D[双方向リスト]
    C --> E{操作種別}
    D --> E
    E -->|add| F[末尾追加 O(1)]
    E -->|prepend| G[先頭追加 O(1)]
    E -->|remove| H{リスト種別}
    H -->|Singly| I[O(n)で前ノード探索]
    H -->|Doubly| J[O(1)で直接削除]
    E -->|find| K[O(n)で線形探索]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | ポインタ公開 | next/prevポインタは公開され直接操作可能 | 常時 |
| BR-02 | 単方向削除O(n) | SinglyLinkedList.removeは前ノード探索のためO(n) | SinglyLinkedList |
| BR-03 | 双方向削除O(1) | DoublyLinkedList.removeはprev使用でO(1) | DoublyLinkedList |
| BR-04 | リング循環 | リングの末尾ノードは先頭ノードを指す | Ring種別 |
| BR-05 | addMoved空化 | addMovedは元リストを空にする（同一アドレス除く） | addMoved/prependMoved |
| BR-06 | 自己追加サイクル | 自分自身へのaddMovedはサイクルを生成 | addMoved(a, a) |
| BR-07 | シャローコピー | copyはシャローコピーを作成（要素は参照を共有） | copy関数 |

### 計算ロジック

- **リスト走査**: headからnextポインタを辿って全要素にアクセス
- **リング走査**: headからnextを辿り、headに戻ったら終了
- **双方向削除**: `n.next.prev = n.prev; n.prev.next = n.next`で両側のポインタを更新

## データベース操作仕様

### 操作別データベース影響一覧

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| - | - | - | 本モジュールはデータベース操作を行わない |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | - | DoublyLinkedList.removeでリストに含まれないノードを指定 | 動作未定義、事前確認を推奨 |

### リトライ仕様

該当なし（同期処理のためリトライ不要）

## トランザクション仕様

該当なし（データベース操作なし）

## パフォーマンス要件

- **add/prepend**: O(1)の時間計算量（全リスト種別）
- **DoublyLinkedList.remove**: O(1)の時間計算量
- **SinglyLinkedList.remove**: O(n)の時間計算量（前ノード探索）
- **find/contains**: O(n)の時間計算量（線形探索）
- **addMoved/prependMoved**: O(1)の時間計算量
- **copy**: O(n)の時間計算量
- **空間計算量**: O(n)、ただしノードごとにポインタのオーバーヘッドあり

## セキュリティ考慮事項

- ノードはrefオブジェクトとしてGCにより管理される
- next/prevポインタの直接操作によりデータ構造の整合性が壊れる可能性がある（ユーザー責任）
- cursorプラグマによりprev/tailは参照カウントに影響しない

## 備考

- Nim 1.5.1以降で追加された機能（prepend(a,b), addMoved, copy, to*関数等）には`since`プラグマが付与
- DoublyLinkedRingはtailフィールドを持たない（head.prevで末尾にアクセス可能）
- 型エイリアス（SomeLinkedList, SomeLinkedRing等）でジェネリック処理を実現

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: 型定義を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | lists.nim | `lib/pure/collections/lists.nim` | 65-108行目: ノード型とリスト型の定義 |

**読解のコツ**:
- **66-73行目**: `DoublyLinkedNodeObj[T]` - next/prev/valueフィールド、prevは`{.cursor.}`
- **75-81行目**: `SinglyLinkedNodeObj[T]` - next/valueフィールドのみ
- **83-100行目**: 4種類のリスト/リング型（SinglyLinkedList, DoublyLinkedList, SinglyLinkedRing, DoublyLinkedRing）
- **102-108行目**: 型エイリアス（SomeLinkedList, SomeLinkedRing, SomeLinkedCollection, SomeLinkedNode）

**注意点**:
- `{.cursor.}`プラグマはprev/tailに付与され、参照カウントに影響しない

#### Step 2: 初期化とノード生成を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | lists.nim | `lib/pure/collections/lists.nim` | 110-166行目: init関数とnewNode関数 |

**主要処理フロー**:
- **110-148行目**: 4つのinit関数 - `default()`で空リストを返却
- **150-166行目**: newDoublyLinkedNode/newSinglyLinkedNode - new()でノード生成し値を設定

#### Step 3: イテレーションを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | lists.nim | `lib/pure/collections/lists.nim` | 168-180行目: itemsListImpl/itemsRingImplテンプレート |
| 3-2 | lists.nim | `lib/pure/collections/lists.nim` | 182-298行目: items/mitems/nodesイテレータ |

**主要処理フロー**:
- **168-172行目**: `itemsListImpl` - headからnextを辿ってnilまで走査
- **174-180行目**: `itemsRingImpl` - headからnextを辿り、headに戻ったら終了
- **248-271行目**: `nodes`イテレータ - 走査中の削除をサポート（nxt = it.nextを先に保存）

#### Step 4: 追加操作を理解する（SinglyLinkedList）

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | lists.nim | `lib/pure/collections/lists.nim` | 393-464行目: SinglyLinkedList.add/prepend |

**主要処理フロー**:
- **393-412行目**: `add(n)` - n.next=nil, tail.next=n, tail=n, 空ならhead=n
- **430-447行目**: `prepend(n)` - n.next=head, head=n, 空ならtail=n

#### Step 5: 追加・削除操作を理解する（DoublyLinkedList）

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | lists.nim | `lib/pure/collections/lists.nim` | 523-607行目: DoublyLinkedList.add/prepend |
| 5-2 | lists.nim | `lib/pure/collections/lists.nim` | 728-753行目: DoublyLinkedList.remove |

**主要処理フロー**:
- **523-545行目**: `add(n)` - n.prev=tail, tail.next=n, tail=n
- **566-588行目**: `prepend(n)` - n.next=head, head.prev=n, head=n
- **728-753行目**: `remove(n)` - n.next.prev=n.prev, n.prev.next=n.next でO(1)削除

#### Step 6: リスト結合を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 6-1 | lists.nim | `lib/pure/collections/lists.nim` | 490-521行目: SinglyLinkedList.addMoved |
| 6-2 | lists.nim | `lib/pure/collections/lists.nim` | 633-666行目: DoublyLinkedList.addMoved |
| 6-3 | lists.nim | `lib/pure/collections/lists.nim` | 366-391行目: prependMoved |

**主要処理フロー**:
- **490-521行目**: SinglyLinkedList.addMoved - a.tail.next=b.head, a.tail=b.tail, b空化
- **633-666行目**: DoublyLinkedList.addMoved - 双方向ポインタを更新
- **366-391行目**: prependMoved - b.addMoved(a)してswap

#### Step 7: リング操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 7-1 | lists.nim | `lib/pure/collections/lists.nim` | 757-835行目: SinglyLinkedRing.add/prepend |
| 7-2 | lists.nim | `lib/pure/collections/lists.nim` | 839-949行目: DoublyLinkedRing.add/prepend/remove |

**主要処理フロー**:
- **757-778行目**: SinglyLinkedRing.add - tail.next=n, n.next=head（循環維持）
- **839-863行目**: DoublyLinkedRing.add - head.prev.next=n, n.prev=head.prev, head.prev=n
- **929-949行目**: DoublyLinkedRing.remove - ポインタ更新、最後の1要素ならhead=nil

### プログラム呼び出し階層図

```
lists.nim (ユーザーコード)
    │
    ├─ 型定義
    │   ├─ SinglyLinkedNodeObj[T] {next, value}
    │   ├─ DoublyLinkedNodeObj[T] {next, prev, value}
    │   ├─ SinglyLinkedList[T] {head, tail}
    │   ├─ DoublyLinkedList[T] {head, tail}
    │   ├─ SinglyLinkedRing[T] {head, tail}
    │   └─ DoublyLinkedRing[T] {head}
    │
    ├─ 初期化
    │   ├─ initSinglyLinkedList() → default()
    │   ├─ initDoublyLinkedList() → default()
    │   ├─ initSinglyLinkedRing() → default()
    │   └─ initDoublyLinkedRing() → default()
    │
    ├─ ノード生成
    │   ├─ newSinglyLinkedNode(value) → new() + value設定
    │   └─ newDoublyLinkedNode(value) → new() + value設定
    │
    ├─ 追加操作 (O(1))
    │   ├─ add(n) → 末尾追加（tail更新）
    │   └─ prepend(n) → 先頭追加（head更新）
    │
    ├─ 削除操作
    │   ├─ SinglyLinkedList.remove(n) → O(n)で前ノード探索
    │   ├─ DoublyLinkedList.remove(n) → O(1)でポインタ更新
    │   └─ DoublyLinkedRing.remove(n) → O(1)でポインタ更新
    │
    ├─ 結合操作 (O(1))
    │   ├─ addMoved(a, b) → aの末尾にbを移動
    │   └─ prependMoved(a, b) → aの先頭にbを移動
    │
    └─ イテレーション
        ├─ items() → itemsListImpl / itemsRingImpl
        ├─ mitems() → 変更可能なitems
        └─ nodes() → ノードを直接返却（走査中削除対応）
```

### データフロー図

```
[入力]                         [処理]                        [出力]

value ────────────────────▶ newSinglyLinkedNode ─────────▶ SinglyLinkedNode
                                     │
                                     ▼
openArray[T] ─────────────▶ toSinglyLinkedList ──────────▶ SinglyLinkedList
                                     │
                           ┌─────────┴─────────┐
                           │                   │
                     ┌─────▼─────┐       ┌─────▼─────┐
                     │   head    │       │   tail    │
                     │     ↓     │       │     ↑     │
                     │  [Node1]──┼──next──▶[Node2]──┼──next──▶[Node3]
                     │           │       │           │
                     └───────────┘       └───────────┘
                           │                   │
                           └─────────┬─────────┘
                                     ▼
                              SinglyLinkedList

DoublyLinkedList:
                     head                           tail
                       ↓                             ↓
                   [Node1] ◀──prev── [Node2] ◀──prev── [Node3]
                       │              │              │
                       └───next──▶   └───next──▶   nil
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| lists.nim | `lib/pure/collections/lists.nim` | ソース | メインモジュール（全機能実装） |
| deques.nim | `lib/pure/collections/deques.nim` | ソース | 関連モジュール（両端キュー） |
| since.nim | `lib/std/private/since.nim` | ソース | バージョン管理プラグマ |
| assertions.nim | `lib/std/assertions.nim` | ソース | assert機能を提供 |
