Chaba Content Site

静的配列 (Static Arrays)

2025-08-17

静的配列の学習ノート

JavaやC++を勉強してて初めて知った「静的配列」。最初はPythonに慣れてたから「なんで最初にサイズ決めなきゃいけないの？」って思った。

静的配列とは

静的型付け言語（Java、C++、C#など）では、配列を作る時にサイズと型を決める必要がある。一度決めたら変更できない。

# Pythonで静的配列をシミュレート
class StaticArray:
    def __init__(self, capacity):
        self.data = [0] * capacity  # 固定サイズ
        self.capacity = capacity
        self.length = 0  # 実際に使ってる要素数

基本操作と時間計算量

1. 読み込み（アクセス） - O(1)

def get(self, index):
    if 0 <= index < self.length:
        return self.data[index]
    raise IndexError("インデックスが範囲外")

# 使用例
myArray = StaticArray(5)
myArray.data = [1, 3, 5, 0, 0]  # 最初の3つだけ使用
myArray.length = 3

print(myArray.get(1))  # 3を返す（一瞬でアクセス！）

なぜO(1)なのか理解した瞬間：

2. 配列の走査 - O(n)

def traverse(self):
    for i in range(self.length):
        print(self.data[i])
    
    # または
    i = 0
    while i < self.length:
        print(self.data[i])
        i += 1

重要な発見：配列の最後の要素は常に n-1 番目（nは配列サイズ）

3. 末尾から削除 - O(1)

def remove_end(self):
    if self.length > 0:
        # ソフトデリート：値を0にして長さを減らすだけ
        self.data[self.length - 1] = 0
        self.length -= 1
        return True
    return False

# 例：[4, 5, 6] → [4, 5, 0]（lengthは2になる）

4. 任意の位置から削除 - O(n)

これが最初めっちゃ苦労した操作：

def remove_middle(self, index):
    if index < 0 or index >= self.length:
        return False
    
    # index+1から最後まで、全部1つ左にシフト
    for i in range(index + 1, self.length):
        self.data[i - 1] = self.data[i]
    
    # 最後の要素をクリア
    self.data[self.length - 1] = 0
    self.length -= 1
    return True

# 例：[1, 2, 3, 4] でindex=1を削除
# → [1, 3, 4, 0]（2が消えて、後ろが詰まる）

最悪のケース：最初の要素を削除 → 全要素をシフトする必要がある

5. 末尾に挿入 - O(1)

def insert_end(self, value):
    if self.length < self.capacity:
        self.data[self.length] = value
        self.length += 1
        return True
    return False  # 配列が満杯

# 例：[1, 2, 0, 0] に3を追加 → [1, 2, 3, 0]

6. 任意の位置に挿入 - O(n)

これも結構複雑だった：

def insert_middle(self, index, value):
    if index < 0 or index > self.length:
        return False
    if self.length >= self.capacity:
        return False  # 配列が満杯
    
    # 後ろから順番に右にシフト（重要：後ろから！）
    for i in range(self.length - 1, index - 1, -1):
        self.data[i + 1] = self.data[i]
    
    # indexの位置に挿入
    self.data[index] = value
    self.length += 1
    return True

# 例：[4, 5, 6, 0] のindex=1に8を挿入
# → [4, 8, 5, 6]

完全な静的配列クラス（練習用）

class StaticArray:
    def __init__(self, capacity):
        self.data = [0] * capacity
        self.capacity = capacity
        self.length = 0
    
    def get(self, index):
        if 0 <= index < self.length:
            return self.data[index]
        raise IndexError(f"Index {index} out of bounds")
    
    def set(self, index, value):
        if 0 <= index < self.length:
            self.data[index] = value
            return True
        return False
    
    def insert_end(self, value):
        if self.length < self.capacity:
            self.data[self.length] = value
            self.length += 1
            return True
        return False
    
    def remove_end(self):
        if self.length > 0:
            self.data[self.length - 1] = 0
            self.length -= 1
            return True
        return False
    
    def insert_middle(self, index, value):
        if index < 0 or index > self.length or self.length >= self.capacity:
            return False
        
        for i in range(self.length - 1, index - 1, -1):
            self.data[i + 1] = self.data[i]
        
        self.data[index] = value
        self.length += 1
        return True
    
    def remove_middle(self, index):
        if index < 0 or index >= self.length:
            return False
        
        for i in range(index + 1, self.length):
            self.data[i - 1] = self.data[i]
        
        self.data[self.length - 1] = 0
        self.length -= 1
        return True
    
    def print_array(self):
        print(f"配列: {self.data[:self.length]}")
        print(f"全体: {self.data}")
        print(f"長さ: {self.length}/{self.capacity}")

時間計算量まとめ

操作時間計算量備考
読み込みO(1)インデックスアクセス最強
挿入（末尾）O(1)空きがあれば一瞬
挿入（中間）O(n)シフトが必要
削除（末尾）O(1)簡単
削除（中間）O(n)シフトが必要

学んだこと・ハマったポイント

  1. lengthとcapacityの違いを最初理解してなかった

    • capacity: 配列の最大サイズ
    • length: 実際に使ってる要素数

  2. シフト操作の向きでよく間違えた

    • 挿入時：後ろから前にシフト
    • 削除時：前から後ろにシフト

  3. 境界チェックを忘れがち

    • 必ずindexの範囲チェックをする
    • 配列が満杯かチェックする

  4. なぜ静的配列を使うのか

    • メモリ使用量が予測可能
    • 動的配列より若干高速（リサイズがない）
    • 組み込みシステムでは必須

実際の面接問題での使い方

# Two Sum問題で静的配列を使う
def two_sum(nums, target):
    # ハッシュテーブルの代わりに配列を使う（値の範囲が限定的な場合）
    seen = [False] * 10001  # 値の範囲が0-10000と仮定
    
    for num in nums:
        complement = target - num
        if 0 <= complement <= 10000 and seen[complement]:
            return True
        if 0 <= num <= 10000:
            seen[num] = True
    
    return False

まとめ

次は動的配列がどうやってサイズを変えるか見ていく

Tags: 配列 静的配列