配列と連結リスト【Algorithm-Data構造入門Ⅱ】

配列

配列はデータを連続的に格納するデータ構造であり、インデックスを使用して要素にアクセスします。配列は任意の位置へのデータの読み書きが定数時間で行えますが、要素の追加や削除には全体の要素のシフトが必要であり、これによりO(n)の時間がかかります。

Pythonでの配列操作例

# 配列の作成
arr = [1, 2, 3, 4, 5]

# 要素の追加
arr.append(6)

# 先頭に要素を追加（O(n)の時間がかかる）
arr.insert(0, 0)

# 先頭の要素を削除（O(n)の時間がかかる）
arr.pop(0)

配列の操作メソッドについて詳しくはこちらをご覧下さい。

連結リスト

連結リストは、データとポインタを持つノードが連結しているデータ構造です。連結リストでは要素の追加や削除がO(1)の時間で行えますが、要素の探索にはポインタをたどる必要があり、これによりO(n)の時間がかかります。また、連結リストはメモリ使用量が多いという欠点があります。

Pythonでの連結リストの操作例

# ノードと連結リストの定義
# ノードと単方向連結リストの定義
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

	# 先頭に要素を追加
	def add_at_head(self, data):
		new_node = Node(data)
		new_node.next = self.head
		self.head = new_node

	# 末尾に要素を追加
	def add_at_tail(self, data):
		new_node = Node(data)
		if not self.head:
			self.head = new_node
		else:
			current = self.head
			while current.next: # 末尾の要素を探す
				current = current.next
			current.next = new_node

	# 先頭の要素を削除
	def remove_head(self):
		if self.head:
			self.head = self.head.next

	# 末尾の要素を削除
	def remove_tail(self):
		if self.head:
			if not self.head.next: # 要素が1つだけの場合
				self.head = None
			else:
				current = self.head
				while current.next.next: # 末尾の1つ前の要素を探す
					current = current.next
				current.next = None

	# 特定の要素を削除
	def remove(self, data):
		if self.head:
			if self.head.data == data: # 先頭の要素を削除
				self.head = self.head.next
			else:
				current = self.head
				while current.next:
					if current.next.data == data:
						current.next = current.next.next
						break
					current = current.next

	# リストの要素を表示
	def display(self):
		current = self.head
		while current:
			print(current.data, end=" -> ")
			current = current.next
		print("None")

# 連結リストの操作例
ll = LinkedList() # 空の連結リストを作成
ll.add_at_head(3) # 3 -> None
ll.add_at_head(2) # 2 -> 3 -> None
ll.add_at_head(1) # 1 -> 2 -> 3 -> None
ll.display()  # Output: 1 -> 2 -> 3 -> None
ll.add_at_tail(4) # 1 -> 2 -> 3 -> 4 -> None
ll.display()  # Output: 1 -> 2 -> 3 -> 4 -> None
ll.remove_head() # 2 -> 3 -> 4 -> None
ll.display()  # Output: 2 -> 3 -> 4 -> None

まとめ

配列と連結リストは、それぞれ利点と欠点を持ちます。配列はランダムアクセスが高速である一方、要素の追加や削除には時間がかかります。一方、連結リストは要素の追加や削除が効率的であるが、要素の探索には時間がかかり、メモリ使用量も大きくなる可能性があります。適切なデータ構造の選択は、特定の問題やアプリケーションの要件に合わせて行う必要があります。

参考文献