接続リストとは?

接続リストは、[リンクを使用してリストを作成]です.意味は.
接続リストはノードで構成され、ノードは値を含む値と次のノードへの参照で構成されます.

上図のノード1、ノード2、ノード3、ノード4は順に接続リストであり、最初のノードをheadノードと呼ぶ.

計算された時間の複雑さ

find() : O(n)random access:接続リストはランダムアクセスをサポートせず、headノードから検索するノードに1つずつ入る必要があります.insert() : O(1)delete() : O(1)

ノードの挿入例

1枚目の写真のノード2とノード3との間にノード5を挿入する例.
1)まずvalue=5を持つノード5を作成する.
2)ノード2をノード5に向ける.
3)ノード2が指すノード3をノード5に向ける.

削除ノードの例

次に、1枚目の写真を削除するノード3の例を示す.
1)ノード2をノード3が指すノード4に向ける.
2)ノード3を削除する.

インプリメンテーション

github

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

def printNodes(node:ListNode):
    crnt_node = node
    while crnt_node is not None:
        print(crnt_node.val, end=' ')
        crnt_node = crnt_node.next

def printNodesRecur(node:ListNode):
    print(node.val, end=' ')
    if node.next is not None:
        printNodesRecur(node.next)

head_node = ListNode(1)
head_node.next = ListNode(2)
head_node.next.next = ListNode(3)
head_node.next.next.next = ListNode(4)
printNodes(head_node)
printNodesRecur(head_node)

__init__()接続リストを構成するノードを初期化します.
ノードはvalue、referenceからなり、ノードが接続(指向)されていないため、referenceはself.next=Noneである.head_node = ListNode(1)value=1を使用してノードを作成し、ノード2、ノード3、ノード4の順に作成して接続します.printNodes()接続リストを反復的に出力します.printNodesRecur()接続リストを再帰的に出力します.
参考講座:コードレスプログラミング