Python でリンクリストを逆にする
![Python でリンクリストを逆にする](/img/Python/feature-image---reverse-linked-list-python.webp)
リンクリストは、要素の一定時間の追加と削除を提供するコンピュータサイエンスの線形データ構造です。ノードで構成されています。
1つのノードには、いくつかのデータと次のノードのアドレスが格納されます。次のノードは、そのデータと次のノードのアドレスを格納します。単一のノードは、それが指しているノードについてのみ知っています。それを指しているノードに関する情報はありません。
この構造により、配列を新しい配列にコピーしたり、配列の要素をシフトして追加と削除の余地を作成したりする必要がある配列とは異なり、新しいノードを追加したり、既存のノードを一定時間で削除したりできます。
配列では、インデックスを使用して一定時間で要素にアクセスできます。ただし、リンクリストの場合、要素にアクセスするのに O(n)
の時間がかかります。ここで、n
はリンクリストの長さです。
リンクリストは構造(線形)の点で配列に似ているため、リンクリストの並べ替え、フィルタリング、検索などの操作も実行できます。バブルソート、挿入ソート、マージソート、クイックソート、選択ソート、バイナリ検索、リンクリストの線形検索などのソートおよび検索アルゴリズムを使用できます。
この記事では、Python を使用してリンクリストを逆にする方法を説明します。コードスニペットは、リンクリストのブロックを表す Node
クラスを考慮していることに注意してください。
Node
クラスは次のようになります。
class Node:
def __init__(self, data):
self.data = data
self.next = None
Python でリンクリストを逆にする
Python でリンクリストを逆にするには、次の Python コードを参照してください。
def reverse(head: Node) -> Node:
previous = None
current = head
next = None
while current is not None:
next = current.next
current.next = previous
previous = current
current = next
head = previous
return head
コードを理解するために、リンクリストの例 1-> 2-> 3-> 4-> 5->なし
を考えてみましょう。
最初に、入力リンクリストの先頭である None
、および None
をそれぞれ指す 3つの変数、previous
、current
、および next
を宣言します。次に、current
ノードが None
を指しているときに終了する while
ループを宣言します。
反復ごとに:
current
ノードの次のノードをnext
ノードに保存します。現在の
ノードの次のノードを前の
ノードに設定します。前の
ノードを現在の
ノードにリセットします。現在の
ノードを次の
ノードにリセットします。
次の表は、上記の例にアルゴリズムを適用したときに、変数の値、つまり前へ
、現在
、および次へ
がどのように変化するかを示しています。
|| previous
| current
| next
|
| ———- | ——— | —— |
| None | 1 | None |
| 1 | 2 | 2 |
| 2 | 3 | 3 |
| 3 | 4 | 4 |
| 4 | 5 | 5 |
| 5 | None | None |
上のテーブルセルには、ノードによって保存されている値が表示されます。