[Data Structure] 단일 연결 리스트, Singly Linked-List

---

연결 리스트 (Linked-List)

추상적 자료형인 리스트를 구현한 자료구조
데이터를 저장 할 때 하나의 데이터와 다음 데이터의 위치를 함께 저장하여, 논리적으로 연결하는 방식으로 자료를 저장

❓ 리스트란
순열(Sequence)라고도 불리며, 순서를 가지고 일렬로 나열한 원소들의 모임으로 정의
순서가 있다는 점에서 집합과는 구별되며,
갈림길 없이 일렬로 나열되어 처음과 끝이 하나만 존재한다는 점에서 그래프와도 구별된다.

---

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

노드라 불리는 개별 요소들이 데이터와 다음 노드를 가리키는 포인터로 구성되어 선형적으로 연결된 구조

---

단일 연결 리스트 vs. 배열

특징	단일 연결 리스트	배열
메모리 구조	비연속적	연속적
크기	가변적	고정 또는 동적 조절
접근 시간	O(n)	O(1)
삽입 / 삭제	O(1) (탐색 후)	O(n)
메모리 오버헤드	포인터로 인해 높음	낮음
캐시 효율성	낮음	높음

‼ 결론
단일 연결 리스트는 동적 크기 조절과 삽입/삭제가 빈번한 상황에 적합.
배열은 빠른 접근과 메모리 효율성이 중요한 경우 유리.

---

구현 코드 (C++)