配列と文字列（導入）

配列と文字列

コーディング面接において最も活用されるデータ構造ではないでしょうか？配列とは、複数の値を連続的に格納するためのデータ構造です。これらの値は通常、同じ型（例えば、全て整数や全ての文字列）を持ち、それぞれが固有のインデックスまたはキーによってアクセスされます。また文字列は、文字の配列と考えることができるので、これらは同一視して考えても問題ありません。

特徴

要素はメモリ上に連続して配置されます

要素はメモリ上に連続して配置されているので、メモリ配置の順序にデータにアクセス（シーケンシャルアクセス）した際のキャッシュ効率を向上を期待できる（キャッシュメモリは、アクセスされたデータの近くにあるデータも一緒に読み込む傾向がある）

インデックスを使って任意の要素に高速にアクセスできます。これをランダムアクセスと呼びます（の時間計算量）

配列のサイズは初期化時に固定され、その後は変更できません。多くのプログラミング言語では、動的なサイズ調整をサポートするために動的配列を使用することはありますが、これは裏側で新しい配列を作成し、既存の要素を新しい配列にコピーすることによって行われます。

計算量

Operation	Average Time Complexity	Worst Time Complexity
Search
Insert
Insert (at the end)
Remove
Remove (at the end)

Search（探索）

配列内の特定の要素を探す操作です。最良の場合、探している要素が最初に位置していれば、時間計算量はとなります。しかし、平均・最悪の場合（つまり、探している要素が配列の最後にあるか、存在しない場合）時間計算量は)となります。これは、N個の要素すべてを探索する必要があるためです。

Searchの擬似コード


def search(arr: int[], target: int, length: int):
    for i in range(length):
        if arr[i] == target:
            return i
    return -1

Insert（挿入）

配列の任意の位置に新しい要素を挿入する操作です。途中の位置に要素を挿入するのは実は簡単ではありません。これは、要素を挿入するために、その位置から後ろのすべての要素を後ろにシフトする必要があるためです。最悪の場合（つまり、挿入する要素が配列の最初にある場合）時間計算量はです。

Insertの擬似コード


def insert(arr: int[], index: int, value: int, length: int):
    # 最後の要素からindexまで右にシフトする
    for i in range(length-1, index-1, -1):
        arr[i+1] = arr[i]
    arr[index] = value

Insert at the end（最後に挿入）

配列の最後に新しい要素を追加する操作です。これは最良でも最悪でも時間計算量はです。これは、配列の最後はすぐにアクセス可能で、新しい要素を追加するために他の要素を移動する必要がないためです。

Insert at the endの擬似コード


def insert_at_the_end(arr: int[], value: int, length: int):
    # ここではarrのサイズは一旦考えない
    arr[length] = value

Remove（削除）

配列の任意の位置の要素を削除する操作です。挿入と同様に途中の位置に要素を削除するのは簡単ではありません。これは、要素を削除した後、その位置から後ろのすべての要素を前にシフトする必要があるためです。最悪の場合（つまり、挿入する要素が配列の最初にある場合）時間計算量はです。

Removeの擬似コード


def remove(arr: int[], index: int, length):
    # 消したい要素のindex+1から最後まで左に要素をシフトする
    for index in range(index + 1, length):
        arr[index - 1] = arr[index]
    # 最後の要素を削除する
    arr[length - 1] = null

Remove at the end（最後を削除）

配列の最後の要素を削除する操作です。これは最良でも最悪でも時間計算量はです。これは、最後の要素はすぐにアクセス可能で、削除後に他の要素を移動する必要がないためです。

Remove at the endの擬似コード


def remove_at_the_end(arr: int[], length: int):
    if length > 0:
        # 最後の要素を削除する
        arr[length - 1] = null

動的配列（Dynamic Array）

動的配列は動的にサイズが変更できる配列です。普通の配列は静的配列でサイズが固定されており、宣言時にそのサイズを指定する必要があります。一方、動的配列は要素が追加または削除されると自動的にサイズが調整されます。

多くのプログラミング言語、例えばPython、JavaScriptなどでは配列はデフォルトで動的です。なので多くのエンジニアは配列のサイズを気にする事なく活用する事ができます。

JavaのArrayListと呼ばれるクラスがこの実装になっています。初期状態でArrayListは、一部の要素を保持するための小さな配列（デフォルトでは10要素）を確保します。新しい要素がArrayListに追加されると、その要素は内部配列に格納されます。閾値に達すると、内部的に新しい容量で新しい内部配列を作成し、古い内部配列から新しい内部配列にすべての古い要素をコピーします。

例えば擬似コードで書くと以下のような実装になっています。


# 配列の最後の位置に要素を挿入する
def append(self, value: int):
    # 配列が既に全て埋まっている場合は、サイズを拡張する
    if self.length == self.capacity:
        self.resize()
        
    # 次の空いている位置に要素を挿入します
    self.arr[self.length] = value
    self.length += 1

def resize(self):
   # サイズを2倍にした新しい配列を作成します
   self.capacity = 2 * self.capacity
   newArr = [0] * self.capacity 

   # 既存の全ての要素を新しい配列にコピーします
   for i in range(self.length):
       newArr[i] = self.arr[i]
   self.arr = newArr

このリサイズはの時間計算量となりますが、appendメソッドはの時間計算量にはなりません。何故ならリサイズは毎回行われるわけではないからです。大部分の要素の追加操作（ArrayListがまだ拡大できる場合）はO(1)です。そのため、これらの軽い操作と稀に発生する重い操作を全体として考えると、要素を追加する操作の「平均的な」時間計算量は実際にはとなります。計算量とBigOにも書きましたが、これはならし（amortized）計算量という考え方です。

Pythonでの使い方

Pythonでは配列はリストという名前で実装されています（ややこしい）。また動的配列となっているので、要素の追加や削除がされるとる配列のサイズを変更します。より詳しく知りたい方は次のPythonのデータ構造と内部実装〜List編〜 - Qiitaをご覧下さい。


# リストの作成
array = [1, 2, 3, 4, 5]

# リストへの要素の追加 (O(1))
array.append(6)  # array: [1, 2, 3, 4, 5, 6]

# リストの特定位置への要素の挿入 (O(n) - n is the number of elements to shift)
array.insert(0, 0)  # array: [0, 1, 2, 3, 4, 5, 6]

# リストからの要素の削除 (O(n) - n is the number of elements to shift)
array.remove(3)  # array: [0, 1, 2, 4, 5, 6]

# リストの特定のインデックスの要素の取得 (O(1))
print(array[2])  # Output: 2

# リストの長さの取得 (O(1))
print(len(array))  # Output: 6

# リストから最後の要素を削除 (O(1))
last_element = array.pop()  # last_element: 6, array: [0, 1, 2, 4, 5]

文字列はそのまま文字列型として扱います。


# 文字列の作成
string = "Hello, World!"

# 文字列の連結 (O(n+m) - n and m are lengths of the strings)
string += " How are you?"  # string: "Hello, World! How are you?"

# 文字列の特定のインデックスの文字の取得 (O(1))
print(string[0])  # Output: 'H'

# 文字列の長さの取得 (O(1))
print(len(string))  # Output: 29

# 文字列の分割 (O(n) - n is the number of characters in the string)
print(string.split(' '))  # Output: ['Hello,', 'World!', 'How', 'are', 'you?']

Pythonの文字列はイミュータブル（変更不可）であるため、一度作成した文字列は直接編集することはできません。JavaのStringBuilderのような要素はないので、listとjoinを活用する事で文字列の連結時の時間計算量をにする事ができます。


class StringBuilder:
    def __init__(self):
        self._strings = []

    def append(self, string):
        self._strings.append(string)

    def to_string(self):
        return "".join(self._strings)

sb = StringBuilder()
# 文字列の連結 (O(1))
sb.append("Hello, ")
# 文字列の連結 (O(1))
sb.append("World!")
print(sb.to_string())  # Output: "Hello, World!"

📔

本書に掲載されているLeetCode問題集

📖

ハッシュテーブル（導入）