Python開発入門19 ArrayとLinked Listの違い

Python

はじめに

プログラミングで効率的なデータ処理を行うためには、適切なデータ構造を選ぶことが重要です。ArrayとLinked Listは、データを格納するための基本的なデータ構造ですが、それぞれ異なる特徴と用途があります。

この記事では、PythonでArrayとLinked Listの基本から応用までを解説します。特に、以下の点に焦点を当てています：

  • ArrayとLinked Listの基礎知識
  • それぞれの利点と欠点
  • Pythonでの実装方法
  • 適切なデータ構造の選び方

初心者でも理解しやすい具体例を交えていますので、ぜひ参考にしてください！

Arrayの基礎

Arrayとは？

Arrayは、同じ型のデータを連続したメモリ領域に格納するデータ構造です。Pythonでは、リスト（list）が動的配列として使用されるほか、arrayモジュールやnumpyライブラリを使用してよりメモリ効率の高い配列を操作することも可能です。

Arrayの特徴

  1. 固定長または可変長
    • Pythonのリストは可変長ですが、arrayモジュールやnumpy配列では通常固定長が使用されます。
  2. インデックスによる高速アクセス
    • Array内の要素は、インデックスを指定してO(1)でアクセス可能です。
  3. 連続したメモリ配置
    • Arrayはメモリ上で連続して格納されるため、キャッシュ効率が高いです。

PythonでのArrayの実装

1. リストを使った配列

Pythonのリストは最も一般的な動的配列です。

numbers = [10, 20, 30, 40]
print(numbers[2])  # 出力: 30

2. arrayモジュールを使用した配列

型が固定され、メモリ効率が向上します

import array

numbers = array.array('i', [10, 20, 30, 40])  # 'i'は整数型
print(numbers[2])  # 出力: 30

3. numpyを使用した配列

科学計算や大規模データ処理に最適です。

import numpy as np

numbers = np.array([10, 20, 30, 40])
print(numbers[2])  # 出力: 30

Linked Listの基礎

Linked Listとは？

Linked Listは、データ要素（ノード）と、次のノードへのポインタで構成されるデータ構造です。各ノードは分散してメモリに格納されており、柔軟なサイズ変更が可能です。

Linked Listの種類

  1. Singly Linked List
    各ノードが次のノードへのポインタを持つ構造です。
  2. Doubly Linked List
    各ノードが次と前のノードへのポインタを持つ構造です。
  3. Circular Linked List
    最後のノードが最初のノードを指すように構成されるリンクリストです。

Linked Listの特徴

  1. 動的なサイズ変更
    ノードを追加または削除することで、Linked Listのサイズを柔軟に変更できます。
  2. 分散したメモリ配置
    ノードが連続して格納される必要がないため、大規模データの操作に適しています。
  3. ランダムアクセスが非効率
    要素を探すにはリストを順番にたどる必要があるため、O(n)の時間がかかります。

PythonでのLinked Listの実装

Singly Linked Listの例

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.value, end=" -> ")
            current = current.next
        print("None")

# 使用例
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display()  # 出力: 10 -> 20 -> 30 -> None

Doubly Linked Listの例

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.prev = current

    def display(self):
        current = self.head
        while current:
            print(current.value, end=" <-> ")
            current = current.next
        print("None")

# 使用例
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.display()  # 出力: 10 <-> 20 <-> 30 <-> None

ArrayとLinked Listの比較

特徴の違い

特徴ArrayLinked List
メモリ配置連続したメモリ配置分散したメモリ配置
アクセス速度O(1)（インデックスによるアクセスが可能）O(n)（順にたどる必要がある）
挿入と削除O(n)（要素をシフトする必要がある場合）O(1)（ポインタ操作のみ）
サイズの柔軟性固定または可変非常に柔軟

用途別の選び方

Arrayを選ぶべき場面

  • 要素へのランダムアクセスが頻繁に必要な場合。
  • メモリ効率が重要な場合。
  • データが固定サイズの場合。

Linked Listを選ぶべき場面

  • 要素の挿入と削除が頻繁に発生する場合。
  • データ量が動的に増減する可能性がある場合。
  • 順次アクセスが多い場合。

まとめ

ArrayとLinked Listは、それぞれ異なる特性を持つデータ構造です。配列は高速なアクセスとメモリ効率を提供する一方で、リンクリストは柔軟性と効率的な挿入・削除を可能にします。

プログラムの要件に応じて適切なデータ構造を選択することで、効率的なコードを書くことができます。Pythonでは、配列にリストやnumpy、リンクリストにカスタム実装が用意されているため、目的に応じて適切に使い分けましょう。

コメント