Python のリンクリスト
- Python のリンクリストとは
- Python でリンクリストを作成する方法
- リンクリストのすべての要素を Python で出力する
- Python のリンクリストに要素を挿入する
- Python でリンクリストから要素を削除する
- Python でリンクリストの要素数を数える
- Python でリンクリストのノードを更新する
- Python でリンクリストを使用する理由
- Python での完全な実装リンクリスト
- まとめ
![Python のリンクリスト](/img/Python/feature-image---linked-list-in-python.webp)
Python は、さまざまな組み込みデータ構造を提供します。
ただし、各データ構造には制限があります。このため、カスタムデータ構造が必要です。
この記事では、リンクリストと呼ばれるカスタムデータ構造について説明します。また、Python でリンクリストを実装し、リンクリストに対してさまざまな操作を実行します。
Python のリンクリストとは
名前が示すように、リンクリストは、リンクを使用して接続された要素を含むデータ構造です。
リンクリストは、ノードと呼ばれるオブジェクトを使用して作成されます。各ノードには 2つの属性が含まれています。1つはデータを格納するためのもので、もう 1つはリンクリスト内の次のノードに接続するためのものです。
次の図を使用して、ノードの構造を理解できます。
ここ、
Node
は、属性data
とnext
を含むオブジェクトです。- 属性
data
はデータを保存します。 - 属性
next
は、リンクリスト内の次のノードを参照します。
次の画像に示すように、さまざまなノードを接続してリンクリストを作成できます。
ここ、
- 4つのノードで構成されるリンクリストを作成しました。
- 最初のノードには 10 が含まれ、2 番目のノードには 20 が含まれ、3 番目のノードには 30 が含まれ、最後のノードには 40 が含まれます。
- 最初のノードを参照する変数
Head
も作成しました。リンクリストオブジェクトには、Head
変数のみを保持します。他のすべてのノードのデータは、Head
によって参照される最初のノードからリンクリストをトラバースすることによって取得されます。 - 最後のノードの
next
属性は、None
オブジェクトを参照します。リンクリストの最後のノードのnext
属性は、常にNone
オブジェクトを参照します。 - リンクリストが空の場合、
Head
変数はNone
オブジェクトを参照します。
これで、リンクリストの基本構造を理解できました。Python でリンクリストを実装しましょう。
Python でリンクリストを作成する方法
ノードはリンクリストの構成要素であるため、最初にノードを作成します。このために、以下に示すように、属性 data
および next
を持つ Node
クラスを定義します。
class Node:
def __init__(self, data):
self.data = data
self.next = None
myNode = Node(10)
print("The data in the node is:", myNode.data)
print("The next attribute in the node is:", myNode.next)
出力:
The data in the node is: 10
The next attribute in the node is: None
上記の例では、Node
の next
属性がデフォルトで None
を参照していることがわかります。リンクリストに挿入するときは、後で説明するように、リンクリストのノードに next
属性を割り当てます。
リンクリストを作成するには、属性 Head
を使用してオブジェクトを作成する必要があります。以下に示すように、LinkedList
クラスを定義できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4
print("The elements in the linked list are:")
print(myLinkedList.Head.data, end=" ")
print(myLinkedList.Head.next.data, end=" ")
print(myLinkedList.Head.next.next.data, end=" ")
print(myLinkedList.Head.next.next.next.data)
出力:
The linked list is:
10 20 30 40
上記の例では、リンクリストを作成しました。
その後、与えられたデータを使用してノードを手動で作成し、リンクリストに 1つずつ追加して、出力しました。後で、Python の while
ループを使用してリンクリストに要素を挿入する方法を学習します。
ここで、すべてのノードに手動でアクセスせずに、リンクリストのすべての要素を出力する方法について説明します。
リンクリストのすべての要素を Python で出力する
while
ループを使用して、すべてのリンクリスト要素を出力します。
Head
ポインタから始めて、最初にノードの data
属性を使用して現在のノードのデータを出力します。その後、next
ポインタを使用して次のノードに移動します。
リンクリストの最後に到達するまで(つまり、ノードの next
属性が None
であることが判明するまで)、このプロセスに従います。以下に示すように、printList()
メソッドでロジック全体を実装できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
10 20 30 40
Python のリンクリストに要素を挿入する
リンクリストに要素を挿入する場合、4つの状況があります。
- リンクリストは挿入前に空にすることができます。
- 空でないリンクリストの先頭に要素を挿入する必要があります。
- リンクリストの最後に要素を挿入する必要があります。
- リンクリストの特定の位置に要素を挿入する必要があります。
すべての状況でリンクリストに要素を挿入する方法について説明しましょう。
空のリンクリストに要素を挿入する
空のリンクリストに要素を挿入するには、要素を入力引数として受け入れ、入力要素を含むノードをリンクリストに追加するメソッド insertIntoEmptyList()
を定義します。
このために、入力要素を data
として insertIntoEmptyList()
にノードを作成します。ノードを作成したら、ノードを Head
属性に割り当てます。
このようにして、新しいノードがリンクリストの最初のノードになります。この方法は、次のように実装できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertIntoEmptyList(self, element):
newNode = Node(element)
self.Head = newNode
myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
10
リンクリストの先頭に要素を挿入する
空でないリストの先頭に要素を挿入するには、要素を入力として受け取り、それをリンクリストの先頭に追加するメソッド insertAtBeginning()
を定義します。insertAtBeginning()
メソッドでは、最初に入力要素をデータとしてノードを作成します。
その後、新しく作成されたノードの next
属性を、リンクリストの Head
属性が指すノードにポイントします。次に、新しく作成したノードを Head
属性に割り当てます。
このようにして、新しいノードがリンクリストの先頭に挿入されます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertIntoEmptyList(self, element):
newNode = Node(element)
self.Head = newNode
def insertAtBeginning(self, element):
newNode = Node(element)
newNode.next = self.Head
self.Head = newNode
myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
30 20 10
以下に示すように、上記のメソッドを組み合わせて、リンクリストの先頭に要素を挿入する単一のメソッドを作成できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertAtBeginning(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
newNode = Node(element)
newNode.next = self.Head
self.Head = newNode
myLinkedList = LinkedList()
myLinkedList.insertAtBeginning(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
30 20 10
空のリンクリストに挿入するということは、基本的にリンクリストの先頭に要素を挿入することを意味するため、insertIntoEmptyList()
メソッドを insertAtBeginning()
メソッドにマージしました。
リンクリストの最後に要素を挿入する
空のリストの最後に要素を挿入することは、リンクリストの最初に要素を挿入することに似ています。
リンクリストの最後に要素を挿入するには、最初にリンクリストが空かどうかを確認します。リンクリストが空であることがわかった場合は、insertAtBeginning()
メソッドで行ったように、新しい要素を含むノードを Head
属性に割り当てることができます。
それ以外の場合は、while
ループを使用してリンクリストを最後までトラバースします。Head
から始めて、ノードの next
属性が None
を指していることがわかるまで、ノードの next
属性を使用して次のノードに移動し続けます。
next
属性が None
を指すノードに到達すると、最後のノードに到達します。次に、入力データを使用して新しいノードを作成し、このノードをリンクリストの最後のノードの次の属性に割り当てます。
このようにして、新しい要素がリンクリストの最後に挿入されます。このロジック全体は、次のようにメソッド insertAtEnd()
に実装できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
def insertAtEnd(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
current = self.Head
while current.next is not None:
current = current.next
newNode = Node(element)
current.next = newNode
myLinkedList = LinkedList()
myLinkedList.insertAtEnd(10)
myLinkedList.insertAtEnd(20)
myLinkedList.insertAtEnd(30)
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
10 20 30
リンクリストの特定の位置に要素を挿入する
カウンター変数と while
ループを使用して、リンクリストの特定の位置に要素を挿入します。
ヘッドポインタから開始し、while
ループを使用して次のノードに移動し続けます。各反復で、カウンター変数もインクリメントします。
指定された位置の前のノードに到達したら、while
ループを終了します。また、リンクリストの最後に到達すると、ループを終了します。そうしないと、プログラムでエラーが発生します。
その後、まだ Head
にいる場合は、リンクリストの最初の位置に要素を追加する必要があります。指定された位置にあるノードを、新しいノード要素を含む next
ポインタに割り当てます。次に、新しい要素のノードをリンクリストの Head
に割り当てます。
要素を最初の位置に挿入する必要がない場合は、指定された位置のノードを、新しい要素を含むノードの next
ポインタに割り当てます。次に、新しいノードを position-1
にあるノードの next
属性に割り当てます。
このようにして、新しい要素が指定された位置に挿入されます。以下に示すように、insertAtPosition()
メソッドでロジック全体を実装できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(20, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(30, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
10
The elements in the linked list are:
10 20
The elements in the linked list are:
10 20 30
The elements in the linked list are:
10 40 20 30
Python でリンクリストから要素を削除する
リンクリストから要素を削除しようとすると、3つの状況が発生する可能性があります。
- リンクリストの最初の要素を削除する必要があります。
- リンクリストの最後の要素を削除する必要があります。
- リンクリストの任意の位置にある要素を削除する必要があります。
これらすべてのケースについて 1つずつ説明しましょう。
リンクリストの最初の要素を削除する
リンクリストの最初の要素を削除するには、最初にリンクリストが空かどうかを確認します。
このために、リンクリストの Head
が None
を指しているかどうかを確認します。はいの場合、リンクリストが空であり、削除する要素がないことをユーザーに通知します。
それ以外の場合は、最初のノードを一時変数に割り当てます。その後、リンクリストの 2 番目のノードを Head
属性に割り当てます。
次に、del
ステートメントを使用して、一時変数に格納されている最初のノードを削除します。以下に示すように、deleteFromBeginning()
メソッドでロジック全体を実装できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteFromBeginning(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
node = self.Head
self.Head = self.Head.next
del node
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
40 20 30
The elements in the linked list are:
20 30
リンクリストの最後の要素を削除する
リンクリストの最後の要素を削除するには、最初にリンクリストが空かどうかを確認します。
このために、リンクリストの Head
が None
を指しているかどうかを確認します。はいの場合、リンクリストが空であり、削除する要素がないことをユーザーに通知します。
リストに要素が含まれている場合は、次のプロセスに従います。
- 最初のノードを変数
current
に割り当てます。 - 変数
previous
をNone
に初期化します。 while
ループを使用してリンクリストをトラバースし、current
変数のノードをprevious
変数に割り当て、current
変数が最後のノードに到達するまでcurrent
変数を次のノードに進めます。この場合、current
に割り当てられたノードのnext
属性はNone
になります。- 現在の変数が最後のノードに到達したら、
previous
変数のnext
属性にNone
を割り当て、current
変数に割り当てられたノードを削除します。
上記の手順を実行すると、リンクリストの最後の要素を削除できます。以下に示すように、deleteFromLast()
メソッドでロジック全体を実装できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteFromLast(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
while current.next is not None:
previous = current
current = current.next
previous.next = None
del current
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
10 40 20
The elements in the linked list are:
10 40
リンクリストの任意の位置にある要素を削除する
リンクリスト内の任意の位置にある要素を削除するには、最初にリンクリストが空かどうかを確認します。
このために、リンクリストの Head
が None
を指しているかどうかを確認します。はいの場合、リンクリストが空であり、削除する要素がないことをユーザーに通知します。
リンクリストに要素があり、他の位置にある要素を削除する必要がある場合は、次の手順に従います。
- 最初のノードを変数
current
に割り当てます。 - 変数
previous
をNone
に初期化します。 - 変数
count
を 1 に初期化します。 while
ループを使用してリンクリストをトラバースし、各反復でcount
をインクリメントし、current
変数のノードをprevious
に割り当て、count
変数が削除される要素のposition
になるか、リンクリストの最後に到達するまで、current
変数を次のノードに進めていきます。この時点で、変数current
は削除する必要のあるノードを参照しています。count
が削除する要素の位置と等しくなると、2つの状況が考えられます。- まだ
Head
にいる場合は、1 番目の位置で、現在の変数のnext
属性によって参照されるノードをHead
属性に割り当てます。その後、current
変数を削除します。 - 1 番目の位置にいない場合は、
current
変数の次のノードをprevious
変数に割り当てられたノードの次の属性に割り当てます。current
変数に割り当てられたノードを削除します。このようにして、指定された位置にある要素が削除されます。
上記のロジックは、以下で説明する deleteAtPosition()
メソッドで実装できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteAtPosition(self, position):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
count = 1
while current.next is not None and count < position:
previous = current
current = current.next
count += 1
if current == self.Head:
self.Head = current.next
del current
else:
previous.next = current.next
del current
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(2)
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
40 20 30
The elements in the linked list are:
40 30
Python でリンクリストの要素数を数える
リンクリスト内の要素の数をカウントするには、変数 count
を 0 に初期化するだけです。
その後、Head
から開始し、リンクリストの最後に到達するまで while
ループを使用して次のノードに移動します。while
ループの各反復で、count
を 1 ずつインクリメントします。
while
ループを実行した後、変数 count
のリンクリストに要素の数が表示されます。以下の countElements()
メソッドに示すように、このロジックを実装できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def countElements(self):
count = 0
current = self.Head
while current is not None:
count += 1
current = current.next
print("Number of elements in the linked list are:", count)
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.countElements()
出力:
The elements in the linked list are:
10 40 20 30
Number of elements in the linked list are: 4
Python でリンクリストのノードを更新する
リンクリストのノードの値を更新するには、2つの状況が考えられます。
- 値を置き換える必要があります。
- リンクリストの任意の位置にある要素に新しい値を割り当てる必要があります。
リンクリストの値を置き換える
リンクリストの値を置き換えるには、最初のノードから開始し、while
ループを使用してリンクリストをトラバースします。
current
ノードに各ノードで置き換えられる値が含まれているかどうかを確認します。はいの場合、現在のノードの値を新しい値に置き換えます。
このようにして、replaceElement()
メソッドに示されているように、リンクリスト内の任意の要素の最初の出現を更新できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def replaceElement(self, old_element, new_element):
current = self.Head
while current is not None:
if current.data == old_element:
current.data = new_element
break
current = current.next
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(30, 100)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(20, 150)
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
10 40 20 100
The elements in the linked list are:
10 40 150 100
リンクリストの特定の位置にある要素を更新する
リンクリスト内の特定の位置にある要素を更新するには、最初にリンクリストが空かどうかを確認します。はいの場合、2つの状況が考えられます。
リンクリストが空で、最初の位置以外の要素を更新する必要がある場合は、更新できないことをユーザーに通知します。
リンクリストが空で、最初の位置の要素を更新する必要がある場合は、指定された要素で新しいノードを作成し、そのノードをリンクリストのヘッド
に割り当てます。それ以外の場合は、変数 counter
を 1 に初期化します。
その後、while
ループを使用してリンクリストをトラバースします。while
ループの各反復で、リンクリスト内の次のノードに移動し、変数 counter
を 1 ずつインクリメントし、更新が必要な要素の位置に到達したかどうかを確認します。
更新が必要な位置に到達すると、リンクリストの現在のノードの値を更新し、ユーザーに通知します。
更新が必要な位置に到達できず、while
ループが終了した場合、十分な要素がなく、値を更新できないことをユーザーに通知します。このロジックは、以下に示すように updateAtPosition()
メソッドで実装できます。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def updateAtPosition(self, new_element, position):
if self.Head is None and position != 1:
print("No element to update in the linked list.")
return
elif self.Head is None and position == 1:
newNode = Node(new_element)
self.Head = newNode
return
count = 1
current = self.Head
while current.next is not None and count < position:
count += 1
current = current.next
if count == position:
current.data = new_element
elif current.next is None:
print("Not enough elements in the linked list.")
myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(100, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(150, 12)
print("The elements in the linked list are:")
myLinkedList.printList()
出力:
The elements in the linked list are:
10 40 20 30
The elements in the linked list are:
10 40 100 30
Not enough elements in the linked list.
The elements in the linked list are:
10 40 100 30
Python でリンクリストを使用する理由
- 要素へのランダムアクセスが必要ない場合は、リンクリストの方が適しています。保存する要素が数百万あり、ランダムアクセスが不要な場合は、Python の通常のリストの代わりにリンクリストを使用する必要があります。
- リストの実際のサイズは、リストに存在する要素の数に比べて非常に大きくなります。リストの実際のサイズは、リストに存在する要素の数の約 1.5 倍です。これにより、リストに要素を挿入するのに十分なメモリが確保されます。ただし、リンクリストには余分なスペースは必要ありません。
- リンクリストに要素を挿入する場合、必要なのはストレージのみです。リストには、連続したメモリ位置も必要です。逆に、リンクリストのノードは、物理メモリ内の任意の場所に存在できます。それらは参照を使用して接続されます。
- リンクリストを使用して、スタックとキューの両方のデータ構造を効率的に実装できます。一方、リストを使用してキューを実装すると、時間の複雑さが増します。
Python での完全な実装リンクリスト
以下は、この記事で説明されているすべてのメソッドを使用して、Python でリンクリストを実装するための完全な実行コードです。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.Head = None
def printList(self):
current = self.Head
while current is not None:
print(current.data, end=" ")
current = current.next
print("")
def insertAtBeginning(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
newNode = Node(element)
newNode.next = self.Head
self.Head = newNode
def insertAtEnd(self, element):
if self.Head is None:
newNode = Node(element)
self.Head = newNode
else:
current = self.Head
while current.next is not None:
current = current.next
newNode = Node(element)
current.next = newNode
def insertAtPosition(self, element, position):
counter = 1
current = self.Head
while counter < position - 1 and current is not None:
counter += 1
current = current.next
if position == 1:
newNode = Node(element)
newNode.next = current
self.Head = newNode
else:
newNode = Node(element)
newNode.next = current.next
current.next = newNode
def deleteFromBeginning(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
node = self.Head
self.Head = self.Head.next
del node
def deleteFromLast(self):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
while current.next is not None:
previous = current
current = current.next
previous.next = None
del current
def deleteAtPosition(self, position):
if self.Head is None:
print("The linked list empty. Cannot delete an element.")
return
else:
current = self.Head
previous = None
count = 1
while current.next is not None and count < position:
previous = current
current = current.next
count += 1
if current == self.Head:
self.Head = current.next
del current
else:
previous.next = current.next
del current
def countElements(self):
count = 0
current = self.Head
while current is not None:
count += 1
current = current.next
print("Number of elements in the linked list are:", count)
def replaceElement(self, old_element, new_element):
current = self.Head
while current is not None:
if current.data == old_element:
current.data = new_element
break
current = current.next
def updateAtPosition(self, new_element, position):
if self.Head is None and position != 1:
print("No element to update in the linked list.")
return
elif self.Head is None and position == 1:
newNode = Node(new_element)
self.Head = newNode
return
count = 1
current = self.Head
while current.next is not None and count < position:
count += 1
current = current.next
if count == position:
current.data = new_element
elif current.next is None:
print("Not enough elements in the linked list.")
まとめ
この記事では、リンクリストのデータ構造と Python での実装について説明しました。また、リンクリストにさまざまな操作のメソッドを実装しました。
この記事では、メソッドを使用してすべての操作を実装しました。リンクリストの Head
を入力として受け取り、必要な操作を実行した後に head を返す関数を使用して、各操作を実装することもできます。
ただし、これには実行中により多くのリソースが必要になります。したがって、この記事で使用されているアプローチを使用することをお勧めします。
Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.
GitHub