- LinkedList는 Node는 데이터 값과 다음 Node의 addrss를 저장함.
- Linked List는 물리적인 메모리상에서 비연속적으로 저장됨
- 메모리상에서 불연속적으로 데이터가 저장됨
- 다음 node의 address를 통해 불연속적인 데이터를 연결하여 논리적 연속성을 보장함
- 데이터가 추가되는 시점에 메모리를 할당함(메모리를 효율적으로 사용함(
- tree나 graph등 다른 자료구조 구현할 때 자주 쓰이는 기본 자료구조임
- 물리적으로 옮길 필요 없이 next address가 가리키는 주소만 변경하면 되기 때문에, 데이터 삽입 / 삭제는 O(1)의 시간 복잡도가 걸림
- Linked List는 조회시 O(n)이 걸림. 맨 처음 Node를 보고 그 다음 address 정보를 순차적으로 조회해야하기 때문.
728x90
반응형
'Algorithm > 자료 구조 및 개념 정리' 카테고리의 다른 글
| 이진트리 순회 (0) | 2022.09.06 |
|---|---|
| Array와 LinkedList의 차이 (0) | 2022.07.10 |
| 문자열 검색 (0) | 2022.05.01 |
| 집합 (0) | 2022.04.17 |
| 검색 알고리즘 (0) | 2022.03.15 |
