Technical Interview Master Plan [2] - Linked List를 알아도 왜 포인터 역전 문제에서 자꾸 틀리는가

Linked List 를 마치고 챕터 Fast-Slow Pointer, Sliding Window 순으로 이어집니다.

Linked Lists

Introduction to Linked Lists

연결 리스트는 노드들의 연속(sequence) 으로 구성된 데이터 구조로, 각 노드는 다음 노드(next) 에 연결되어 있다. 연결 리스트의 노드는 두 가지 주요 구성 요소를 가진다.

저장하는 데이터(val) 의 순서상 다음 노드를 가리키는 참조이다. 아래와 같이 ListNode 클래스를 사용해서 노드를 정의 하도록 한다.

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

Singly linked list, 단일 연결 리스트

연결 리스트의 가장 단순한 형태는 단일 연결 리스트이다. 여기서 각 노드는 연결 리스트 내의 다음 노드를 가리키며 마지막 노드는 아무것도 가리키지 않는다(null). 이는 연결리스트의 끝을 의미한다.

연결리스트의 시작은 head 라고 불리며, 일반적으로 우리가 처음에 즉시 접근할 수 있는 유일한 노드이다. 연결 리스트의 시작은 head 라고 불리며, 일반적으로 우리가 처음에 즉시 접근할 수 있는 유일한 노드이다. 연결 리스트의 다른 노드들에 접근하려면 head 에서 시작하여 순회(traverse) 해야 한다.

단일 연결 리스트는 데이터 집합을 저장하는 데 사용될 수 있다. 이들의 주요 장점 중 하나는 동적 크기 조절(dynamic sizing) 능력에 있다. 배열과 다르게 고정된 크기를 가지지 않기 때문에 유연하게 크기를 늘리거나 줄일 수 있다. 또한, 단일 연결 리스트는 빈번한 삽입과 삭제가 필요한 상황에서 뛰어나다. 이러한 연산은 배열보다 더 효율적으로 수행 될 수 있는데, 배열은 삽입이나 삭제를 수행하기 위해 요소들을 이동시켜야 하기 때문이다.

예를 들어, 연결 리스트의 노드 2와 노드 4 사이에 노드 3을 삽입한다고 가정해봅니다.

1 -> 2 -> 4
이러한 구조로 연결 리스트가 만들어져 있습니다. 
여기에 노드2와 노드4 사이에 3을 추가할 것입니다. 

먼저 3이라는 값을 노드와 함께 생성해줍니다. 

new_node = Node(3)

그러기 위해서는 노드2의 next 포인터를 노드3으로 지정을 해주어야 합니다. 
node2.next = new_node
이렇게 하면 

1 -> 2 -> 3  4 

이러한 상태가 될 것입니다. 노드2의 다음 노드로 노드3이 연결되어 있지만, 
노드3의 next 는 아직 노드4와 연결되지 않았습니다. 
따라서, new_node.next = node4 이렇게 노드3과 노드4를 연결해줍니다. 

최종적으로 1 -> 2 -> 3 -> 4 와 같이 연결 리스트에 새로운 노드3이 성공적으로
노드2와 노드4 사이에 삽입됩니다. 

이러한 연산의 효율성은 랜덤 접근(random access) 을 수행할 수 없다는 대가를 치릅니다. 배열처럼 인덱스를 사용하여 노드에 접근 할 수 없습니다. 이러한 트레이드 오프는 많은 사용 사례에서 알 수 있습니다. 동적 크기 조절의 이점과 삽입/삭제의 효율성이 랜덤 접근의 주요 성능 이점보다 더 클 수 있기 때문입니다.

Doubly linked list, 이중 연결 리스트

이중 연결 리스트는 연결 리스트의 확장 버전으로, 각 노드는 두개의 참조를 가진다. 하나는 다음 노드 next 를 가리키고 다른 하나는 이전 노드 prev 를 가리킨다. 대부분의 구현에서 이중 연결 리스트는 head 노드와 tail 노드 모두에 즉시 접근 할 수 있습니다.

이중 연결 리스트의 큰 장점 중 하나는 양방향 순회(bidirectional traversal) 를 허용한다는 점이다. 또한, 다음 노드와 이전 노드 모두에 대한 참조를 가지고 있기 때문에 이중 연결 리스트에서 노드를 삭제하는 것은 일반적으로 더 직관적이다.

class ListNode:
    def __init__(self, val: int, prev: ListNode, next: ListNode):
        self.val = val 
        self.prev = prev 
        self.next = next

Pointer Manipulation, 포인터 조작 (중요)