[연결리스트] 개념 - 2

단일 연결리스트란(Singly Linked List)란?

노드는 value, reference로 이루어지는데 다음 노드를 가리키는 reference가 한쪽 방향으로만 이루어진 연결리스트를 단일 연결리스트라고 한다.

노드 구현

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)

init(self) : 아무 정보도 없는 헤드노드 생성
addAtHead(self, val) : 새로운 노드 생성 후 헤드노드 바로 다음에 삽입, O(1)
addBack(self, val) : 새로운 노드 생성 후 연결리스트의 가장 마지막에 삽입, O(n)
=> 여기까지 수행하면 노드2 -> 노드1 -> 노드3
addAfter(self, node, val) : 새로운 노드 생성 후 특정 노드 뒤에 삽입하기, O(1)
위의 예제에서 노드2 -> 노드1 -> 노드3 이었던걸 노드2 -> 노드1 -> 노드4 -> 노드3으로 바꾸기

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")

findNode(self, val) : 입력으로 들어온 val을 가지는 노드 찾기
1) 헤드노드부터 시작해 현재 노드(crnt_node)를 받아온다.
2) 현재 노드가 존재할 때 :
2-1) 현재 노드의 val값이 val과 동일하면 노드 찾기 완료.
2-2) val값이 동일하지 않으면 다음 노드와 비교 수행.
2-3) 끝까지 비교했는데도 val값이 동일한 노드가 없다면 runtime error 발생시키기.

delete() 연산 구현

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

특정 노드를 삭제하려면 삭제하려는 노드를 가리키는 노드를 알아야 한다.
여기서는 간단하게 노드를 삭제하는 연산을 구현하기 위해 특정 노드 다음 노드를 삭제하는 deleteAfterNode(self, prev_node) 함수를 구현했다.

전체 코드

참고한 강의 : 코드없는 프로그래밍