연결 리스트 (Linked List)

연결 리스트 (선형)

각 노드가 데이터와 다음 노드를 가리키는 포인터를 포함하는 자료구조

• 종류로 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트
• 배열보다 메모리 낭비가 없고 크기 변경이 용이
• 포인터 변경만 하면 되므로 삽입 / 삭제가 빠름 → O(1)
• 특정 인덱스 접근이 느림 → O(n)
• 사용 예제: 텍스트 편집