연결리스트

연결리스트를 사용하는 이유

리스트의 특정 원소를 조회시는 시간복잡도가 O(1)이 걸리지만,
리스트에 특정 원소를 삽입,삭제시는 O(N)이 걸리게된다.
이때 linked list(연결리스트)를 사용하면 삽입,삭제시 O(1)이 걸린다.

연결리스트의 구조

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


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

    def append(self, val):
        if not self.head:
            self.head = ListNode(val, None)
            return

        node = self.head
        while node.next:
            node = node.next

        node.next = ListNode(val, None)

각 노드는 값이 들어있고 다음 값을 가리키는 .next라는 구조로 되어있다.
append시에는 .head를 우선적으로 값을 채우고 그 다음 .head에 값이 있다면 node는 .next를 가리키고 그 .next에 값을 채우는 방식으로 반복하는 구조이다.