ダブルリンクリスト

単一リンクリストは、1つのデータとリンクしたいポインタからなるノードが接続されたリストです.
デュアルリンクリストは、prevを指すポインタが1つ増えたことを意味します.

このようにして,データ,Prev,Nextはノードを構成する.

ノード、リンクリストの作成

この部分は単一リンクリストと何の違いもありません.

ノードの作成時のみ

class Node:
   def __init__(self, data):
      self.data = data
      self.next = None
      self.prev = None   # 이 부분이 추가 되었다.

以前のノードへのポインタprevが追加されました.

二重リンクリストへのアクセスと参照

独身者と変わらない.そっくりです.

二重リンクリストを追加する演算

二重リンクリストを追加する場合
境遇リンクリストが空の場合
境遇違う時.
区切りでいいです.

def append(self, data):
   new_node = Node(data)
   
   # 링크드 리스트가 비어 있을때
   if self.head is None:
      self.head = new_node
      self.tail = new_node
   # 링크드 리스트의 맨 끝에 추가 할때
   else:
     self.tail.next = new_node
     new.node.prev = self.tail   # new_node의 prev를 설정해주는 부분이 생겼다.
     self.tail = new_node

二重リンクリストを挿入する演算

挿入演算時
1 tailノードに追加した場合(追加した操作と同じ).
2つのノード間を挿入する場合

def insert_after(self, previous_node, data):
   new_node = Node(data)
   # tail노드 뒤에 삽입 할 경우
   if previous_node is self.tail:
      self.tail.next = new_node
      new_node.prev = self.tail
      self.tail = new_node
   # 두 노드 사이에 삽입할때 (약간 복잡하다.)
   else:
      previous_node.next.prev = new_node # 기존에 있던 previous_node의 다음 노드의 prev를 new 노드로 설정
      new_node.next = previous_node.next # new_node의 next를 기존의 previous_node의 다음으로 설정
      new_node.prev = previous_node      # 삽입하는 new_node의 prev를 previous노드로 설정
      previous_node.next = new_node      # previous_node의 next를 new_node로 설정

一番前に挿入

ダブルリンクリストも一番前に直接挿入できません.
リストが空の場合と空でない場合を考慮します.

def prepand(self, data):
   new_node = Node(data)
   if self.head is None:
      self.head = new_node
      self.tail = new_node
   else:
      new_node.next = self.head
      self.head.prev = new_node
      self.head = new_node

加算するようにすればいいです.難しくないです.

アクションの削除

単一のリンクリストとは異なり、以前のノードへのポインタの追加に伴い、削除したいノード自体を受信するだけでよい.
条件
ケース1で、最後に消去するノードが残っている場合
2個のheadノードをクリアすると、最後のノードX
3 tailノードをクリアすると、最後のノードX
4ノード間で挿入する場合:
この4つの席でいいと思います.
関数名はdelete、削除するノードはnode to deleteです.

def delete(self, node_to_data):
   # 경우 1
   if self.head is self.tail:
      self.head = None
      self.tail = None
   # 경우2
   elif node_to_delete is self.head:
      node_to_delete.next.prev = None
      self.head = node_to_delete.next
   # 경우3
   elif node_to_delete is self.tail:
      node_to_delete.prev.next = None
      self.tail = node_to_delete.prev
   # 경우4
   else:
      node_to_delete.prev.next = node_to_delete.next
      node_to_delete.next.prev = node_to_delete.prev

これでいいです.

時間の複雑さ

単一チェーンテーブルとは異なり、削除演算で変更されます.
シングルリンクドロップダウンリストの削除演算は、削除するノードの前のノードがナビゲーション後に削除する必要があり、ダブルリンクドロップダウンリストの削除は削除するノードに直接アクセスできるのでO(1)である.

エクストラスペース

単一リンクリストの余分な空間、すなわちポインタがn−1個を占めているため、O(n)である.しかし,二重リンクリストは2 n−2個でO(n)であるが,実際に占有される空間は2倍異なる.