링크드 리스트(singly linked list) 구현

구현하려는 동작 첫 번째 동작은 addAtHead이다.

head가 가리키던 노드를 새로운 노드의 next가 가리키게 만들고 head가 가리키는 노드를 새로운 노드로 만든다.

 

두 번째 동작은 addBack이다. 링크드 리스트에 새로운 노드를 추가한다.

 

세 번째 동작은 find이다. 노드를 찾아 반환한다.

 

네 번째 동작은 addAfter이다. node, value를 파라미터로 받는다. node 다음에 value를 가진 새로운 노드를 추가한다.

 

마지막 동작은 deleteAfter이다. 편의상 delete 대신 구현하는 동작으로 파라미터로 받은 노드 다음의 노드를 삭제한다. 

 

from typing import Coroutine


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

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

class SLinkedList:
    def __init__(self) -> None:
        self.head = None
    
    def addAtHead(self, val)->None:
        node = ListNode(val)
        node.next = self.head
        self.head = node
    
    #but when the list
    def addBack(self, val) ->None:
        node = ListNode(val)
        crnt_node = self.head
        while crnt_node.next :
            crnt_node = crnt_node.next
        crnt_node.next = node
    
    def findNode(self, val) -> ListNode:
        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')

    def addAfter(self, node, val) -> None:
        new_node = ListNode(val)
        new_node.next = node.next
        node.next = new_node

    def deleteAfter(self, prev_node) -> None:
        if prev_node.next is not None:
            prev_node.next = prev_node.next.next

slist = SLinkedList()
slist.addAtHead(1)
slist.addAtHead(2)
slist.addBack(3)

node1 = slist.findNode(1)
slist.addAfter(node1,4)
slist.deleteAfter(node1)
printNodes(slist.head)

 

참조 : (3) 코딩 테스트, 기초, 링크드리스트 구현 - YouTube