Chapter 2 정리 - 리스트 구조 완전 정복

📌 과목 개요

• 과목명: 자료구조
• 교재: 『파이썬으로 쉽게 배우는 자료구조 (개정판)』 - 최영규, 천인국
• 중간고사 범위: Chapter 1 ~ Chapter 3
• 시험 스타일: 리스트 코드 구현, 연결 리스트 구조 이해, 시간복잡도 분석

---

📚 Chapter 2 핵심 개념 요약

1. 리스트(List)란?

• 데이터들을 순차적으로 나열한 자료구조
• 파이썬에서는 list 타입으로 제공됨

 

2. 배열 기반 리스트 (Array-based List)

• 연속된 메모리 공간에 저장
• 접근 속도 빠름 (O(1)), 삽입/삭제는 느림 (O(n))

arr = [1, 2, 3, 4]
arr.insert(2, 99)  # 2번 인덱스에 삽입 → 시간복잡도 O(n)
arr.pop(1)         # 1번 인덱스 삭제

 

3. 연결 리스트 (Linked List)

• 노드(Node)들이 포인터로 연결된 구조
• 동적 메모리 할당 → 크기 제한 없음
• 삽입/삭제는 빠름 (O(1)), 접근은 느림 (O(n))

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

# 리스트의 시작점
head = Node(1)
second = Node(2)
head.next = second

 

4. 단일 연결 리스트 vs 이중 연결 리스트

• 단일 연결 리스트: 다음 노드만 가리킴 (next)
• 이중 연결 리스트: 이전, 다음 노드 모두 가리킴 (prev, next)

 

5. 시간복잡도 비교 요약

연산	배열 기반 리스트	연결 리스트
접근 (get)	O(1)	O(n)
삽입/삭제	O(n)	O(1) (노드 위치 알고 있을 때)

 

---

💡 자주 나오는 시험 유형

• 삽입/삭제 시 시간복잡도 비교
• 연결 리스트 구현 코드에서 head, next의 흐름 분석
• 파이썬 리스트와 연결 리스트의 차이 설명
• 연결 리스트 직접 구현 (class Node, class LinkedList 등)

---

🎯 교수님이 강조한 포인트

• 연결 리스트는 포인터 구조를 그려서 이해할 것
• 배열 기반 리스트는 삽입/삭제 시 index 이동 발생
• 파이썬 list와 자료구조적 리스트는 구현 방식이 다르다는 점 인지할 것

---

📌 내 오답노트 & 복습 포인트

• 연결 리스트에서 head = head.next 잘못 써서 기존 노드 날림
• 배열에서 삽입 시 시간복잡도 O(1)이라 착각 → 실제로는 index 이동 있음
• 포인터 연습 부족으로 NoneType 오류 자주 발생

---

📝 마무리 요약

• 리스트는 자료구조 공부의 기본 중 기본!
• 연결 리스트는 손으로 그려가며 포인터 흐름 이해가 핵심
• 시간복잡도는 삽입/삭제/접근을 분리해서 기억해야 실수하지 않음

---

📘 다음 편 예고
《전공이 밥 먹여준다믄 - 자료구조 Chapter 3 정리》
스택과 큐 - 선입선출 vs 후입선출 구조 완벽 비교