박종훈 기술블로그

단방향 연결리스트의 중간 노드 삭제

중간 노드 삭제: 단방향 연결리스트가 주어졌을 때 중간(정확히는 가운데 노드일 필요는 없고 처음과 끝 노드만 아니면 된다)에 있는 노드 하나를 삭제하는 알고리즘을 구현하라. 단, 삭제할 노드에만 접근할 수 있다.

삭제할 노드(A) 접근 → 다음 노드(B = A.next) 접근
→ A.next = B.next, A.value = B.value 하면
A 노드가 사라지게 된다.

코드

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

def delete_node_in_middle(node_to_delete):
    # 첫 번째 노드나 마지막 노드는 삭제할 수 없다고 명시되어 있기 때문에 고려하지 않음.

    # 다음 노드의 값을 현재 노드로 복사
    next_node = node_to_delete.next

    node_to_delete.next = next_node.next
    node_to_delete.val = next_node.val

node4 = Node(4)
node3 = Node(3, node4)
node2 = Node(2, node3)
node1 = Node(1, node2)
head = Node(0, node1)

print("# 삭제 전")
current_node = head
while current_node:
    print(current_node.val, end=" -> ")
    current_node = current_node.next
print("None")

delete_node_in_middle(node2)

print("# 삭제 후")
current_node = head
while current_node:
    print(current_node.val, end=" -> ")
    current_node = current_node.next
print("None")

출력

# 삭제 전
0 -> 1 -> 2 -> 3 -> 4 -> None
# 삭제 후
0 -> 1 -> 3 -> 4 -> None

Python Print

print(*objects, sep=' ', end='\n', file=None, flush=False)
print의 기본 end 값은 \n이다.