配列と連結リスト

連続したメモリ領域と参照によるデータ構造の違いを理解する。

配列

連続したメモリ領域にデータを格納するデータ構造。

連結リスト

各要素が次の要素への参照を持つデータ構造。

ノード

連結リストの各要素。データと次のノードへの参照を持つ。

ヘッド

連結リストの最初のノード。

テール

連結リストの最後のノード。

計算量

アルゴリズムの実行時間を表す指標。

配列

本棚

配列は「本棚」のようなもの。本棚の各棚には、連続して本が並んでいます。ある棚の本を取り出すとき、棚番号を指定すれば、すぐに取り出せます。ただし、新しい本を追加するときは、棚の空きを探す必要があります。

なぜ配列が必要か？

配列は、連続したメモリ領域にデータを格納するためのデータ構造です。インデックスによる高速なアクセス、メモリ効率の良さ、実装の容易さなど、多くの利点があります。特に、データの順序が重要で、頻繁なアクセスが必要な場合に適しています。

いつ使うか？

データの順序が重要な場合
頻繁なランダムアクセスが必要な場合
データのサイズが事前に分かっている場合
メモリ効率が重要な場合

実践テクニック

リスト内包表記を活用する

リスト内包表記を使うことで、簡潔で効率的なコードを書くことができます。例：`[x ** 2 for x in arr]` は、各要素を2乗した新しいリストを作成します。

enumerate()を使う

インデックス付きの走査には `enumerate()` 関数を使います。これにより、インデックスと要素の両方にアクセスできます。例：`for index, element in enumerate(arr):`

スライスを活用する

スライスを使うことで、配列の一部を簡単に取り出せます。例：`arr[1:4]` は、インデックス1から3までの要素を取り出します。

計算量を理解する

配列の操作の計算量を理解することは、パフォーマンス最適化に重要です。例：要素へのアクセスはO(1)、要素の削除はO(n)です。これらを理解して、適切なデータ構造を選択します。

1
# 配列の基本操作
2
arr = [1, 2, 3, 4, 5]
3
print(arr[0])  # 1
4
print(arr[2])  # 3
5

6
# 要素の追加
7
arr.append(6)  # [1, 2, 3, 4, 5, 6]
8

9
# 要素の削除
10
arr.remove(3)  # [1, 2, 4, 5, 6]
11

12
# 要素の挿入
13
arr.insert(2, 3)  # [1, 2, 3, 4, 5, 6]
14

15
# 要素の取得
16
print(arr.pop())  # 6
17
print(arr)  # [1, 2, 3, 4, 5]

連結リスト

宝探し

連結リストは「宝探し」のようなもの。各宝箱には、次の宝箱への地図が入っています。ある宝箱を開けると、地図を見て次の宝箱へ移動します。宝箱を追加するときは、最後の宝箱に地図を追加します。

なぜ連結リストが必要か？

連結リストは、各要素が次の要素への参照を持つデータ構造です。動的なサイズ変更、効率的な挿入・削除、メモリの柔軟性など、多くの利点があります。特に、要素の挿入・削除が頻繁な場合に適しています。

いつ使うか？

要素の挿入・削除が頻繁な場合
データのサイズが動的に変わる場合
メモリの断片化を避けたい場合
先頭または末尾への操作が頻繁な場合

実践テクニック

ダミーヘッドを使う

ダミーヘッドを使うことで、挿入・削除のロジックを簡素化できます。ダミーヘッドは、実際のデータを持たず、最初のノードへの参照を持つノードです。

双方向連結リストを検討する

双方向連結リストを使うことで、前後のノードへのアクセスが可能になります。これは、特定の操作（逆走査など）を効率化できます。

計算量を理解する

連結リストの操作の計算量を理解することは、パフォーマンス最適化に重要です。例：要素の追加はO(1)、要素の検索はO(n)です。これらを理解して、適切なデータ構造を選択します。

1
# 連結リストの基本操作
2
class Node:
3
    def __init__(self, data):
4
        self.data = data
5
        self.next = None
6

7
class LinkedList:
8
    def __init__(self):
9
        self.head = None
10

11
    def append(self, data):
12
        new_node = Node(data)
13
        if not self.head:
14
            self.head = new_node
15
            return
16
        current = self.head
17
        while current.next:
18
            current = current.next
19
        current.next = new_node
20

21
    def display(self):
22
        current = self.head
23
        while current:
24
            print(current.data, end=" -> ")
25
            current = current.next
26
        print("None")
27

28
# 使用例
29
ll = LinkedList()
30
ll.append(1)
31
ll.append(2)
32
ll.append(3)
33
ll.display()  # 1 -> 2 -> 3 -> None

走査

配列と連結リストの走査方法を理解する。

1
# 配列の走査
2
arr = [1, 2, 3, 4, 5]
3

4
# for ループ
5
for element in arr:
6
    print(element)
7

8
# インデックス付きの走査
9
for index, element in enumerate(arr):
10
    print(f"Index {index}: {element}")
11

12
# リスト内包表記
13
squared = [x ** 2 for x in arr]
14
print(squared)  # [1, 4, 9, 16, 25]

1
# 連結リストの走査
2
class LinkedList:
3
    def __init__(self):
4
        self.head = None
5

6
    def append(self, data):
7
        new_node = Node(data)
8
        if not self.head:
9
            self.head = new_node
10
            return
11
        current = self.head
12
        while current.next:
13
            current = current.next
14
        current.next = new_node
15

16
    def traverse(self):
17
        current = self.head
18
        while current:
19
            print(current.data)
20
            current = current.next
21

22
# 使用例
23
ll = LinkedList()
24
ll.append(1)
25
ll.append(2)
26
ll.append(3)
27
ll.traverse()  # 1 2 3

計算量

配列と連結リストの操作の計算量を比較する。

1
# 配列の計算量
2
arr = [1, 2, 3, 4, 5]
3

4
# 要素へのアクセス: O(1)
5
print(arr[2])  # 3
6

7
# 要素の追加: O(1)
8
arr.append(6)
9

10
# 要素の削除: O(n)
11
arr.remove(3)
12

13
# 要素の検索: O(n)
14
if 3 in arr:
15
    print("Found")

1
# 連結リストの計算量
2
ll = LinkedList()
3

4
# 要素の追加: O(1)
5
ll.append(1)
6

7
# 要素の削除: O(n)
8
# （削除する要素を探す必要がある）
9

10
# 要素の検索: O(n)
11
# （先頭から順に探す必要がある）
12

13
# 要素へのアクセス: O(n)
14
# （先頭から順にたどる必要がある）

使用例

配列と連結リストの実際の使用例を確認する。

1
# 配列の使用例
2
# データの収集
3
scores = [85, 90, 78, 92, 88]
4

5
# データのフィルタリング
6
high_scores = [score for score in scores if score >= 90]
7
print(high_scores)  # [90, 92]
8

9
# データの変換
10
normalized = [score / 100 for score in scores]
11
print(normalized)  # [0.85, 0.9, 0.78, 0.92, 0.88]
12

13
# データの集計
14
average = sum(scores) / len(scores)
15
print(average)  # 86.6

1
# 連結リストの使用例
2
# 動的なデータの管理
3
ll = LinkedList()
4

5
# 順序を保ったデータの追加
6
ll.append("First")
7
ll.append("Second")
8
ll.append("Third")
9

10
# メモリ効率の良いデータ管理
11
# （要素の削除が頻繁な場合に有利）

比較

配列と連結リストの特徴を比較する。

特徴	配列	連結リスト
メモリレイアウト	連続	非連続
アクセス	O(1) （インデックス）	O(n) （走査）
挿入	O(n)	O(1) （先頭）
削除	O(n)	O(n) （ノード探索）
サイズ変更	固定	動的
メモリ効率	高い	低い

合格ライン

☐ 配列の基本操作ができる

☐ 連結リストの基本操作ができる

☐ 配列と連結リストの走査ができる

☐ 配列と連結リストの計算量を理解している

☐ 配列と連結リストの使い分けができる

演習課題

課題1: 配列の基本操作

配列を作成し、要素を追加・削除・検索するコードを書いてください。

課題2: 連結リストの実装

連結リストクラスを実装し、要素の追加・削除・走査を行うメソッドを作成してください。

課題3: 計算量の比較

配列と連結リストの操作の計算量を比較し、どのような場面でどちらが有利かを説明してください。

参考文献

この記事は以下の公的ガイドライン/標準に基づいています。

Python Data Structures - 公式ドキュメント
list Documentation - list() 関数ドキュメント
Linked Lists in Python - Real Python チュートリアル