연결 리스트(Linked List)란?

연결 리스트(Linked List)는 노드(Node)들이 포인터로 연결된 자료구조

배열과 다르게 연속된 메모리 공간이 필요 없고, 동적으로 크기를 조절할 수 있는 장점

하지만 접근 속도가 느리고, 추가적인 메모리(포인터)가 필요함

---

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

1. 메모리 구조
   • 배열: 연속된 메모리 할당
   • 연결 리스트: 비연속적인 메모리 할당
2. 삽입/삭제 속도
   • 배열: 느림(O(N), 요소 이동 필요)
   • 연결 리스트: 빠름(O(1), 포인터만 변경)
3. 검색 속도
   • 배열: 빠름(O(1), 인덱스로 접근 가능)
   • 연결 리스트: 느림(O(N), 처음부터 탐색)
4. 추가 메모리
   • 배열: 필요 없음
   • 연결 리스트: 노드마다 포인터(next) 필요

---

연결 리스트의 기본 개념

• 연결 리스트는 노드(Node)들로 구성되며, 각 노드는 데이터(data)와 다음 노드를 가리키는 포인터(next)를 갖고 있음
• 연결 리스트는 첫 번째 노드(head)만 알고 있으면 전체 리스트를 탐색할 수 있음.

연결 리스트의 노드 구조

![

• 각 노드(Node)는 데이터 + 다음 노드의 주소(next)를 저장
• 마지막 노드는 None(=끝)을 가리킴

---

연결 리스트의 종류

1. 단일 연결 리스트(Singly Linked List)
   • 각 노드가 다음 노드(next)만 가리킴
   • 단방향으로만 이동 가능
2. 이중 연결 리스트(Doubly Linked List)
   • 각 노드가 이전 노드(prev)와 다음 노드(next)를 모두 가짐
   • 양방향 이동 가능
3. 원형 연결 리스트(Circular Linked List)
   • 마지막 노드가 다시 처음 노드(head)를 가리킴
   • 무한히 순환할 수 있음

프리 리스트(Free List)

• 삭제된 레코드를 관리할 때 사용하는 자료구조
• 프리 리스트를 사용하면 삭제 후 발생하는 빈 공간 문제를 해결할 수 있음.

---

연결 리스트의 기본 연산

1) 노드 삽입 (Insert)

• 맨 앞(head)에 삽입 (O(1), 빠름)

  class Node:
      def __init__(self, data):
          self.data = data
          self.next = None
  
  class LinkedList:
      def __init__(self):
          self.head = None
  
      def insert_front(self, data):
          new_node = Node(data)
          new_node.next = self.head
          self.head = new_node

• 맨 끝에 삽입 (O(N), 마지막 노드 찾기 필요)

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

2) 노드 삭제 (Delete)

• 맨 앞(head) 삭제 (O(1), 빠름)

  def delete_front(self):
      if self.head:
          self.head = self.head.next

• 중간 또는 끝 노드 삭제 (O(N), 탐색 필요)

  def delete_value(self, key):
      temp = self.head
      if temp and temp.data == key:
          self.head = temp.next
          return
      prev = None
      while temp and temp.data != key:
          prev = temp
          temp = temp.next
      if temp:
          prev.next = temp.next

3) 탐색 (Search)

• 노드를 찾을 때까지 순차 탐색 (O(N))

  def search(self, key):
      temp = self.head
      while temp:
          if temp.data == key:
              return True
          temp = temp.next
      return False

4) 연결 리스트 출력

  def print_list(self):
      temp = self.head
      while temp:
          print(temp.data, end=" → ")
          temp = temp.next
      print("None")

---

연결 리스트의 시간 복잡도

연산	평균 시간 복잡도
삽입(Insert) 맨 앞	O(1)
삽입(Insert) 맨 끝	O(N)
삭제(Delete) 맨 앞	O(1)
삭제(Delete) 맨 끝	O(N)
탐색(Search)	O(N)

---

연결 리스트 vs. 배열 정리

1. 메모리 구조
   • 연결 리스트: 동적 할당, 비연속적
   • 배열: 연속된 메모리
2. 접근 속도
   • 연결 리스트: 느림(O(N))
   • 배열: 빠름(O(1))
3. 삽입/삭제
   • 연결 리스트: 빠름(O(1))
   • 배열: 느림(O(N), 요소 이동 필요)
4. 추가 메모리
   • 연결 리스트: 포인터 필요
   • 배열: 필요 없음

---

연결 리스트 정리

장점

• 동적으로 크기 조절 가능
• 삽입/삭제가 빠름 (O(1), 맨 앞 기준)

단점

• 인덱스 접근 불가능 (O(N), 순차 탐색 필요)
• 추가적인 메모리 필요 (포인터 저장)

언제 사용하면 좋을까?

• 빈번한 삽입/삭제가 필요한 경우
• 리스트 크기가 자주 변하는 경우