Ch.5 연결 리스트
삽입과 삭제 — 연결 리스트의 진짜 강점
포인터 하나만 바꾸면 삽입 끝?
배열에서 중간 삽입은 뒤의 모든 원소를 밀어야 하지만, 연결 리스트에서는 포인터 2개만 수정하면 됩니다. 하지만 head 삽입과 중간 삽입은 코드가 다릅니다.
head에 삽입할 때와 중간에 삽입할 때를 어떻게 통일할까?
dummy head(가짜 노드)를 쓰면 모든 삽입/삭제를 하나의 로직으로 처리할 수 있습니다.
핵심 내용
리스트 맨 앞에 새 노드를 삽입합니다
def insert_at_head(head, val):
new_node = ListNode(val)
new_node.next = head # 새 노드가 기존 head를 가리킴
return new_node # 새 노드가 새로운 head시간 복잡도: O(1) 포인터 연결만 바꾸면 끝입니다
특정 위치에 삽입하려면 이전 노드(prev)를 먼저 찾아야 합니다
def insert_at_index(head, index, val):
if index == 0:
return insert_at_head(head, val)
curr = head
for _ in range(index - 1): # prev 위치로 이동
if not curr:
return head
curr = curr.next
new_node = ListNode(val)
new_node.next = curr.next # 새 노드 → 다음 노드
curr.next = new_node # 이전 노드 → 새 노드
return head삽입 핵심 순서: new_node.next = curr.next → curr.next = new_node (순서가 바뀌면 연결이 끊김!)
삭제도 이전 노드(prev)를 찾아 prev.next를 건너뛰게 합니다
def delete_at_index(head, index):
if index == 0:
return head.next # head 삭제
curr = head
for _ in range(index - 1):
curr = curr.next
curr.next = curr.next.next # 건너뛰기
return headhead 삭제를 특별 처리하기 싫다면? 가짜 노드(dummy)를 앞에 붙입니다
def delete_at_index_v2(head, index):
dummy = ListNode(0) # 가짜 노드
dummy.next = head
curr = dummy
for _ in range(index):
curr = curr.next
curr.next = curr.next.next
return dummy.next # 진짜 head 반환dummy head 패턴: head가 바뀔 수 있는 모든 연결 리스트 문제에서 사용. 면접 필수 테크닉!
삽입/삭제 시간 복잡도 Head 삽입/삭제: O(1) 중간 삽입/삭제: O(n) — prev 찾는 데 O(n) Tail 삽입: O(n) — 끝까지 순회 필요
dummy head를 사용한 삽입 코드를 봅시다
def insert_at_index_v2(head, index, val):
dummy = ListNode(0)
dummy.next = head
curr = dummy
for _ in range(index):
curr = curr.next
new_node = ListNode(val)
new_node.next = curr.next
curr.next = new_node
return dummy.nextdummy head 덕분에 index == 0 체크 없이 하나의 로직으로 모든 위치에 삽입 가능!
연결 리스트 중간에 노드를 삽입할 때, 포인터 연결 순서로 올바른 것은?
dummy head를 사용하면 head 삭제와 중간 삭제를 같은 로직으로 처리할 수 있다
연결 리스트 head에 새 노드를 삽입하는 시간 복잡도: O(___)
삽입과 삭제 정복!
정리 노트
삽입과 삭제 — 연결 리스트의 강점
핵심 연산
- Head 삽입
- new.next = head → head = new / O(1)
- 중간 삽입
- new.next = prev.next → prev.next = new / O(n)
- 삭제
- prev.next = prev.next.next / O(n)
면접 필수
- dummy head
- head 변경 가능한 문제에서 엣지 케이스 제거
- 포인터 순서
- new.next 먼저 연결 → 그 다음 prev.next 수정
면접관은 '엣지 케이스를 어떻게 처리하나요?'라고 묻는다. dummy head를 말하면 신뢰도 UP!
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작