배열 vs 연결리스트 완전 비교: 자료구조 선택 기준과 실제 예제 코드

배열 vs 연결리스트 완전 비교: 자료구조 선택 기준과 실제 예제 코드

자료구조를 공부하다 보면 가장 먼저 마주치는 두 구조가 바로 배열(Array) 과 **연결리스트(Linked List)**입니다. 이 두 자료구조는 겉보기에는 유사해 보이지만, 메모리 사용 방식, 삽입/삭제 성능, 접근 방식 등에서 큰 차이를 보입니다.

이번 글에서는 배열과 연결리스트의 핵심 차이점부터 장단점, 그리고 실제 코드를 통한 시간복잡도 분석까지 정리해보겠습니다.

---

✅ 배열(Array)란?

배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조입니다.
각 요소는 인덱스를 통해 O(1) 시간에 바로 접근할 수 있습니다.

🔹 특징

• 빠른 접근 속도 (O(1))
• 삽입/삭제가 느림 (중간 삽입/삭제 시 O(n))
• 메모리가 연속적으로 필요함

📌 예제 코드

arr = [10, 20, 30, 40]

# 인덱스를 이용한 접근
print(arr[2])  # O(1), 출력: 30

# 중간에 값 삽입
arr.insert(2, 99)  # O(n), 30 앞에 99 삽입
print(arr)  # [10, 20, 99, 30, 40]

---

✅ 연결리스트(Linked List)란?

반응형

연결리스트는 각 요소(Node)가 다음 노드에 대한 참조를 포함하는 자료구조입니다.
연속된 메모리 공간을 사용하지 않고, 노드 단위로 메모리를 할당합니다.

🔹 특징

• 동적 메모리 관리 가능 (중간 삽입/삭제가 O(1))
• 접근 속도 느림 (임의 접근이 O(n))
• 구현이 배열보다 복잡

📌 예제 코드

# 단일 연결 리스트 구현
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 리스트 생성
head = Node(10)
second = Node(20)
third = Node(30)

head.next = second
second.next = third

# 순차 탐색
current = head
while current:
    print(current.data, end=" -> ")
    current = current.next
# 출력: 10 -> 20 -> 30 ->

---

🔍 성능 비교 (시간복잡도)

연산 배열 (Array) 연결리스트 (Linked List)

접근 (Access)	O(1)	O(n)
삽입 (Insert)	O(n)	O(1)*
삭제 (Delete)	O(n)	O(1)*
메모리 사용	연속적	비연속적

*연결리스트는 해당 노드의 참조(포인터)를 알고 있다는 전제 하에 삽입/삭제가 O(1)입니다.

---

🤔 언제 어떤 자료구조를 선택해야 할까?

상황 추천 자료구조 이유

빠르게 특정 위치의 데이터를 조회해야 할 때	배열	O(1) 접근
삽입/삭제가 빈번할 때	연결리스트	O(1) 삽입/삭제
크기가 유동적인 데이터 저장이 필요할 때	연결리스트	유동적 메모리 할당
메모리 효율과 캐시 친화성이 중요할 때	배열	메모리 접근 최적화

---

🧪 실제로 비교해보자

배열에서 중간 삭제

arr = [1, 2, 3, 4, 5]
arr.pop(2)  # O(n) → [1, 2, 4, 5]

연결리스트에서 중간 삭제

# 삭제할 노드 앞 노드가 필요함
second.next = third.next  # 20 다음 노드를 30 → 40으로 변경

---

💡 배열과 연결리스트 혼합형: 파이썬의 리스트는?

파이썬의 list는 **동적 배열(Dynamic Array)**입니다.

• 내부적으로는 배열과 비슷하지만 크기가 자동 조절됨.
• 메모리가 부족하면 더 큰 공간을 새로 할당 후 복사하는 방식으로 확장됨.

---

📌 결론 및 요약

• 배열은 접근 속도가 빠르고, 연결리스트는 삽입/삭제가 빠른 구조입니다.
• 문제의 특성과 연산 패턴에 따라 자료구조를 선택하는 것이 중요합니다.
• 현업에서도 알고리즘보다 자료구조 선택이 더 중요한 경우가 많습니다.

👉 다음 글에서는 스택과 큐의 구조와 사용 사례를 실제 예제와 함께 알아보겠습니다.

---

📚 참고자료 및 출처

• 『Introduction to Algorithms (CLRS)』
• 『파이썬으로 배우는 자료구조』(한빛미디어)
• Python Docs – List