Linked List란?

연결 리스트는 데이터를 "노드(node)"로 저장하고, 각 노드가 다음 노드의 주소를 가리키는 자료구조이다.

💡 배열과 달리 연속된 공간에 저장하지 않고, 노드끼리 연결된다.
연결리스트는 배열처럼 일렬로 붙어있지 않고, 마치 떨어진 그룹처럼 있다.

---

각 칸은 다음 주소를 가리키는 포인터를 가지고 있기 때문에, 메모리 주소가 연속되지 않아도 된다.
그림에서 a는 b의 주소를 b는 c의 주소를 가리키고 있기때문에, 잘 찾아갈 수 있는 것 !

---

☑️ 구조

하나의 노드(node) = 데이터 + 다음 노드를 가리키는 포인터(next)

예시:

[1 | next] → [3 | next] → [5 | next] → None

• 1은 첫 번째 값, next는 다음 노드의 주소

---

☑️ 배열 vs 연결 리스트

개념	배열 (Array)	연결 리스트 (Linked List)
저장 방식	메모리 연속 공간에 저장	메모리 흩어진 공간에 노드끼리 연결
삽입/삭제	O(N) (중간 삽입/삭제 느림)	O(1) (노드만 수정하면 됨)
접근 속도	빠름 (O(1))	느림 (O(N))

💡 연결리스트에서 접근 속도가 느린 이유

배열에서는 위치의 데이터에 즉시 접근가능하다.
하지만 연결 리스트는 각 노드가 다음 노드의 주소만 알고 있기 때문에, 맨 앞부터 차례차례 따라가며 이동해야 한다.

🎯 예를 들어, c에 접근하려면
a에게 b의 주소를 물어보고, b에게 c의 주소를 다시 물어봐야 도달할 수 있다!

---

☑️ 연결 리스트 종류

1. 단일 연결 리스트 (Singly Linked List)

   → 앞에서 뒤로만 연결

2. 이중 연결 리스트 (Doubly Linked List)

   → 앞뒤로 연결 (next & prev 포인터)

3. 원형 연결 리스트 (Circular Linked List)

   → 마지막 노드가 첫 노드를 가리킴

---

☑️ 단일 연결 리스트 기본 구현 (파이썬)

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node

    def print_list(self):
        cur = self.head
        while cur:
            print(cur.data, end=' -> ')
            cur = cur.next
        print('None')

---

☑️ 사용 예시

ll = LinkedList()
ll.append(1)
ll.append(3)
ll.append(5)
ll.print_list()

출력:

1 -> 3 -> 5 -> None

---

☑️ 시간 복잡도

연산	시간 복잡도
삽입 (끝에)	O(N) (끝까지 탐색 필요)
삭제	O(N)
앞에 삽입	O(1) (head 앞에 바로 추가 가능)
탐색	O(N)

---

☑️ 언제 사용하나?

• 중간에 자주 삽입/삭제가 필요한 경우
• 메모리가 연속되지 않아도 될 때

---

☑️ 이중 연결 리스트 차이점

• prev 포인터가 추가됨

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

→ 양방향으로 이동 가능

---

🎯 요약

Linked List = 노드끼리 포인터로 이어진 자료구조,

삽입/삭제는 빠르지만 탐색은 느림