1.2.2. リスト

class Node {
    int data;      // データを格納するフィールド
    Node next;     // 次のノードを参照するポインタ
    
    // コンストラクタ - 新しいノードの初期化
    Node(int data) {
        this.data = data;
        this.next = null;  // 初期状態では次ノードなし
    }
}

class SingleLinkedList {
    Node head;     // リストの先頭ノードへの参照
    
    // 先頭への挿入 - O(1)の操作
    public void insertAtHead(int data) {
        // 新しいノードを作成
        Node newNode = new Node(data);
        // 新ノードの次ポインタを現在の先頭に設定
        newNode.next = head;
        // 先頭ポインタを新ノードに更新
        head = newNode;
    }
    
    // 指定値の探索 - O(n)の操作
    public boolean search(int key) {
        Node current = head;
        // リストの終端に達するまで探索を続ける
        while (current != null) {
            if (current.data == key) {
                return true;    // 値が見つかった
            }
            current = current.next;  // 次のノードへ移動
        }
        return false;   // リスト内に値が存在しない
    }
    
    // 全要素の表示 - O(n)の操作
    public void display() {
        Node current = head;
        // リストの終端に達するまですべてのノードを表示
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;  // 次のノードへ移動
        }
        System.out.println("null");
    }
}

// 使用例
public class Main {
    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        list.insertAtHead(3);   // リストに3を追加
        list.insertAtHead(7);   // リストの先頭に7を追加
        list.insertAtHead(12);  // リストの先頭に12を追加
        
        list.display();  // 出力: 12 -> 7 -> 3 -> null
        
        System.out.println("7は存在するか: " + list.search(7));  // 出力: true
        System.out.println("5は存在するか: " + list.search(5));  // 出力: false
    }
}

class Node {
    int data;      // データを格納するフィールド
    Node next;     // 次のノードを参照するポインタ
    
    // コンストラクタ - 新しいノードの初期化
    Node(int data) {
        this.data = data;
        this.next = null;  // 初期状態では次ノードなし
    }
}

class SingleLinkedList {
    Node head;     // リストの先頭ノードへの参照
    
    // 先頭への挿入 - O(1)の操作
    public void insertAtHead(int data) {
        // 新しいノードを作成
        Node newNode = new Node(data);
        // 新ノードの次ポインタを現在の先頭に設定
        newNode.next = head;
        // 先頭ポインタを新ノードに更新
        head = newNode;
    }
    
    // 指定値の探索 - O(n)の操作
    public boolean search(int key) {
        Node current = head;
        // リストの終端に達するまで探索を続ける
        while (current != null) {
            if (current.data == key) {
                return true;    // 値が見つかった
            }
            current = current.next;  // 次のノードへ移動
        }
        return false;   // リスト内に値が存在しない
    }
    
    // 全要素の表示 - O(n)の操作
    public void display() {
        Node current = head;
        // リストの終端に達するまですべてのノードを表示
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;  // 次のノードへ移動
        }
        System.out.println("null");
    }
}

// 使用例
public class Main {
    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        list.insertAtHead(3);   // リストに3を追加
        list.insertAtHead(7);   // リストの先頭に7を追加
        list.insertAtHead(12);  // リストの先頭に12を追加
        
        list.display();  // 出力: 12 -> 7 -> 3 -> null
        
        System.out.println("7は存在するか: " + list.search(7));  // 出力: true
        System.out.println("5は存在するか: " + list.search(5));  // 出力: false
    }
}

class Node:
    def __init__(self, data):
        self.data = data    # データを格納
        self.next = None    # 次ノードへの参照（初期値はNone）

class SingleLinkedList:
    def __init__(self):
        self.head = None    # 先頭ノードへの参照（初期値はNone）
    
    # 先頭への挿入 - O(1)の操作
    def insert_at_head(self, data):
        new_node = Node(data)    # 新ノードを作成
        new_node.next = self.head    # 新ノードの次を現在の先頭に
        self.head = new_node    # 先頭を新ノードに更新
    
    # 指定値の探索 - O(n)の操作
    def search(self, key):
        current = self.head
        while current is not None:    # リストの終端までループ
            if current.data == key:
                return True    # 値が見つかった
            current = current.next    # 次ノードへ移動
        return False    # リスト内に値が存在しない
    
    # 全要素の表示 - O(n)の操作
    def display(self):
        current = self.head
        while current is not None:    # リストの終端までループ
            print(f"{current.data} -> ", end="")
            current = current.next    # 次ノードへ移動
        print("None")

# 使用例
if __name__ == "__main__":
    linked_list = SingleLinkedList()
    linked_list.insert_at_head(3)    # リストに3を追加
    linked_list.insert_at_head(7)    # リストの先頭に7を追加
    linked_list.insert_at_head(12)   # リストの先頭に12を追加
    
    linked_list.display()    # 出力: 12 -> 7 -> 3 -> None
    
    print(f"7は存在するか: {linked_list.search(7)}")    # 出力: True
    print(f"5は存在するか: {linked_list.search(5)}")    # 出力: False

class Node:
    def __init__(self, data):
        self.data = data    # データを格納
        self.next = None    # 次ノードへの参照（初期値はNone）

class SingleLinkedList:
    def __init__(self):
        self.head = None    # 先頭ノードへの参照（初期値はNone）
    
    # 先頭への挿入 - O(1)の操作
    def insert_at_head(self, data):
        new_node = Node(data)    # 新ノードを作成
        new_node.next = self.head    # 新ノードの次を現在の先頭に
        self.head = new_node    # 先頭を新ノードに更新
    
    # 指定値の探索 - O(n)の操作
    def search(self, key):
        current = self.head
        while current is not None:    # リストの終端までループ
            if current.data == key:
                return True    # 値が見つかった
            current = current.next    # 次ノードへ移動
        return False    # リスト内に値が存在しない
    
    # 全要素の表示 - O(n)の操作
    def display(self):
        current = self.head
        while current is not None:    # リストの終端までループ
            print(f"{current.data} -> ", end="")
            current = current.next    # 次ノードへ移動
        print("None")

# 使用例
if __name__ == "__main__":
    linked_list = SingleLinkedList()
    linked_list.insert_at_head(3)    # リストに3を追加
    linked_list.insert_at_head(7)    # リストの先頭に7を追加
    linked_list.insert_at_head(12)   # リストの先頭に12を追加
    
    linked_list.display()    # 出力: 12 -> 7 -> 3 -> None
    
    print(f"7は存在するか: {linked_list.search(7)}")    # 出力: True
    print(f"5は存在するか: {linked_list.search(5)}")    # 出力: False

// ノード構造
構造体 Node {
    データ: 整数
    次: Node型へのポインタ
    前: Node型へのポインタ
}

// 1. 指定ノードの後ろに新しいノードを挿入する操作
関数 insertAfter(ノード: Node, 値: 整数)
    新ノード = 新しいNode作成
    新ノード.データ = 値
    
    // リンクの更新
    新ノード.次 = ノード.次
    新ノード.前 = ノード
    
    // 後続ノードが存在する場合、そのノードの「前」ポインタを更新
    もし ノード.次 != NULL ならば
        ノード.次.前 = 新ノード
    
    // 現在のノードの「次」ポインタを更新
    ノード.次 = 新ノード

// 2. 指定ノードを削除する操作
関数 deleteNode(ノード: Node)
    // 前のノードが存在する場合、その「次」ポインタを更新
    もし ノード.前 != NULL ならば
        ノード.前.次 = ノード.次
    
    // 次のノードが存在する場合、その「前」ポインタを更新
    もし ノード.次 != NULL ならば
        ノード.次.前 = ノード.前
    
    // ノードのメモリを解放
    ノードを解放

// ノード構造
構造体 Node {
    データ: 整数
    次: Node型へのポインタ
    前: Node型へのポインタ
}

// 1. 指定ノードの後ろに新しいノードを挿入する操作
関数 insertAfter(ノード: Node, 値: 整数)
    新ノード = 新しいNode作成
    新ノード.データ = 値
    
    // リンクの更新
    新ノード.次 = ノード.次
    新ノード.前 = ノード
    
    // 後続ノードが存在する場合、そのノードの「前」ポインタを更新
    もし ノード.次 != NULL ならば
        ノード.次.前 = 新ノード
    
    // 現在のノードの「次」ポインタを更新
    ノード.次 = 新ノード

// 2. 指定ノードを削除する操作
関数 deleteNode(ノード: Node)
    // 前のノードが存在する場合、その「次」ポインタを更新
    もし ノード.前 != NULL ならば
        ノード.前.次 = ノード.次
    
    // 次のノードが存在する場合、その「前」ポインタを更新
    もし ノード.次 != NULL ならば
        ノード.次.前 = ノード.前
    
    // ノードのメモリを解放
    ノードを解放

関数 hasCycle(head: Node): 真偽値
    // 空リストまたは要素が1つだけの場合
    もし head == NULL または head.next == NULL ならば
        return false
    
    slow = head        // カメ（1ステップずつ移動）
    fast = head.next   // ウサギ（2ステップずつ移動）
    
    // fastがNULLになるまで繰り返す
    while (fast != NULL かつ fast.next != NULL)
        // slowとfastが同じノードを指したら循環が存在する
        もし slow == fast ならば
            return true
        
        slow = slow.next       // カメは1ステップ進む
        fast = fast.next.next  // ウサギは2ステップ進む
    
    // fastがリストの終端に達した場合、循環はない
    return false

関数 hasCycle(head: Node): 真偽値
    // 空リストまたは要素が1つだけの場合
    もし head == NULL または head.next == NULL ならば
        return false
    
    slow = head        // カメ（1ステップずつ移動）
    fast = head.next   // ウサギ（2ステップずつ移動）
    
    // fastがNULLになるまで繰り返す
    while (fast != NULL かつ fast.next != NULL)
        // slowとfastが同じノードを指したら循環が存在する
        もし slow == fast ならば
            return true
        
        slow = slow.next       // カメは1ステップ進む
        fast = fast.next.next  // ウサギは2ステップ進む
    
    // fastがリストの終端に達した場合、循環はない
    return false

関数 mergeLists(list1: Node, list2: Node): Node
    // いずれかのリストが空の場合
    もし list1 == NULL ならば
        return list2
    もし list2 == NULL ならば
        return list1
    
    // 結果リストの先頭ノードを決定
    結果リスト: Node
    現在のノード: Node
    
    もし list1.データ <= list2.データ ならば
        結果リスト = list1
        list1 = list1.次
    そうでなければ
        結果リスト = list2
        list2 = list2.次
    
    現在のノード = 結果リスト
    
    // 両方のリストが空になるまでループ
    while (list1 != NULL かつ list2 != NULL)
        もし list1.データ <= list2.データ ならば
            現在のノード.次 = list1
            list1 = list1.次
        そうでなければ
            現在のノード.次 = list2
            list2 = list2.次
        
        現在のノード = 現在のノード.次
    
    // 残りのノードを結合
    もし list1 != NULL ならば
        現在のノード.次 = list1
    そうでなければ
        現在のノード.次 = list2
    
    return 結果リスト

関数 mergeLists(list1: Node, list2: Node): Node
    // いずれかのリストが空の場合
    もし list1 == NULL ならば
        return list2
    もし list2 == NULL ならば
        return list1
    
    // 結果リストの先頭ノードを決定
    結果リスト: Node
    現在のノード: Node
    
    もし list1.データ <= list2.データ ならば
        結果リスト = list1
        list1 = list1.次
    そうでなければ
        結果リスト = list2
        list2 = list2.次
    
    現在のノード = 結果リスト
    
    // 両方のリストが空になるまでループ
    while (list1 != NULL かつ list2 != NULL)
        もし list1.データ <= list2.データ ならば
            現在のノード.次 = list1
            list1 = list1.次
        そうでなければ
            現在のノード.次 = list2
            list2 = list2.次
        
        現在のノード = 現在のノード.次
    
    // 残りのノードを結合
    もし list1 != NULL ならば
        現在のノード.次 = list1
    そうでなければ
        現在のノード.次 = list2
    
    return 結果リスト