Python でのリンク リストの実装を理解する

データ構造はプログラミングの世界において重要な役割を果たします。これらは、データを効率的に使用できる方法で整理するのに役立ちます。

このチュートリアルでは、 単連結リスト と 二重連結リスト について学びます。

リンク リストは線形データ構造です。配列のように連続したメモリ位置にデータを保存しません。そして、linked の各要素は ノード と呼ばれ、 ポインタを 使用して接続されます。リンクされたリストの最初の ノードは head と呼ばれます。

リンクされたリストのサイズは動的です。したがって、デバイスでストレージが利用可能でない限り、必要な数のノードを持つことができます。

リンク リストには 2 つのタイプがあります。それらについての詳細なチュートリアルを 1 つずつ見てみましょう。

#1. 単一リンクリスト

単一リンク リストには、リンク リスト内の 次のノード に接続された 単一のポインタ が含まれます。リンクされたリスト内の各ノードのデータとポインタを保存する必要があります。

リンク リストの最後のノードには、リンク リストの終わりを表す次のポインタとして null が含まれます。

以下のリンクの図を見ることができます。

これで、単一リンクリストについて完全に理解できました。 Python で実装する手順を見てみましょう。

単一リンクリストの実装

1. 最初のステップは、 リンク リスト の ノード を作成することです。

作成方法は?

Python では、 class を使用して ノードを 簡単に作成できます。このクラスには データ と 次のノード への ポインタが 含まれています。

ノードのコードを見てください。

 class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

上記のクラスを使用して、任意のタイプのデータを含むノードを作成できます。ちょっと見てみましょう。

これでノードが手に入りました。次に、複数のノードを含むリンク リストを作成する必要があります。リンク リスト用に別のクラスを作成しましょう。

2. ヘッドが None に初期化された LinkedList というクラスを作成します。以下のコードを参照してください。

 class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. Node クラス と LinkedList クラスがあります。リンクされたリストに新しいノードを挿入するにはどうすればよいでしょうか?簡単な答えは、 LinkedList クラスのメソッドを使用することです。そうですね、それはいいですね。リンクされたリストに新しいノードを挿入するメソッドを書いてみましょう。

リンクされたリストに新しいノードを挿入するには、特定の手順に従う必要があります。

見てみましょう。

• ヘッドが空かどうかを確認してください。
• ヘッドが空の場合は、新しいノードをヘッドに割り当てます。
• 先頭が空でない場合は、リンクされたリストの最後のノードを取得します。
• 新しいノードを最後のノードの次のポインタに割り当てます。

リンクされたリストに新しいノードを挿入するコードを見てみましょう。

 class LinkedList:

	####

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node != None:
				last_node = last_node.next

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

		else:
			## head is empty
			## assigning the node to head
			self.head = new_node

万歳！リンクされたリストに新しいノードを挿入する方法が完了しました。リンクされたリストからノード データにアクセスするにはどうすればよいですか?

リンクされたリストのデータにアクセスするには、挿入メソッドで最後のノードを取得する場合と同様に 、次のポインター を使用してリンクされたリストを反復処理する必要があります。 LinkedList クラス内にメソッドを記述して、リンク リスト内のすべてのノード データを出力しましょう。

4. 以下の手順に従って、リンク リスト内のすべてのノード データを印刷します。

• head で変数を初期化します。
• リンクされたリストの最後に到達するまで繰り返すループを作成します。
  • ノードデータを出力します。
  • 次のポインタを移動します

コードを見てみましょう。

 class LinkedList:

	####

	def display(self):
		## variable for iteration
		temp_node = self.head

		## iterating until we reach the end of the linked list
		while temp_node != None:
			## printing the node data
			print(temp_node.data, end='->')

			## moving to the next node
			temp_node = temp_node.next

		print('Null')

ふう！必要なメソッドを使用してリンクの作成が完了しました。いくつかのデータを使用してリンク リストをインスタンス化して、リンク リストをテストしてみましょう。

Node(1) コードを使用してノードを作成できます。リンク リスト実装の完全なコードを使用例とともに見てみましょう。

 class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node.next != None:
				last_node = last_node.next

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

		else:
			## head is empty
			## assigning the node to head
			self.head = new_node

	def display(self):
		## variable for iteration
		temp_node = self.head

		## iterating until we reach the end of the linked list
		while temp_node != None:
			## printing the node data
			print(temp_node.data, end='->')

			## moving to the next node
			temp_node = temp_node.next

		print('Null')


if __name__ == '__main__':
	## instantiating the linked list
	linked_list = LinkedList()

	## inserting the data into the linked list
	linked_list.insert(Node(1))
	linked_list.insert(Node(2))
	linked_list.insert(Node(3))
	linked_list.insert(Node(4))
	linked_list.insert(Node(5))
	linked_list.insert(Node(6))
	linked_list.insert(Node(7))

	## printing the linked list
	linked_list.display()

上記のプログラムを実行すると、次の結果が得られます。

 1->2->3->4->5->6->7->Null

リンクされたリストについては以上です。これで、単一リンクリストを実装する方法がわかりました。単一リンク リストの知識があれば、二重リンク リストを簡単に実装できます。チュートリアルの次のセクションに進みましょう。

#2. 二重リンクリスト

二重リンク リストには、リンク リスト内の 前のノード と 次のノード に接続された 2 つのポインターが 含まれます。リンクされたリスト内の各ノードのデータと 2 つのポインターを保存する必要があります。

両側のリンクされたリストの終わりを表すために、最初のノードの 前のポインタ は null であり、最後のノードの 次のポインタ は null です。

以下のリンクの図を見ることができます。

二重リンク リストの実装にも、単一リンク リストと同様の手順があります。同じことをもう一度説明するのは退屈でしょう。各ステップのコードを確認すると、すぐに理解できるようになります。さあ行こう。

二重リンクリストの実装

1. 前のノード ポインタ、データ、および次のノード ポインタを使用して二重リンク リストのノードを作成します。

 class Node:

	def __init__(self, data):
		## previous pointer
		self.prev = None

		## data of the node
		self.data = data

		## next pointer
		self.next = None

2. 二重リンクリストクラス。

 class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. 二重リンクリストに新しいノードを挿入する方法。

 class LinkedList:

	####

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node.next != None:
				last_node = last_node.next

			## assigning the last node to the previous pointer of the new node
			new_node.prev = last_node

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

4. 二重リンクリストデータを表示する方法。

 class LinkedList:

	####

	def display(self):

		## printing the data in normal order
		print("Normal Order: ", end='')

		temp_node = self.head
		while temp_node != None:
			print(temp_node.data, end=' ')
			temp_node = temp_node.next
		print()

		## printing the data in reverse order using previous pointer
		print("Reverse Order: ", end='')

		## getting the last node
		last_node = self.head
		while last_node.next != None:
			last_node = last_node.next

		temp_node = last_node
		while temp_node != None:
			print(temp_node.data, end=' ')
			temp_node = temp_node.prev
		print()

二重リンクリストのコードを見てきました。また、二重リンク リスト クラスを使用するためのコードはありません。それをあなたに。単一リンク リストと同様の二重リンク リスト クラスを使用します。楽しんでください 🙂

結論

リンクされたリストに基づいて多くの問題を見つけることができます。ただし、このチュートリアルで学んだリンクの基本的な実装を理解しておく必要があります。新しい概念を学ぶのに楽しい時間を過ごしていただければ幸いです。

また、Python のインデックス メソッドを使用してリスト内の項目のインデックスを検索する方法も確認してください。

コーディングを楽しんでください 😀