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 のインデックスメソッドを使用してリスト内の項目のインデックスを検索する方法も確認してください。

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