4.3 リスト¶
リストは、要素へのアクセス、変更、追加、削除、走査などの操作をサポートする、順序付けられた要素のコレクションを表す抽象的なデータ構造の概念であり、ユーザーが容量制限を考慮する必要がありません。リストは連結リストまたは配列に基づいて実装できます。
- 連結リストは本質的にリストとして機能し、要素の追加、削除、検索、変更の操作をサポートし、サイズを動的に調整する柔軟性があります。
- 配列もこれらの操作をサポートしますが、長さが不変であるため、長さ制限のあるリストと考えることができます。
配列を使用してリストを実装する場合、長さの不変性によりリストの実用性が低下します。これは、事前に格納するデータ量を予測することが困難な場合が多く、適切なリスト長を選択することが困難であるためです。長さが小さすぎると要件を満たさない可能性があり、大きすぎるとメモリ空間を無駄にする可能性があります。
この問題を解決するために、動的配列を使用してリストを実装できます。これは配列の利点を継承し、プログラム実行中に動的に拡張できます。
実際、多くのプログラミング言語の標準ライブラリは動的配列を使用してリストを実装しています。例えば、Pythonのlist、JavaのArrayList、C++のvector、C#のListなどです。以下の議論では、「リスト」と「動的配列」を同義の概念として扱います。
4.3.1 リストの一般的な操作¶
1. リストの初期化¶
通常、「初期値なし」と「初期値あり」の2つの初期化方法を使用します。
2. 要素へのアクセス¶
リストは本質的に配列であるため、\(O(1)\)時間で要素にアクセスし更新することができ、非常に効率的です。
3. 要素の挿入と削除¶
配列と比較して、リストは要素の追加と削除においてより柔軟性を提供します。リストの末尾への要素追加は\(O(1)\)操作ですが、リストの他の場所での要素の挿入と削除の効率は配列と同じままで、時間計算量は\(O(n)\)です。
list_test.go
/* リストをクリア */
nums = nil
/* 末尾に要素を追加 */
nums = append(nums, 1)
nums = append(nums, 3)
nums = append(nums, 2)
nums = append(nums, 5)
nums = append(nums, 4)
/* 中間に要素を挿入 */
nums = append(nums[:3], append([]int{6}, nums[3:]...)...) // インデックス3に数値6を挿入
/* 要素を削除 */
nums = append(nums[:3], nums[4:]...) // インデックス3の要素を削除
4. リストの反復¶
配列と同様に、リストはインデックスを使用して反復することも、各要素を直接反復することもできます。
5. リストの連結¶
新しいリストnums1が与えられたとき、それを元のリストの末尾に追加できます。
6. リストのソート¶
リストがソートされると、「二分探索」や「双ポインタ」アルゴリズムなど、配列関連のアルゴリズム問題でよく使用されるアルゴリズムを使用できます。
4.3.2 リストの実装¶
多くのプログラミング言語には、Java、C++、Pythonなどを含む組み込みリストが付属しています。それらの実装は、初期容量や拡張係数などの様々なパラメータを慎重に考慮した設定で、複雑になりがちです。興味のある読者は、さらなる学習のためにソースコードを調べることができます。
リストがどのように動作するかの理解を深めるために、3つの重要な設計側面に焦点を当てて、簡略化されたリストの実装を試みます：
- 初期容量：配列に合理的な初期容量を選択します。この例では、初期容量として10を選択します。
- サイズ記録：リスト内の現在の要素数を記録する変数
sizeを宣言し、要素の挿入と削除でリアルタイムに更新します。この変数により、リストの末尾を特定し、拡張が必要かどうかを判断できます。 - 拡張メカニズム：要素挿入時にリストが満杯に達した場合、拡張プロセスが必要です。これには拡張係数に基づいてより大きな配列を作成し、現在の配列からすべての要素を新しい配列に転送することが含まれます。この例では、拡張のたびに配列サイズを2倍にすることを規定します。
my_list.py
class MyList:
"""リストクラス"""
def __init__(self):
"""コンストラクタ"""
self._capacity: int = 10 # リストの容量
self._arr: list[int] = [0] * self._capacity # 配列（リスト要素を格納）
self._size: int = 0 # リストの長さ（現在の要素数）
self._extend_ratio: int = 2 # 各リスト拡張の倍数
def size(self) -> int:
"""リストの長さ（現在の要素数）を取得"""
return self._size
def capacity(self) -> int:
"""リストの容量を取得"""
return self._capacity
def get(self, index: int) -> int:
"""要素にアクセス"""
# インデックスが範囲外の場合、以下のように例外をスロー
if index < 0 or index >= self._size:
raise IndexError("Index out of bounds")
return self._arr[index]
def set(self, num: int, index: int):
"""要素を更新"""
if index < 0 or index >= self._size:
raise IndexError("Index out of bounds")
self._arr[index] = num
def add(self, num: int):
"""末尾に要素を追加"""
# 要素数が容量を超える場合、拡張メカニズムをトリガー
if self.size() == self.capacity():
self.extend_capacity()
self._arr[self._size] = num
self._size += 1
def insert(self, num: int, index: int):
"""中間に要素を挿入"""
if index < 0 or index >= self._size:
raise IndexError("Index out of bounds")
# 要素数が容量を超える場合、拡張メカニズムをトリガー
if self._size == self.capacity():
self.extend_capacity()
# インデックス index より後のすべての要素を1つ後ろに移動
for j in range(self._size - 1, index - 1, -1):
self._arr[j + 1] = self._arr[j]
self._arr[index] = num
# 要素数を更新
self._size += 1
def remove(self, index: int) -> int:
"""要素を削除"""
if index < 0 or index >= self._size:
raise IndexError("Index out of bounds")
num = self._arr[index]
# インデックス index より後のすべての要素を1つ前に移動
for j in range(index, self._size - 1):
self._arr[j] = self._arr[j + 1]
# 要素数を更新
self._size -= 1
# 削除された要素を返す
return num
def extend_capacity(self):
"""リストを拡張"""
# 元の配列の _extend_ratio 倍の長さの新しい配列を作成し、元の配列を新しい配列にコピー
self._arr = self._arr + [0] * self.capacity() * (self._extend_ratio - 1)
# リストの容量を更新
self._capacity = len(self._arr)
def to_array(self) -> list[int]:
"""有効な長さのリストを返す"""
return self._arr[: self._size]
my_list.cpp
/* リストクラス */
class MyList {
private:
int *arr; // 配列（リスト要素を格納）
int arrCapacity = 10; // リストの容量
int arrSize = 0; // リストの長さ（現在の要素数）
int extendRatio = 2; // リスト拡張時の倍率
public:
/* コンストラクタ */
MyList() {
arr = new int[arrCapacity];
}
/* デストラクタ */
~MyList() {
delete[] arr;
}
/* リストの長さを取得（現在の要素数）*/
int size() {
return arrSize;
}
/* リストの容量を取得 */
int capacity() {
return arrCapacity;
}
/* 要素にアクセス */
int get(int index) {
// インデックスが範囲外の場合、例外をスロー（以下同様）
if (index < 0 || index >= size())
throw out_of_range("Index out of bounds");
return arr[index];
}
/* 要素を更新 */
void set(int index, int num) {
if (index < 0 || index >= size())
throw out_of_range("Index out of bounds");
arr[index] = num;
}
/* 末尾に要素を追加 */
void add(int num) {
// 要素数が容量を超えた場合、拡張メカニズムをトリガー
if (size() == capacity())
extendCapacity();
arr[size()] = num;
// 要素数を更新
arrSize++;
}
/* 中間に要素を挿入 */
void insert(int index, int num) {
if (index < 0 || index >= size())
throw out_of_range("Index out of bounds");
// 要素数が容量を超えた場合、拡張メカニズムをトリガー
if (size() == capacity())
extendCapacity();
// `index`より後のすべての要素を1つ後ろに移動
for (int j = size() - 1; j >= index; j--) {
arr[j + 1] = arr[j];
}
arr[index] = num;
// 要素数を更新
arrSize++;
}
/* 要素を削除 */
int remove(int index) {
if (index < 0 || index >= size())
throw out_of_range("Index out of bounds");
int num = arr[index];
// `index`より後のすべての要素を1つ前に移動
for (int j = index; j < size() - 1; j++) {
arr[j] = arr[j + 1];
}
// 要素数を更新
arrSize--;
// 削除された要素を返却
return num;
}
/* リストを拡張 */
void extendCapacity() {
// 元の配列のextendRatio倍の長さで新しい配列を作成
int newCapacity = capacity() * extendRatio;
int *tmp = arr;
arr = new int[newCapacity];
// 元の配列のすべての要素を新しい配列にコピー
for (int i = 0; i < size(); i++) {
arr[i] = tmp[i];
}
// メモリを解放
delete[] tmp;
arrCapacity = newCapacity;
}
/* リストをVectorに変換して印刷用に使用 */
vector<int> toVector() {
// 有効な長さ範囲内の要素のみを変換
vector<int> vec(size());
for (int i = 0; i < size(); i++) {
vec[i] = arr[i];
}
return vec;
}
};
my_list.java
/* リストクラス */
class MyList {
private int[] arr; // 配列（リスト要素を格納）
private int capacity = 10; // リスト容量
private int size = 0; // リスト長（現在の要素数）
private int extendRatio = 2; // リストの各拡張倍率
/* コンストラクタ */
public MyList() {
arr = new int[capacity];
}
/* リスト長を取得（現在の要素数） */
public int size() {
return size;
}
/* リスト容量を取得 */
public int capacity() {
return capacity;
}
/* 要素へのアクセス */
public int get(int index) {
// インデックスが範囲外の場合、以下のように例外をスロー
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("インデックスが範囲外です");
return arr[index];
}
/* 要素の更新 */
public void set(int index, int num) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("インデックスが範囲外です");
arr[index] = num;
}
/* 末尾に要素を追加 */
public void add(int num) {
// 要素数が容量を超える場合、拡張メカニズムを実行
if (size == capacity())
extendCapacity();
arr[size] = num;
// 要素数を更新
size++;
}
/* 中間に要素を挿入 */
public void insert(int index, int num) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("インデックスが範囲外です");
// 要素数が容量を超える場合、拡張メカニズムを実行
if (size == capacity())
extendCapacity();
// `index` より後のすべての要素を1つ後ろに移動
for (int j = size - 1; j >= index; j--) {
arr[j + 1] = arr[j];
}
arr[index] = num;
// 要素数を更新
size++;
}
/* 要素の削除 */
public int remove(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("インデックスが範囲外です");
int num = arr[index];
// `index` より後のすべての要素を1つ前に移動
for (int j = index; j < size - 1; j++) {
arr[j] = arr[j + 1];
}
// 要素数を更新
size--;
// 削除された要素を返す
return num;
}
/* リストを拡張 */
public void extendCapacity() {
// 元の配列の長さを extendRatio 倍した新しい配列を作成し、元の配列を新しい配列にコピー
arr = Arrays.copyOf(arr, capacity() * extendRatio);
// リスト容量を更新
capacity = arr.length;
}
/* リストを配列に変換 */
public int[] toArray() {
int size = size();
// 有効な長さ範囲内の要素のみを変換
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = get(i);
}
return arr;
}
}