링크드리스트
- 고정되지 않은 공간을 가지고 있고, 각각의 원소들이 연속되지 않는 메모리 공간을 할당
- 각 노드가 데이터와 포인터를 가지고 있으면서 노드들이 한 줄로 쭉 연결되어 있는 방식
- 유동적으로 연결고리를 떼었다가 붙였다가 할 수 있음
- 양방향으로도 연결 가능
- 노드 : 각각의 원소 값 저장
- 포인터 : 현재 노드가 가리키는 다음 노드
- C++의 List와 유사
링크드리스트와 배열 비교
| 배열 | 링크드리스트 | |
| 조회 | index로 직접 접근, 시간 복잡도 : O(1) | 모든 요소 조회, 시간 복잡도 : O(n) |
| 중간 삽입 및 삭제 | 모든 요소 이동, 시간 복잡도 : O(n) | 시간 복잡도 : O(1) 또는 O(n) |
| 공간 | 크기가 고정 | 유동적으로 변함 |
| 메모리 공간 | 연속적 | 비연속적 |
| 장점 | 빠른 조회 | 중간 삽입 및 삭제 효율적 |
| 단점 | 중간 삽입 및 삭제 비효율적 | 조회 느림 |
