TIL 34:ダブルリンクリスト

🙄 ダブルリンクリスト

ダブルリンクリストとは?

各ノードに次のノードのレビュー、全ノードのレビューのリンクリストを格納する

class Node:
    """링크드 리스트 노드"""
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


class LinkedList:
    """링크드 리스트"""
    def __init__(self):
        self.head = None
        self.tail = None

🙄 ダブルリンクリスト演算

e単一リンクリストとの汎用演算

접근/탐색 연산・__str__方法はシングルリンクのメニューと同じ

ダブルリンクドロップダウンリスト追加演算：append

class Node:
    """링크드 리스트 노드"""
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


class LinkedList:
    """링크드 리스트"""
    def __init__(self):
        self.head = None
        self.tail = None

    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
            self.tail = new_node
  

# 빈 링크드 리스트 정의
my_list = LinkedList()

# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)

print(my_list)

# | 2 | 3 | 5 | 7 |

👉 欠点は、リストの一番前に挿入できないことです
👉 この機能を補完するフロントエンドメソッドを作成します.

ダブルリンクドロップダウンリスト追加演算：prepend

class LinkedList:
    """링크드 리스트"""
    def __init__(self):
        self.head = None
        self.tail = None

    def prepend(self, data):
        """링크드 리스트 가장 앞에 데이터를 추가시켜주는 메소드"""
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.head.prev = new_node
            new_node.next = self.head
            self.head = new_node


# 새로운 링크드 리스트 생성
my_list = LinkedList()

# 여러 데이터를 링크드 리스트 앞에 추가
my_list.prepend(11)
my_list.prepend(7)
my_list.prepend(5)
my_list.prepend(3)
my_list.prepend(2)

print(my_list) 	# 링크드 리스트 출력

# head, tail 노드가 제대로 설정됐는지 확인
print(my_list.head.data)
print(my_list.tail.data)

# | 2 | 3 | 5 | 7 | 11 |
# 2
# 11

二重リンクリストを削除する操作

4種類の場合を考える
1.リスト長が1の場合
2.クリアheadノードの場合
3.クリアtailノードの場合
4.両ノード間のノードをクリアした場合

class LinkedList:
    """링크드 리스트"""
    def __init__(self):
        self.head = None
        self.tail = None

    def delete(self, node_to_delete):
        """더블리 링크드 리스트 삭제 연산 메소드"""
        data = node_to_delete.data

        if self.head is self.tail:
            self.head = None
            self.tail = None
        elif self.head is node_to_delete:
            self.head = self.head.next
            self.head.prev = None
        elif self.tail is node_to_delete:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            node_to_delete.next.prev = node_to_delete.prev
            node_to_delete.prev.next = node_to_delete.next
        return data

    def find_node_at(self, index):
        """링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정"""

        iterator = self.head

        for _ in range(index):
            iterator = iterator.next

        return iterator

 

# 새로운 링크드 리스트 생성
my_list = LinkedList()

# 새로운 노드 4개 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)

print(my_list)

# 두 노드 사이에 있는 노드 삭제
node_at_index_2 = my_list.find_node_at(2)
my_list.delete(node_at_index_2)
print(my_list)

# 가장 앞 노드 삭제
head_node = my_list.head
print(my_list.delete(head_node))
print(my_list)

# 가장 뒤 노드 삭제
tail_node = my_list.tail
my_list.delete(tail_node)
print(my_list)

# 마지막 노드 삭제
last_node  = my_list.head
my_list.delete(last_node)
print(my_list)

# | 2 | 3 | 5 | 7 |
# | 2 | 3 | 7 |
# 2
# | 3 | 7 |
# | 3 |
# |

🙄 デュアルリンクリストの時間的複雑さ

デュアルリンクリストの時間的複雑さ

演算リンクリストアクセスO(n)O(n)O(n)O(n)O(n)O(n)O(n)挿入O(1)O(1)O(1)削除O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)

じつじかんふくざつさ

計算リンクリストアクセスO(n)O(n)O(n)O(n)O(n)O(n)O(n)O(n)O(n)アクセスまたはブラウズ+挿入O(n+1)O(n+1)O(n+1)アクセスまたはブラウズ+削除O(n+1)O(n+1)O(n+1)O(n+1)O(n+1)O(n+1)

特殊な場合の挿入と削除

演算二重リンクリストの一番前のアクセス+挿入O(1+1)O(1+1)O(1+1)一番前のアクセス+削除O(1+1)O(1+1)一番後ろのアクセス+挿入O(1+1)O(1+1)O(1+1)一番後ろのアクセス+削除O(1+1)O(1+1)O(1+1)O(1+1)O(1+1)O(1+1)O(1+1)O(1+1)O(1+1)O(1+1)O(1+1)

1ページと2ページのリンクリストtailノードの削除

単一リンクリスト二重リンクリストの一番前のアクセス＋挿入O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)))(1＋1)O(1＋1)O(1＋1＋1)O(1＋1)O(1＋1)O(1＋1＋1)O(1＋1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1))O(1＋1)O(1＋1)O(1)(n＋1)O(1)(n＋1)O(n＋1)O(1＋1)O(1＋1)O(1＋1)O(1＋1)O
👉 tail前のノードにアクセスしてノードのシングルポイントをクリアする必要がある
👉 属性格納tailノードをパラメータとするデュプレクス

リンクリストが必要な場合tail多くのノードを削除する必要がある場合
ダブルリンクリストは、単一のリストよりも有効です.

🙄 シングルとダブルリンクリスト

シングル:前のノードに特定のノードからアクセスできない

双利:どのノードでもリンクリストのすべてのノードにアクセスできる

エクストラスペース

データ構造で使用される空間において、実際に記憶するデータ以外の情報を記憶する空間
ex)リファレンスストレージ

単点:ノードがn個の場合n-1個のメモリ、O(n)O(n)の余分な空間複雑度

双利:ノードがn個の場合2n-2個のメモリ、O(n)O(n)の余分な空間複雑度

👉 同じ空間複雑度:O(n)O(n)O(n)O(n)であるが,実際には2倍の差がある.
👉 普段はあまり差はありませんが、本格的なスペースを有効に使いたいならシングルルームが効率的です.