連結リスト（基本操作）

// ノードクラス
class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

// 連結リストクラス
class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    
    // 先頭に挿入 - O(1)
    insertHead(value) {
        const newNode = new ListNode(value);
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
        return this.size;
    }
    
    // 末尾に挿入 - O(n)
    insertTail(value) {
        const newNode = new ListNode(value);
        
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
        return this.size;
    }
    
    // 指定位置に挿入 - O(n)
    insertAt(index, value) {
        if (index < 0 || index > this.size) {
            throw new Error("インデックスが範囲外です");
        }
        
        if (index === 0) {
            return this.insertHead(value);
        }
        
        const newNode = new ListNode(value);
        let current = this.head;
        
        for (let i = 0; i < index - 1; i++) {
            current = current.next;
        }
        
        newNode.next = current.next;
        current.next = newNode;
        this.size++;
        return this.size;
    }
    
    // 先頭を削除 - O(1)
    deleteHead() {
        if (!this.head) {
            throw new Error("リストが空です");
        }
        
        const deletedValue = this.head.value;
        this.head = this.head.next;
        this.size--;
        return deletedValue;
    }
    
    // 末尾を削除 - O(n)
    deleteTail() {
        if (!this.head) {
            throw new Error("リストが空です");
        }
        
        if (!this.head.next) {
            const deletedValue = this.head.value;
            this.head = null;
            this.size--;
            return deletedValue;
        }
        
        let current = this.head;
        while (current.next.next) {
            current = current.next;
        }
        
        const deletedValue = current.next.value;
        current.next = null;
        this.size--;
        return deletedValue;
    }
    
    // 値を検索 - O(n)
    find(value) {
        let current = this.head;
        let index = 0;
        
        while (current) {
            if (current.value === value) {
                return index;
            }
            current = current.next;
            index++;
        }
        
        return -1; // 見つからない場合
    }
    
    // リストの内容を配列で表示
    toArray() {
        const result = [];
        let current = this.head;
        
        while (current) {
            result.push(current.value);
            current = current.next;
        }
        
        return result;
    }
    
    // リストの構造を文字列で表示
    toString() {
        if (!this.head) {
            return "空のリスト";
        }
        return this.toArray().join(" → ") + " → null";
    }
    
    // リストのサイズを取得 - O(1)
    getSize() {
        return this.size;
    }
    
    // リストが空かどうかを確認 - O(1)
    isEmpty() {
        return this.head === null;
    }
}

// 使用例
const list = new LinkedList();

// 要素の挿入
list.insertHead(2);      // [2]
list.insertHead(1);      // [1, 2]
list.insertTail(4);      // [1, 2, 4]
list.insertAt(2, 3);     // [1, 2, 3, 4]

console.log(list.toString()); // "1 → 2 → 3 → 4 → null"

// 要素の検索
console.log(list.find(3)); // 2 (インデックス)
console.log(list.find(5)); // -1 (見つからない)

// 要素の削除
console.log(list.deleteHead()); // 1
console.log(list.deleteTail()); // 4
console.log(list.toString());   // "2 → 3 → null"

// 状態の確認
console.log(list.getSize());    // 2
console.log(list.isEmpty());    // false