HOWTO · Python

Python のリンクリスト

この記事では、Python のリンクリストについて説明します。この記事では、Python のリンクリストにすべての操作を実装しました。

著者 Aditya Raj公開日 2022-04-12更新日 2023-01-30

Python は、さまざまな組み込みデータ構造を提供します。

ただし、各データ構造には制限があります。このため、カスタムデータ構造が必要です。

この記事では、リンクリストと呼ばれるカスタムデータ構造について説明します。また、Python でリンクリストを実装し、リンクリストに対してさまざまな操作を実行します。

Python のリンクリストとは

名前が示すように、リンクリストは、リンクを使用して接続された要素を含むデータ構造です。

リンクリストは、ノードと呼ばれるオブジェクトを使用して作成されます。各ノードには 2つの属性が含まれています。1つはデータを格納するためのもので、もう 1つはリンクリスト内の次のノードに接続するためのものです。

次の図を使用して、ノードの構造を理解できます。

Python のノード

ここ、

  • Node は、属性 data と next を含むオブジェクトです。
  • 属性 data はデータを保存します。
  • 属性 next は、リンクリスト内の次のノードを参照します。

次の画像に示すように、さまざまなノードを接続してリンクリストを作成できます。

Python のリンクリスト

ここ、

  • 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つの状況があります。

  1. リンクリストは挿入前に空にすることができます。
  2. 空でないリンクリストの先頭に要素を挿入する必要があります。
  3. リンクリストの最後に要素を挿入する必要があります。
  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. リンクリストの最初の要素を削除する必要があります。
  2. リンクリストの最後の要素を削除する必要があります。
  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 を指しているかどうかを確認します。はいの場合、リンクリストが空であり、削除する要素がないことをユーザーに通知します。

リストに要素が含まれている場合は、次のプロセスに従います。

  1. 最初のノードを変数 current に割り当てます。
  2. 変数 previous を None に初期化します。
  3. while ループを使用してリンクリストをトラバースし、current 変数のノードを previous 変数に割り当て、current 変数が最後のノードに到達するまで current 変数を次のノードに進めます。この場合、current に割り当てられたノードの next 属性は None になります。
  4. 現在の変数が最後のノードに到達したら、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 を指しているかどうかを確認します。はいの場合、リンクリストが空であり、削除する要素がないことをユーザーに通知します。

リンクリストに要素があり、他の位置にある要素を削除する必要がある場合は、次の手順に従います。

  1. 最初のノードを変数 current に割り当てます。
  2. 変数 previous を None に初期化します。
  3. 変数 count を 1 に初期化します。
  4. while ループを使用してリンクリストをトラバースし、各反復で count をインクリメントし、current 変数のノードを previous に割り当て、count 変数が削除される要素の position になるか、リンクリストの最後に到達するまで、current 変数を次のノードに進めていきます。この時点で、変数 current は削除する必要のあるノードを参照しています。
  5. count が削除する要素の位置と等しくなると、2つの状況が考えられます。
  6. まだ Head にいる場合は、1 番目の位置で、現在の変数の next 属性によって参照されるノードを Head 属性に割り当てます。その後、current 変数を削除します。
  7. 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つの状況が考えられます。

  1. 値を置き換える必要があります。
  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

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