노드 클래스와 리스트 구성
Node 데이터 클래스를 정의하고 노드를 직접 연결해 리스트를 만든 뒤, 포인터 변화를 시각화하는 삽입·삭제·출력 보조 함수를 작성합니다.
노드 클래스와 리스트 구성은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
연결 리스트란 무엇인가요
연결 리스트는 각 노드가 값과 다음 노드를 가리키는 포인터를 저장하는 노드의 연속 구조입니다. 배열과 달리 노드가 메모리 곳곳에 흩어져 있으므로 인덱스를 이용한 O(1) 접근이 없습니다. 대신 알려진 위치에서 요소를 이동하지 않고 O(1) 시간에 삽입하고 삭제할 수 있습니다.
Python에서는 val과 next를 보유한 작은 클래스로 각 노드를 표현합니다. 노드를 서로 연결하면 리스트가 만들어지며, 마지막 노드의 next는 끝을 나타내기 위해 None이 됩니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')배열에서 리스트 만들기
면접에서는 리스트가 주어지고 연결 리스트로 변환하거나, 그 반대 작업을 하라는 요구를 자주 받습니다. 보조 함수인 build와 to_list는 외워 두면 유용합니다. build는 배열의 요소로 노드를 연결하고, to_list는 리스트를 순회하며 값을 수집해 쉽게 확인할 수 있도록 합니다.
n개의 요소로 연결 리스트를 만드는 데는 O(n) 시간과 O(n) 공간이 필요합니다. 더미 헤드 노드를 사용하면 첫 번째 노드가 바뀔 수 있는 경계 상황을 간단히 처리할 수 있습니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]헤드와 tail에 삽입하기
헤드에 새 노드를 삽입하는 작업은 O(1)입니다. 노드를 만들고, 그 노드의 next가 기존 헤드를 가리키도록 한 다음, 새 노드를 헤드로 반환하면 됩니다. tail에 삽입하려면 마지막 노드까지 순회해야 하므로 O(n) 시간이 걸린 뒤 새 노드를 연결합니다.
더미 헤드 노드를 사용하면 두 삽입 작업에서 빈 리스트를 위한 특수 처리가 필요하지 않습니다. dummy.next가 항상 실제 헤드를 가리키기 때문입니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> None값으로 노드 삭제하기
주어진 값과 일치하는 첫 번째 노드를 삭제하려면 curr보다 한 단계 앞에 있는 prev 포인터를 유지합니다. curr.val == target이면 prev.next = curr.next로 설정해 해당 노드를 건너뜁니다. 더미 헤드는 실제 헤드 노드를 삭제하는 특수한 경우를 없애 주므로 특히 유용합니다. prev를 항상 더미 노드에서 시작할 수 있기 때문입니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))포인터 변경 시각화하기
포인터를 변경할 때 노드를 추적하지 못하는 것은 흔한 실수입니다. 덮어쓰기 전에 항상 next를 저장하십시오. 즉, saved = curr.next로 저장한 다음 다시 할당합니다. 리스트를 화살표로 연결된 상자로 그린 뒤, 코드를 작성하기 전에 각 포인터 변경을 종이에 직접 따라 해 보십시오. 이러한 시각적 접근은 면접 중에 발생할 수 있는 실수로 인한 널 포인터 오류를 예방합니다.
Python에서는 curr.next를 다시 할당해도 curr 자체에는 영향을 주지 않습니다. 하지만 저장하기 전에 curr.next에 대한 참조를 잃으면 더 이상 앞으로 순회할 수 없습니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4단일 연결 리스트와 이중 연결 리스트
단일 연결 리스트는 next 포인터만 저장하므로 한 방향으로만 순회할 수 있습니다. 이중 연결 리스트는 prev와 next를 모두 저장하므로 뒤로 O(1) 시간에 순회할 수 있으며, 노드를 직접 참조하고 있다면 O(1) 시간에 삭제할 수도 있습니다. 이때 prev를 추적하는 반복문이 필요하지 않습니다.
Python의 collections.deque는 이중 연결 리스트로 구현되어 있으므로 O(1) 시간에 appendleft와 popleft를 지원합니다. 면접에서는 단일 연결 리스트를 구현하게 되며, 이중 연결 리스트는 LRU 캐시 설계에 등장합니다.
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')길이, tail 및 출력 보조 함수
연결 리스트 면접에서 항상 준비해 두어야 할 세 가지 유틸리티 함수가 있습니다. length(head)는 O(n) 시간에 노드 수를 세고, tail(head)은 O(n) 시간에 마지막 노드를 반환하며, print_list(head)는 리스트를 오류 확인에 적합한 형식으로 출력합니다. 이러한 함수를 미리 준비해 두면 보조 로직을 다시 구현하는 대신 핵심 알고리즘에 집중할 수 있습니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)연결 리스트에서 두 포인터 설정하기
두 포인터 기법은 배열에서만큼 연결 리스트에서도 중요하지만, 포인터가 인덱스가 아니라 연결 리스트의 노드라는 차이가 있습니다. 대표적인 설정으로는 중간 지점을 찾고 순환을 감지하기 위한 느린 포인터와 빠른 포인터(빠른 포인터가 2배 빠르게 이동)와 삭제 및 뒤집기를 위한 선행 노드와 현재 노드 쌍이 있습니다.
두 포인터는 항상 명시적으로 초기화하고, 널 종료 검사를 신중하게 처리하십시오. 빠른 포인터가 끝에 가까이 있을 때 fast and fast.next가 널 포인터 오류를 방지합니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)더미 헤드 패턴
더미 헤드(센티넬 노드) 패턴은 연결 리스트 문제에서 가장 유용한 기법 중 하나입니다. 값이 0인 더미 노드를 앞에 추가하면 빈 리스트나 실제 헤드의 변경을 별도로 처리할 필요가 없습니다. 결과는 항상 dummy.next입니다. 이 패턴은 정렬된 리스트 병합, 끝에서 n번째 노드 삭제, 리스트 분할을 비롯한 여러 문제에 등장합니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]시간 및 공간 복잡도
대부분의 연결 리스트 연산은 다음과 같은 복잡도를 가집니다. 인덱스로 접근: O(n) — 헤드부터 순회해야 합니다. 알려진 노드에 삽입 또는 삭제: O(1) — 포인터만 다시 연결하면 됩니다. k번째 위치에 삽입 또는 삭제: O(k) — 먼저 순회해야 합니다. 검색: O(n) — 최악의 경우 리스트 전체를 확인합니다. 추가 자료 구조를 제외하면 모든 제자리 연산의 공간 복잡도는 O(1)입니다.
배열과 비교해 보십시오. 배열은 O(1) 접근을 제공하지만 요소를 이동해야 하므로 삽입과 삭제에 O(n)이 걸립니다. 임의의 위치에서 삽입과 삭제가 자주 일어날 때는 연결 리스트가 더 적합합니다.
연결 리스트 면접 팁
연결 리스트 코드를 작성하기 전에 상자와 화살표를 사용해 리스트를 시각적으로 그리십시오. 빈 리스트, 노드 하나인 경우, 길이가 짝수인 경우와 홀수인 경우 같은 경계 상황을 소리 내어 확인하십시오. 더미 헤드를 사용해 경계 조건을 간단히 처리하십시오. 처음에 항상 if not head를 확인하십시오. 코드를 작성한 후에는 3개 노드로 이루어진 리스트에서 풀이를 따라가며 면접관이 발견하기 전에 포인터 오류를 찾아내십시오.
연결 리스트의 대부분의 오류는 세 가지 원인에서 발생합니다. 덮어쓰기 전에 next를 저장하지 않는 것, 종료 조건에서 하나를 잘못 세는 것, 헤드가 바뀌는 경계 상황을 처리하지 않는 것입니다. 더미 노드는 세 번째 문제를 완전히 없애 줍니다.
빠른 확인
이 레슨에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 얼마나 이해했는지 확인해 보십시오.
레슨 요약
이 레슨에서는 다음을 배웠습니다. 연결 리스트는 값 필드와 다음 노드 필드를 가진 노드 객체로 구성됩니다. 더미 헤드 패턴은 헤드 변경에 따른 경계 상황을 없애 줍니다. 또한 느린 포인터와 빠른 포인터를 사용하는 두 포인터 설정은 중간 지점 찾기와 순환 감지의 기초입니다. 다음에는 가장 자주 출제되는 포인터 문제 중 하나인 연결 리스트 뒤집기를 다룹니다.
자주 묻는 질문
“노드 클래스와 리스트 구성” 강의는 무료인가요?
네 — “노드 클래스와 리스트 구성” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“노드 클래스와 리스트 구성”에서 뭘 배우나요?
Node 데이터 클래스를 정의하고 노드를 직접 연결해 리스트를 만든 뒤, 포인터 변화를 시각화하는 삽입·삭제·출력 보조 함수를 작성합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“노드 클래스와 리스트 구성” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 노드 클래스와 리스트 구성
- 연결 리스트 뒤집기
- Floyd 알고리즘으로 순환 탐지
- 병합, 분할, 뒤에서 N번째 찾기