배열과 연결리스트

배열(Array)과 연결리스트(Linked List)는 가장 기본적인 선형 자료구조입니다.

배열

연속된 메모리 공간에 데이터를 저장합니다.

인덱스:  [0] [1] [2] [3] [4]
값:      10  20  30  40  50

• 장점: $O(1)$ 랜덤 접근
• 단점: 삽입/삭제 시 $O(n)$ 이동 필요

연결리스트

각 노드가 다음 노드를 가리킵니다. (포인터의 힘!)

• 장점: $O(1)$ 삽입/삭제 (위치를 알 때)
• 단점: $O(n)$ 탐색 — 인덱스 접근 불가

언제 뭘 쓰나?

랜덤 접근이 많으면 배열, 삽입/삭제가 많으면 연결리스트. 면접에서 이것만 대답해도 반은 먹고 들어간다