こんにちはヤク学長です。
データサイエンティスト兼ファーマシストで、アルゴリズムやBI開発を行っています。
本記事の目的は、「アルゴリズムの基本を知る」ことを目的としています。
【本記事のもくじ】
下記の方法で、簡単に概要を抑えることができます。
- １．リンクリストとは
それでは、上から順番に見ていきます。
なお、本上記の方法を順番に抑えれば成果が出ます。
記事の内容は「転載 & 引用OK」問題ありません。
１．リンクリストとは
リンクリストとは
リンクリストは、データ構造の一種で、データを一列に並べたリスト構造です。要素は、前後の要素とのリンクを持つノードとして表されます。各ノードには、データ本体と次のノードへのポインタが含まれます。最初のノードを指すポインタは、通常、リストの先頭を示すものとされます。リストの最後には、次のノードへのポインタがnull値に設定された特別なノードがあります。
リンクリストは、以下のような特徴があります。
- 挿入、削除が高速に行える。
- 検索には時間がかかる。
- 要素の挿入や削除時に、ポインタのつなぎ替えが必要となる。
リンクリストは、連続したメモリ領域を必要としないため、動的なデータの追加や削除が頻繁に行われる場合や、データのサイズが可変の場合に有効です。ただし、ポインタの参照により、メモリ使用量が増えるというデメリットがあります。また、要素の検索が遅いため、ソートされたリストを使用する場合は、バイナリサーチなどの検索速度の高速なアルゴリズムが必要です。
リンクリストは、一般的には、単方向リンクリスト、双方向リンクリスト、環状リンクリストの3つの種類があります。単方向リンクリストは、次のノードへのポインタしか持たず、双方向リンクリストは、次のノードと前のノードの両方へのポインタを持ちます。環状リンクリストは、最後のノードが最初のノードを参照することで、リストの先頭と末尾が繋がった構造を持ちます。
どんな時につかう？
リンクリストは、次のような場合に使用することが多いです。
-
データの挿入、削除が頻繁に行われる場合
リンクリストは、ポインタのつなぎ替えにより要素の挿入、削除が高速に行えるため、要素の追加や削除が頻繁に行われる場合に有効です。 -
データのサイズが可変の場合
リンクリストは、各ノードにデータを持ち、ポインタでつながるため、データのサイズが可変の場合に適しています。例えば、文字列のリストなど、要素のサイズが異なる場合に使用することができます。 -
静的な配列を使用するとメモリ不足になる場合
リンクリストは、ノードごとにメモリを割り当てるため、動的にメモリを確保することができます。そのため、静的な配列を使用するとメモリ不足になる場合に有効です。 -
データが順序付けられていない場合
リンクリストは、要素をリンクでつなぐため、データが順序付けられていなくても使用することができます。そのため、データがランダムな場合や、順序付けが必要でない場合に使用することができます。
一方、リンクリストは、次のような場合にはあまり適していません。
-
データの検索が頻繁に行われる場合
リンクリストは、要素の検索に時間がかかるため、データの検索が頻繁に行われる場合には、バイナリサーチなどの検索速度の高速なアルゴリズムが必要になります。 -
データのサイズが固定の場合
リンクリストは、各ノードにポインタを持つため、データのサイズが固定の場合、要素を連続したメモリ領域に格納する配列の方が効率的です。 -
メモリ使用量を節約する必要がある場合
リンクリストは、各ノードにポインタを持つため、メモリ使用量が大きくなります。メモリ使用量を節約する必要がある場合には、静的な配列を使用する方が効率的です。
シンプルな例
以下は、Pythonでのシンプルなリンクリストの実装例です。
class Node:
"""
リンクリストのノードを表すクラス
"""
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
"""
リンクリストを表すクラス
"""
def __init__(self):
self.head = None
def append(self, data):
"""
リストの末尾に要素を追加する関数
"""
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = new_node
def delete(self, data):
"""
指定した要素を削除する関数
"""
if self.head is None:
return
if self.head.data == data:
self.head = self.head.next
return
current_node = self.head
while current_node.next is not None:
if current_node.next.data == data:
current_node.next = current_node.next.next
return
current_node = current_node.next
def search(self, data):
"""
指定した要素を検索する関数
"""
current_node = self.head
while current_node is not None:
if current_node.data == data:
return True
current_node = current_node.next
return False
# 実行例
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
print(linked_list.search(2)) # True
linked_list.delete(2)
print(linked_list.search(2)) # False
この実装では、Nodeクラスを定義して、データと次のノードへのポインタを持つノードを作成します。LinkedListクラスでは、リストの先頭を示すheadを初期化し、append()メソッドでリストの末尾に要素を追加し、delete()メソッドで指定した要素を削除する処理を実装しています。また、search()メソッドでは、指定した要素を検索する処理を実装しています。この実装は、Pythonにおける基本的なリンクリストの実装例です。
単方向リンクリスト
class Node:
"""
リンクリストのノードを表すクラス
"""
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
"""
リンクリストを表すクラス
"""
def __init__(self):
self.head = None
def append(self, data):
"""
リストの末尾に要素を追加する関数
"""
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = new_node
def delete(self, data):
"""
指定した要素を削除する関数
"""
if self.head is None:
return
if self.head.data == data:
self.head = self.head.next
return
current_node = self.head
while current_node.next is not None:
if current_node.next.data == data:
current_node.next = current_node.next.next
return
current_node = current_node.next
def search(self, data):
"""
指定した要素を検索する関数
"""
current_node = self.head
while current_node is not None:
if current_node.data == data:
return True
current_node = current_node.next
return False
# 実行例
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
print(linked_list.search(2)) # True
linked_list.delete(2)
print(linked_list.search(2)) # False
この実装では、Nodeクラスを定義して、データと次のノードへのポインタを持つノードを作成します。LinkedListクラスでは、リストの先頭を示すheadを初期化し、append()メソッドでリストの末尾に要素を追加し、delete()メソッドで指定した要素を削除する処理を実装しています。また、search()メソッドでは、指定した要素を検索する処理を実装しています。この実装は、Pythonにおける基本的な単方向リンクリストの実装例です。
単方向リンクリストを逆方向に並び替える
単方向リンクリストを逆方向に並び替えるには、各ノードのnextポインタを逆方向につなぎ替える必要があります。具体的には、次のような手順で逆方向に並び替えることができます。
- リストの最初のノードを新しいリストの末尾に設定します。
- 次のノードを新しいリストの先頭に挿入し、その次のノードを新しいリストの先頭に挿入し、この操作をリストの最後のノードまで繰り返します。
- つまり、元のリストの各ノードを、新しいリストの先頭に挿入していきます。
以下は、Pythonでの単方向リンクリストを逆方向に並び替える例です。
class Node:
"""
リンクリストのノードを表すクラス
"""
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
"""
リンクリストを表すクラス
"""
def __init__(self):
self.head = None
def append(self, data):
"""
リストの末尾に要素を追加する関数
"""
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = new_node
def reverse(self):
"""
リストを逆方向に並び替える関数
"""
new_head = None
current_node = self.head
while current_node is not None:
next_node = current_node.next
current_node.next = new_head
new_head = current_node
current_node = next_node
self.head = new_head
def __str__(self):
"""
リストを文字列として表示する関数
"""
result = []
current_node = self.head
while current_node is not None:
result.append(str(current_node.data))
current_node = current_node.next
return " -> ".join(result)
# 実行例
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
print(linked_list) # 1 -> 2 -> 3
linked_list.reverse()
print(linked_list) # 3 -> 2 -> 1
この実装では、reverse()メソッドでリストを逆方向に並び替える処理を実装しています。具体的には、新しいリストの先頭を示すnew_headを初期化し、元のリストの先頭を示すcurrent_nodeを順次辿りながら、各ノードのnextポインタを逆方向につなぎ替えていきます
偶数のものだけを並び替える
単方向リンクリストから偶数の要素だけを抽出し、偶数の要素だけを並び替えるには、次のような手順で行うことができます。
- 空のリストを作成します。これは、偶数の要素を追加するための新しいリストです。
- もとのリストを順番に辿りながら、各ノードのデータが偶数である場合、新しいリストの末尾に追加します。
- 偶数の要素が新しいリストに追加されたら、新しいリストをソートします。これにより、偶数の要素だけが並び替えられます。
- もとのリストを順番に辿りながら、偶数の要素があった場合、新しいリストから偶数の要素を削除し、元のリストに追加します。
以下は、Pythonでの単方向リンクリストから偶数の要素だけを並び替える例です。
class Node:
"""
リンクリストのノードを表すクラス
"""
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
"""
リンクリストを表すクラス
"""
def __init__(self):
self.head = None
def append(self, data):
"""
リストの末尾に要素を追加する関数
"""
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = new_node
def even_sort(self):
"""
偶数の要素だけを並び替える関数
"""
even_list = LinkedList()
current_node = self.head
# もとのリストから偶数の要素を抽出し、even_listに追加
while current_node is not None:
if current_node.data % 2 == 0:
even_list.append(current_node.data)
current_node = current_node.next
# even_listをソートする
sorted_list = sorted(even_list, reverse=True)
# もとのリストから偶数の要素を削除し、sorted_listから追加する
current_node = self.head
prev_node = None
while current_node is not None:
if current_node.data % 2 == 0:
if prev_node is None:
self.head = current_node.next
else:
prev_node.next = current_node.next
current_node.next = None
if len(sorted_list) > 0:
new_node = Node(sorted_list.pop())
if self.head is None:
self.head = new_node
else:
new_node.next = self.head
self.head = new_node
current_node = prev_node.next
以上の実装では、even_sort()メソッドでリストから偶数の要素だけを抽出し、even_listに追加しています。その後、sorted()関数を使ってeven_listを逆順にソートし、sorted_listに格納しています。
その後、元のリストを辿りながら、偶数の要素がある場合には、その要素を元のリストから削除し、sorted_listから偶数の要素を取り出して元のリストに追加していきます。
この実装では、リストから要素を削除したり、要素を追加したりするため、単方向リンクリストよりも双方向リンクリストを使った方が実装が簡単になります。しかし、双方向リンクリストを使った場合でも、基本的なアルゴリズムは同じです。
双方向リンクリスト
双方向リンクリストは、単方向リンクリストのように前方向への参照（prev）と次方向への参照（next）の両方を持ちます。このため、双方向リンクリストでは、リスト内の要素を前方向からも後方向からもアクセスできるようになっています。
双方向リンクリストでは、単方向リンクリストと同様にノードと呼ばれるオブジェクトがリストの要素を表します。ノードには、データを格納するdata属性、前方向の参照を格納するprev属性、次方向の参照を格納するnext属性があります。
双方向リンクリストにおいて、各ノードの前方向の参照と次方向の参照は、以下のように相互に参照し合うようになっています。
prev <--- [data, prev, next] ---> next双方向リンクリストにおいて、最初のノードはhead属性で示され、最後のノードはtail属性で示されます。head属性とtail属性は、それぞれ先頭と末尾のノードへの参照を保持しています。
以下は、Pythonでの双方向リンクリストの実装例です。
class Node:
"""
リンクリストのノードを表すクラス
"""
def __init__(self, data=None):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
"""
双方向リンクリストを表すクラス
"""
def __init__(self):
self.head = None
self.tail = None
def append(self, data):
"""
リストの末尾に要素を追加する関数
"""
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
def __str__(self):
"""
リストを文字列として表示する関数
"""
result = []
current_node = self.head
while current_node is not None:
result.append(str(current_node.data))
current_node = current_node.next
return " <-> ".join(result)
この実装では、Nodeクラスでprev属性を追加して、双方向の参照を表現しています。また、DoublyLinkedListクラスでは、head属性とtail属性を追加して、先頭と末尾のノードへの参照を保持しています。append()メソッドでは、新しいノードを追加する際に、prev属性とnext属性を使って前方向への参照と次方向への参照を双方向リンクリストでは、単方向リンクリストと比べて要素の追加や削除が複雑になりますが、要素の並び替えや逆順へのアクセスが簡単になるという利点があります。また、双方向リンクリストは、スタックやキューのようなデータ構造を実装する際にもよく使われます。
双方向リンクリストを逆方向に並び替える
双方向リンクリストを逆方向に並び替える場合は、prev属性とnext属性を入れ替えることで実現できます。具体的には、以下のように実装します。
class DoublyLinkedList:
...
def reverse(self):
"""
リストを逆順にする関数
"""
current_node = self.head
while current_node is not None:
# prev属性とnext属性を入れ替える
current_node.prev, current_node.next = current_node.next, current_node.prev
# 現在のノードを次のノードに移す
current_node = current_node.prev
# head属性とtail属性を入れ替える
self.head, self.tail = self.tail, self.head
この実装では、reverse()メソッドでリストを逆順にしています。具体的には、current_nodeを先頭のノードに設定し、prev属性とnext属性を入れ替えながらリストを辿ります。そして、head属性とtail属性を入れ替えることで、先頭と末尾のノードへの参照を正しく設定します。
注意点としては、逆方向に並び替える際には、prev属性とnext属性を同時に入れ替える必要があるため、一時的な変数を使うことはできません。また、head属性とtail属性を入れ替えた場合は、リスト内の要素の順序が逆になるため、それに対応するように各ノードのprev属性とnext属性も入れ替える必要があります。
双方向リストをソートする
双方向リストをソートする場合は、通常のソートアルゴリズムと同様に、ノードのデータを比較しながら適切な位置に挿入していく方法が一般的です。
以下は、バブルソートを使って双方向リストをソートする実装例です。
class DoublyLinkedList:
...
def bubble_sort(self):
"""
バブルソートを使ってリストをソートする関数
"""
current_node = self.head
while current_node is not None:
next_node = current_node.next
while next_node is not None:
if current_node.data > next_node.data:
# ノードのデータを入れ替える
current_node.data, next_node.data = next_node.data, current_node.data
next_node = next_node.next
current_node = current_node.nextこの実装では、bubble_sort()メソッドでバブルソートを使ってリストをソートしています。具体的には、current_nodeを先頭のノードに設定し、各ノードのデータを比較しながらリストを辿り、適切な位置に挿入していきます。バブルソートは、ソートする要素が少ない場合には高速ですが、要素数が多い場合には処理時間が長くなるため、より高速なソートアルゴリズムを使った方が良い場合があります。また、今回は昇順でソートしていますが、降順でソートする場合は、比較演算子を逆にすれば良いです。
というわけで、今回は以上です。大変大変お疲れ様でした。
引き続きで、徐々に発信していきます。
コメントや感想を受け付けています。ちょっとした感想でもいいので嬉しいです。
それでは、以上です。
