몇 개의 요소로 구성된 연결 리스트가 있다고 가정해 봅시다. 우리의 과제는 주어진 노드를 리스트에서 삭제하는 함수를 작성하는 것입니다. 예를 들어 리스트가 1 → 3 → 5 → 7 → 9와 같을 때, 값이 3인 노드를 삭제하면 결과는 1 → 5 → 7 → 9가 됩니다.
노드 삭제의 핵심 원리
일반적인 연결 리스트에서 노드를 삭제하려면 이전 노드에 대한 참조가 필요하지만, 삭제할 노드 자체를 가리키는 포인터 'node'만 주어진 경우에는 다른 접근 방식을 사용할 수 있습니다. 바로 현재 노드를 다음 노드로 "덮어쓰는" 기법입니다.
삭제할 노드를 가리키는 포인터가 있다고 할 때, 다음 두 가지 연산만 수행하면 됩니다.
node.val = node.next.val— 다음 노드의 값을 현재 노드에 복사합니다.node.next = node.next.next— 현재 노드가 다다음 노드를 가리키도록 링크를 변경합니다.
이렇게 하면 원래 노드의 데이터는 사라지고, 사실상 다음 노드가 현재 위치로 이동한 것과 같은 효과를 얻게 됩니다. 시간 복잡도는 O(1)로 매우 효율적이라는 장점이 있습니다.
파이썬 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end="")
while ptr:
print(ptr.val, end=", ")
ptr = ptr.next
print(']')
class Solution(object):
def deleteNode(self, node, data):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
while node.val is not data:
node = node.next
node.val = node.next.val
node.next = node.next.next
head = make_list([1, 3, 5, 7, 9])
ob1 = Solution()
ob1.deleteNode(head, 3)
print_list(head)입력
linked_list = [1, 3, 5, 7, 9] data = 3
출력
[1, 5, 7, 9]
동작 방식 살펴보기
위 코드의 실행 흐름은 다음과 같습니다.
make_list함수는 [1, 3, 5, 7, 9] 배열을 받아 연결 리스트를 생성하고 헤드 노드를 반환합니다.deleteNode메서드는 값이 3인 노드를 찾을 때까지 리스트를 순회합니다.- 해당 노드를 발견하면 다음 노드(5)의 값을 복사하고, 링크를 재설정하여 노드를 삭제합니다.
- 최종적으로 리스트는 [1, 5, 7, 9]가 되어 출력됩니다.
주의할 점
이 기법은 삭제할 노드가 리스트의 마지막(tail) 노드인 경우에는 사용할 수 없습니다. 마지막 노드에는 다음 노드가 존재하지 않아 값을 복사할 수 없기 때문입니다. 또한 위 예제에서는 값 비교에 is 연산자를 사용했는데, 실제 프로덕션 코드에서는 정수 객체 캐싱 동작에 따라 의도치 않은 결과가 나올 수 있으므로 == 연산자를 사용하는 것이 더 안전합니다.