Ch.5 연결 리스트
노드와 포인터 — ListNode의 탄생
배열이 아닌 다른 방법이 있다?
배열은 연속된 메모리에 데이터를 저장합니다. 하지만 중간에 데이터를 삽입하려면 뒤의 모든 원소를 밀어야 합니다. 이 비효율을 해결하는 자료구조가 바로 연결 리스트입니다.
메모리가 연속되지 않아도 데이터를 연결할 수 있을까?
각 데이터가 다음 데이터의 주소를 기억하면 어디든 연결할 수 있습니다. 이것이 포인터의 힘입니다.
핵심 개념
노드(Node)
데이터와 다음 노드의 주소(포인터)를 담는 단위
포인터(next)
다음 노드의 메모리 주소를 가리키는 참조
head
연결 리스트의 첫 번째 노드를 가리키는 변수
핵심 내용
기차를 떠올려봅시다. 각 칸은 다음 칸과 연결되어 있습니다
배열은 연속 메모리에 저장하지만 연결 리스트는 흩어진 메모리를 포인터로 연결합니다
연결 리스트의 핵심: 각 노드는 데이터(val)와 다음 노드 주소(next)를 가진다
Python으로 노드를 직접 만들어봅시다
class ListNode:
def __init__(self, val=0, next=None):
self.val = val # 데이터
self.next = next # 다음 노드 주소
# 노드 생성
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
# 연결
node1.next = node2
node2.next = node3
# head 설정
head = node1이제 head부터 따라가면 1 → 2 → 3 → None 순서로 방문합니다
head부터 시작해서 next가 None이 될 때까지 이동합니다
def traverse(head):
curr = head
while curr:
print(curr.val)
curr = curr.next배열 vs 연결 리스트: 배열은 인덱스로 O(1) 접근, 연결 리스트는 순회로 O(n) 접근
배열 vs 연결 리스트 비교 접근: 배열 O(1) / 리스트 O(n) 삽입(앞): 배열 O(n) / 리스트 O(1) 삭제(앞): 배열 O(n) / 리스트 O(1) 메모리: 배열 연속 / 리스트 분산(포인터 추가 비용)
def get_length(head):
count = 0
curr = head
while curr:
count += 1
curr = curr.next
return count순회 패턴은 항상 같습니다: curr = head → while curr → curr = curr.next
연결 리스트 순회 템플릿 1. curr = head — 시작점 설정 2. while curr: — None이 아닌 동안 반복 3. curr = curr.next — 다음 노드로 이동
연결 리스트에서 n번째 노드에 접근하는 시간 복잡도는?
ListNode에서 next가 None이면 리스트의 마지막 노드이다
연결 리스트의 첫 번째 노드를 가리키는 변수를 ___라 한다
연결 리스트 순회의 while 조건에서 curr이 None이면 루프를 종료한다
연결 리스트 순회 시 다음 노드로 이동하는 코드: curr = curr.___
노드와 포인터 마스터!
핵심 용어
노드(Node)
데이터 + 다음 노드 주소를 담는 단위
포인터(next)
다음 노드의 메모리 주소를 가리키는 참조
head
리스트의 첫 번째 노드를 가리키는 변수
정리 노트
노드와 포인터 — ListNode
핵심 개념
- ListNode
- val(데이터) + next(다음 노드 주소)
- head
- 리스트의 첫 번째 노드를 가리키는 변수
- 순회 패턴
- curr = head → while curr → curr = curr.next
배열 vs 연결 리스트
- 인덱스 접근
- 배열 O(1) / 연결 리스트 O(n)
- 삽입/삭제
- 배열 O(n) / 연결 리스트 O(1) (위치를 알 때)
면접에서 ListNode 클래스는 보통 주어지지만, 직접 구현할 줄 알아야 응용이 가능하다!
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작