リンクリスト

各ノードには、データとポインタがあり、データのデータ構造を1行接続で格納します.
ノード上のポインタは、次のノードまたは前のノードへの接続を担当します.

これで接続できます.
ランダムに格納されるデータフォーマットでは、nextは次の格納するデータを指し、リンクの配列である.
data-保存する情報
next-次のノードへの参照

node1.next=node 2(node 1.nextはnode 2の参照)
head:リンクリストの開始点
tail:リンクリストの終点

ノードの作成

ノードを作成するクラスとして、データが存在するdataとポインタが指すノードが存在するnextを作成します.
(None、今は次のノードがないので)

リンクリストの作成

headノードは現在Noneにありませんし、tailノードもいないのでNoneに設定します.

strを使用して、印刷するデータの形態を定義します.各ノードは「|」を使用して分離されます.
iterator=selfもあります.headの最初のheadノードを定義した後
反復器がNoneでない場合はres str文字列に追加します.
「|2|3|5|7|リンクリストが表示されます.

リンクリストへのアクセス

配列アクセスは、特定の場所に格納されているデータに直接アクセスできますが、リンクリストはポインタで接続されているため、headから必要な値に順次アクセスする必要があります.

def find_node_at(self, index):
"""링크드 리스트 접근 연산, 파라미터에 있는 인덱스는 항상 있다고 가정"""
  iterater = self.head
  for _ in range(index):
     iterater  = iterater
  return iterator

時間の複雑さ

むしろ配列から有効に近づく.
インデックスxのノードにアクセスするには、headから次のノードxに移動します.

リンクリストの追加演算(append)

加算をするときは考えなければならない.

リンクリストが空の場合

が最終時点

に直接追加する.

def append(self, data):
    """링크드 리스트 추가 연산 메소드"""
    # 삽입하고자 하는 데이터를 Node화 시겨준 다음
    new_node = Node(data)
    
    if self.head is None:
      self.head = new_node    # 추가된 노드가 head 이자 tail
      self.tail = new_node
    
    # 기존에 노드가 있을 경우
    else:
      self.tail.next = new_node    # 포인터를 설정 tail노드의 next를 new_node로 설정 
      self.tail = new_node         # new node를 다시 tail로 설정 
      

その他の操作は次のとおりです.
1:リンクリストが空の場合
2:既存のノードが存在する場合に追加
考えてみればいい.

リンクリストの挿入(insert)

追加操作は、最後に追加する操作とは異なり、ノードの中央に追加することもできますので、挿入するデータに前のノードから後に追加する方法でアクセスする必要があります.
1の挿入位置がtailノードの末尾にある場合.
2挿入位置がノードの中央にある場合

def insert_after(self, prvious_node, data):
    """링크드 리스트 삽입연산 메소드 """
    new_node = Node(data)
    
    # previous_node가 tail 노드 뒤에 삽입 하는 경우
    if prvious_node = self.tail:
       self.tail.next = new_node
       self.tail = new_node
    # 삽입 하는 위치가 특정 노드 뒤 인 경우
    else:
       new_node.next = previous_node.next  # 새로운 노드의 next가 prvious_node의 next
       previoust_node.next = new_node      # previouse_node의 next를 new node로 지정

新しいノードが一番前の挿入操作の場合

headノードが1つもない場合
2つのheadノードがある場合:

def prepand(self, data):
   new_node = Node(data)
   
   # head 노드가 없는 경우
   if self.head is None:
     self.head = New_node
     self.tail = New_node
  # head 노드가 현재 존재하는 경우
  else:
     new_node.next = self.head
     self.head = new_node

アクションの削除

削除するノードがtailノードであるかどうかを考慮するだけです.
1の場合、削除するノードがtailノードかどうか
2削除するノードがtailノードでない場合.
通常、削除操作は削除されたノードを返します.

def delete_after(self, prvious_node):
  data = previous_node.next.data  # 삭제하고자 하는 노드를 data로 가리켜 준다.
  
  # 삭제하려는 노드가 previous node 인 경우
  if previous_node is self.tail:
    previous_node = None
  # 아닌 경우
  else:
    previous_node.next = previous_node.next.next
  
  return data

「リンクリスト」演算でリンクを中断し、データが見つからない状態で削除されたと判断します.

一番前のデータを削除

指定したノードの次のノードを削除し続けるため、headノードは削除できません.
削除するノードがリストの最後の残りのノードである場合に削除することを考慮してください.

def popleft(self):
   """링크드 리스트의 가장 앞 노드를 삭제하는 경우 단, 리스트에 항상노드가 있다고 가정"""
   data = self.head.data    # 맨 앞 노드의 data를 담아준다.
   
   # 마지막 남은 노드인경우
   if self.tail is self.head:
     self.head = None
     self.tail = None
   # 아닌경우
   else:
     self.head = self.head.next
   
   return data

リンクリストの時間的複雑さ

に近づく

リンクリストでデータにアクセスする操作の時間的複雑さは、ノードとノードの間でポインタで接続されているため、一度にアクセスできません.
だから最大n回までできるので、時間の複雑さはO(n)です.

探索する

配列の探索と同様にO(n)である.

挿入と削除

挿入と削除は、挿入するノードまたは削除する前のノードのみに関連するため、いずれの場合も同じ順序が必要です。だからO(1)です。

現実

挿入と削除自体のみを考慮するとO(1)となるが、挿入位置の検索やノードの削除前のノードの閲覧時間の複雑さはO(n)であるため、O(n+1)=O(n)となる.

特別な場合

一番前の位置でtailノードを挿入、削除する場合は、別途ナビゲートする必要はありません.headノードとtailノードから直接アクセスできるからです.だからO(1)+O(1)なのでO(1)です.
ただし、最後に削除する場合は、Previousノードに移動する必要があります.これによりO(n)が発生します.
したがって,headノードの挿入,削除,tailノードの挿入については,他の場合とは異なる特殊な場合であり,この場合の時間的複雑度はO(1)であると考えられる.

ソース:コードセットデータ構造