[쓰면서 익히는 알고리즘과 자료구조](3) 연결 리스트(Linked List)

많이 등장하는 자료구조

단점

• 특정 위치의 데이터를 찾기 위해서는 처음부터 순회해야 한다.
• 주소값도 저장해야 되서 추가 메모리 공간이 필요하다
• 연속적인 메모리 공간으로 관리되지 않아서 CPU 캐시 입장에서 비용이 더 든다

class Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = None

3.4 연결 리스트 뒤집기

class Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = None

def reverse_list(head: Node) -> Node:
    prev = None
    curr = head

    while curr is not None:
        next_temp = curr.next

        curr.next = prev
        prev = curr
        curr = next_temp

    return prev

class Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = None

def reverse_list(head: Node) -> Node:
    if head is None:
        return head

    stack = []

    curr = head

    while curr.next is not None:
        stack.append(curr)
        curr = curr.next

    first = curr

    while stack:
        curr.next = stack.pop()
        curr = curr.next

    curr.next = None

    return firstclass Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = None

class Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = None

def reverse_list(head: Node) -> Node:
    if head is None or head.head.next is None:
        return head

    reversed_list = reverse_list(head.next)
    head.next.next = head
    head.next = None
    
    return reversed_list

3.5 순환 검출(Cycle Detection)

아이디어 1 (Ideas 1)

1. 노드를 순회한다.
   1. 순회 중 노드가 끝에 도달하거나 연결이 없다면 종료
   2. 현재까지 순회 카운터를 기록
   3. 노드를 처음부터 순회한다.(순회 카운터 만큼)
      1. 바깥 순회에서 선택된 노드와 비교해 2번 겹친다면 순환이 발생
      2. 아니라면 순회를 종료

이게 무슨 소리일까, 설명을 진짜 어렵게 해놨다..

class Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = Noneclass Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = None

def has_cycle(head: Node) -> bool:
    outer = head

    node_cnt = 0

    while outer is not None and outer.next is not None:
        outer = outer.next
        node_cnt += 1

        visit = node_cnt
        inner = head

        matched = 0

        while visit > 0:
            if outer != inner:
                inner = inner.next

            if outer == inner:
                matched += 1

            if matched == 2:
                return True

            visit -= 1

    return False

코드를 보면 이해가 되는데,

일단 링크드 리스트를 문제에서 던져줄 것이기 때문에 크기를 알 수가 없다.
head 부터 순회한다고 하더라도 만약 순환이 있는 LinkedList 라면 크기가 무한대가 나올 것이기 때문이다.

그래서 head 부터 조회하면서 지금까지 몇 개를 조회했는지 카운트 한다.
왜냐면 지금까지 조회한 노드의 갯수는 확실히 알 수 있는 LinkedList의 최소 크기이기 때문이다.
( 그동안 head 를 다시 돌아오는 순환이 발생하지 않았다고 하면)

만약 LinkedList 의 크기가 N 이라면 N 번 순회하는 동안 다시 head 로 돌아오는지 확인하면 순환고리가 있는 것을 알 수 있다.

그래서 점점 카운트를 늘리면서 LinekedList 가 끝이 난다면 (Node.next is None) 순환하지 않는 LinkedList 인 것이다.
만약 다시 head 로 돌아온다면 이 LinkedList는 순환고리를 가지고 있는 것이다.

그래서 우리가 알지 못하는 LinkedList의 크기가 N 이라면, 1 + 2 + 3 .. N 번 조회해야 되기 때문에 시간 복잡도는 O(n^2) 이 된다

아이디어 2 (Ideas 2)

이런 무식한 방법을 안 쓰고 HashMap을 사용하면 O(N) 으로 끝낼 수 있다.
Node의 주소만 잘 저장해놔도 LinkedList의 길이만큼 조회하면서 이미 저장된 주소인지만 확인하면 되기 때문에 O(n)으로 끝날 수 있다.
이 책에서는 Set 으로 해결하였다.

class Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = None

def has_cycle_set(head: Node) -> bool:
    curr = head
    node_set = set()
    
    while curr is not None:
        if curr in node_set:
            return True
        
        node_set.add(curr)
        curr = curr.next
    
    return False

아이디어 3 (Ideas 3)

세 번쨰 방법은 플로이드의 토끼와 거북이 알고리즘 혹은 빠른(Fast) & 느린(Slot) 포인터 패턴이라 불리는 방법이다.
한 개는 두 칸씩 가고 다른 한 개는 한 칸씩 가면 순환한다면 언젠가는 만나게 되어있고, 순환하지 않는다면 LinkedList 의 끝에 도달하게 된다.

class Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = None

def has_cycle(head: Node) -> bool:
    slow = head
    fast = head
    
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

3.6 두 수 더하기

연결 리스트의 각 자리의 숫자 하나하나가 연결 리스트의 노드로 구성되어있고 이 숫자의 합을 구하는 문제이다. 이것은 단일 연결 리스트의 경우 첫 노드(head)를 기준으로 한 방향으로만 접근 및 이동을 한다는 제약을 이용한 문제이다.

아이디어 (Ideas)

1. 스택
2. 연결 리스트 뒤집기
3. 문자열 연산

class Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = None

def add_two_numbers_stack(l1: Node, l2: Node) -> Node:
    stack1 = []
    stack2 = []

    l1_curr = l1
    l2_curr = l2

    head = None

    while l1_curr is not None:
        stack1.append(l1_curr.data)
        l1_curr = l1_curr.next

    while l2_curr is not None:
        stack1.append(l2_curr.data)
        l2_curr = l2_curr.next

    carry = 0
    while stack1 or stack2:
        num1 = stack1.pop() if stack1 else 0
        num2 = stack2.pop() if stack2 else 0  # 배열이 비면 False 구나
        
        # divmod -> Return the tuple (x//y, x%y)
        carry, num = divmod(num + num2 + carry, 10)
        
        # 결과 LinkedList 생성
        node = Node(num)
        
        if head is None:
            head = node
        else:
            temp = head
            head = node
            node.next = temp
            
    if carry != 0:
        node = Node(carry)
        temp = head
        head = node
        node.next = temp
    
    return head

class Node(object):
    def __init__(self):
        self.data: object = None
        self.next: Node = None
        

def add_two_numbers_reverse(l1: Node, l2: Node) -> Node:
    def reverse(head):
        prev = None
        curr = head
        while curr is not None:
            next_temp = curr.next
            curr.next = prev
            
            prev = curr
            curr = next_temp
        return prev
    
    r_l1 = reverse(l1)
    r_l2 = reverse(l2)
    
    res_head = None
    
    carry = 0
    while r_l1 is not None or r_l2 is not None:
        num1 = 0
        num2 = 0
        
        if r_l1 is not None:
            num1 = r_l1.data
            r_l1 = r_l1.next
        if r_l2 is not None:
            num2 = r_l2.data
            r_l2 = r_l2.next
            
        carry, num = divmod(num1 + num2 + carry, 10)
        
        node = Node(num)
        if res_head is None:
            res_head = node
        else:
            temp = res_head
            res_head = node
            node.next = temp
        
    if carry != 0:
        node = Node(carry)
        temp = res_head
        res_head = node
        node.next = temp
    
    return res_head

class Node(object):
    def __init__(self, data):
        self.data: object = data
        self.next: Node = None
        

def add_two_numbers(l1: Node, l2: Node) -> Node:
    num1_str = ""
    num2_str = ""
    
    l1_curr = l1
    l2_curr = l2
    
    while l1_curr is not None:
        num1_str = num1_str + str(l1_curr.data)
        l1_curr = l1_curr.next
    
    while l2_curr is not None:
        num2_str = num2_str + str(l2_curr.data)
        l2_curr = l2_curr.next
    
    res_num = int(num1_str) + int(num2_str)
    
    # dummy node
    head = Node(-1)
    
    curr = head
    for num_ch in str(res_num):
        curr.next = Node(int(num_ch))
        curr = curr.next
    
    curr.next = None
    
    return head.next