연결 리스트와 배열은 모두 데이터를 순차적으로 저장하는 선형 자료구조이지만, 그 저장 방식과 작동 원리, 시간 복잡도 등에서 중요한 차이가 존재한다.

---

1️⃣ 메모리 구조

✅ 배열 (Array)

• 배열은 연속된 메모리 공간에 데이터를 저장한다.

• Python에서는 list 타입이 동적 배열(Dynamic Array)로 구현되어 있다.

• 메모리에 한번에 연속적으로 확보되어야 하므로, 크기 변경 시 전체 복사가 발생할 수 있다.

✅ 연결 리스트 (Linked List)

• 

  연결 리스트는 노드(Node)라 불리는 요소들이 포인터(참조)로 연결된 구조이다.

• 각각의 노드는 다음 노드가 위치한 주소 값을 갖고 있어야 한다.

• 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함한다.

• 메모리는 비연속적으로 할당되며, 필요할 때마다 동적으로 생성되기 때문에 메모리 상의 빈 공간들을 활용하기 좋다.

---

2️⃣ 데이터 접근 방식

✅ 배열

• 인덱스를 사용한 임의 접근(random access)이 가능하다.

• 예: arr[3]은 바로 4번째 요소를 참조할 수 있다.

• 시간 복잡도는 O(1)이다.

✅ 연결 리스트

• 순차 접근(sequential access)만 가능하다.

• 예: 4번째 요소에 접근하려면 첫 번째 노드부터 차례로 탐색해야 한다.

• 시간 복잡도는 O(n)이다.

---

3️⃣ 삽입 및 삭제 연산

• 연결 리스트는 포인터만 수정하면 되기 때문에 맨 앞 삽입/삭제가 빠르다.

• 배열은 삽입/삭제 시 전체 요소를 한 칸씩 이동해야 하기 때문에 비효율적이다.

---

4️⃣ 공간 효율성

✅ 배열

• 요소만 저장하면 되므로 오버헤드가 적다.

• 하지만 크기 변경 시 빈 공간이 남거나 전체 복사가 필요할 수 있다.

✅ 연결 리스트

• 각 노드마다 포인터(참조)를 저장해야 하므로 메모리 오버헤드가 있다.

• 하지만 데이터 삽입/삭제가 잦은 경우 효율적이다.

---

5️⃣ Python에서의 구현 예시

배열

arr = [1, 2, 3, 4]
print(arr[2])  # O(1) 접근

단일 연결 리스트

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

ll = LinkedList()
ll.head = Node(1)
ll.head.next = Node(2)

---

🧠 요약 비교표

---

✅ 정리

• 배열은 빠른 접근 속도와 간단한 구조가 장점이지만, 삽입/삭제에는 비효율적이다.

• 연결 리스트는 동적 메모리 관리, 빠른 삽입/삭제가 가능하지만, 접근 속도가 느리고 구현이 복잡하다.

• Python에서는 기본적으로 배열 기반 list를 많이 사용하지만, 특정 상황(삽입/삭제 빈번한 작업)에서는 연결 리스트를 직접 구현해 사용하는 것이 더 적합할 수 있다.

---

🧠 Python에서 배열 vs 연결 리스트 – 상황별 선택 가이드

✅ 간단 비교 요약

---

📌 상황별 설명과 예시

1️⃣ 많은 데이터를 읽기만 할 때

• 예: 대량의 센서 데이터를 불러와 평균값을 구하는 작업

• 추천: ✅ 배열 (list)

• 이유: 인덱스를 통해 O(1) 시간에 바로 접근할 수 있으며, 읽기만 한다면 리스트가 가장 효율적이다.

---

2️⃣ 맨 앞에 자주 삽입해야 할 때

• 예: 최근 사용 항목을 가장 앞에 추가하는 캐시 구조

• 추천: ✅ 연결 리스트 또는 collections.deque

• 이유: 배열에서는 모든 요소를 한 칸씩 밀어야 하므로 O(n), 반면 연결 리스트는 O(1)에 가능하다.

---

3️⃣ 중간에 자주 삽입/삭제할 때

• 예: 텍스트 에디터에서 커서 위치를 기준으로 문자를 삽입/삭제하는 경우

• 추천: ✅ 연결 리스트

• 이유: 배열은 해당 위치 이후의 모든 요소를 이동시켜야 하지만, 연결 리스트는 포인터 수정만으로 처리 가능하다.

---

4️⃣ 데이터 크기가 자주 바뀌는 경우

• 예: 사용자 입력에 따라 동적으로 리스트가 커지거나 작아지는 상황

• 추천: ✅ 연결 리스트

• 이유: 배열은 크기가 부족해지면 복사 및 재할당이 발생할 수 있다. 연결 리스트는 크기 변화에 유연하다.

---

5️⃣ 데이터가 작고 단순한 작업일 때

• 예: 학생 이름을 저장하고 출력하는 단순한 리스트

• 추천: ✅ 배열 (list)

• 이유: 배열은 구현이 쉽고, Python의 list는 다용도로 쓸 수 있으며 속도도 빠르다.

---

6️⃣ 대량의 정렬 작업이 필요한 경우

• 예: 숫자 수천만 개를 정렬해야 할 때

• 추천: ✅ 배열 (list)

• 이유: 연결 리스트는 정렬 알고리즘에서 불리하고, 배열은 Python의 sort() 등을 통해 빠르게 정렬 가능하다.

---

7️⃣ 큐(Queue)나 스택(Stack)처럼 사용할 때

• 예: BFS, DFS, 작업 순서 처리 등

• 추천: ✅ collections.deque

• 이유: Python의 list는 맨 앞 삽입/삭제에 비효율적이므로, deque를 사용하면 O(1)로 처리할 수 있다.

from collections import deque

q = deque()
q.append(1)      # enqueue
q.popleft()      # dequeue

---

✅ 정리: 언제 배열, 언제 연결 리스트?

---