Algorithm Workbook
[Data Structure] 단일 연결 리스트, Singly Linked-List
likepint
2025. 3. 22. 23:30
연결 리스트 (Linked-List)
추상적 자료형인 리스트를 구현한 자료구조
데이터를 저장 할 때 하나의 데이터와 다음 데이터의 위치를 함께 저장하여, 논리적으로 연결하는 방식으로 자료를 저장
❓ 리스트란
순열(Sequence)라고도 불리며, 순서를 가지고 일렬로 나열한 원소들의 모임으로 정의
순서가 있다는 점에서 집합과는 구별되며,
갈림길 없이 일렬로 나열되어 처음과 끝이 하나만 존재한다는 점에서 그래프와도 구별된다.
단일 연결 리스트 (Singly Linked-List)
노드라 불리는 개별 요소들이 데이터와 다음 노드를 가리키는 포인터로 구성되어 선형적으로 연결된 구조
단일 연결 리스트 vs. 배열
| 특징 | 단일 연결 리스트 | 배열 |
| 메모리 구조 | 비연속적 | 연속적 |
| 크기 | 가변적 | 고정 또는 동적 조절 |
| 접근 시간 | O(n) | O(1) |
| 삽입 / 삭제 | O(1) (탐색 후) | O(n) |
| 메모리 오버헤드 | 포인터로 인해 높음 | 낮음 |
| 캐시 효율성 | 낮음 | 높음 |
‼ 결론
단일 연결 리스트는 동적 크기 조절과 삽입/삭제가 빈번한 상황에 적합.
배열은 빠른 접근과 메모리 효율성이 중요한 경우 유리.