[接続リスト]コンセプト-2

単一接続リストとは?

ノード実装

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

挿入演算の実装

class SLinkedList:
    def __init__(self):
        self.head = None

    def addAtHead(self, val):
        node = ListNode(val)  # 새로운 노드 생성
        node.next = self.head  # 새로운 노드는 헤드노드가 가리키던걸 가리킴
        self.head = node  # 헤드노드가 생성한 노드를 가리키도록

    # 링크드리스트가 비어있으면 동작 안하는 버그 있음
    def addBack(self, val):
        node = ListNode(val)
        crnt_node = self.head  # 마지막 노드가 어떤걸 가리키는지 알기 위해서
        while crnt_node.next:
            crnt_node = crnt_node.next
        crnt_node.next = node  # 마지막 노드가 새로 생성한 노드를 가리키도록

    def addAfter(self, node, val):
       new_node = ListNode(val)
       new_node.next = node.next  # 노드1 -> 노드3 에서 노드4 -> 노드3 으로
       node.next = new_node  # 노드1 -> 노드3 에서 노드1 -> 노드4 로
        
slist = SLinkedList()
slist.addAtHead(1)
slist.addAtHead(2)
slist.addBack(3) 
printNodes(slist.head)

find()演算の実行

class SLinkedList:
    # O(n)
    def findNode(self, val):
        crnt_node = self.head
        while crnt_node is not None:
            if crnt_node.val == val:
                return crnt_node
            crnt_node = crnt_node.next
        raise RuntimeError("Node not found")

delete()演算の実装

class SLinkedList:
    # 입력된 노드의 다음 노드를 삭제하기
    def deleteAfterNode(self, prev_node):  # O(1)
        if prev_node.next is not None:
            prev_node.next = prev_node.next.next