1. 구조
- 연결 리스트
- 연결된 공간에 데이터를 나열하는게 배열이고 Linked List는 떨어진 곳에 있는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다.
- 파이썬에서는 List 타입이 Linked List의 기능을 모두 지원한다.
- 기본 구조와 용어는
@ Node: 데이터 저장 단위(데이터값, 포인터)로 구성이된다.
@ pointer: 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고있는 공간이다.
2. 장단점
- 장점: 데이터 공간을 미리 할당하지 않아도된다.(배열은 미리 데이터 공간을 할당해야한다.)
- 단점: 연결을 위한 별도 데이터 공간이 필요해서 저장공간 효율이 낮다. 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다. 중간 데이터 삭제하면 앞뒤 데이터 연결을 재구성해야하는 부가적인 작업이 필요하다.
'IT > 알고리즘, 코딩테스트' 카테고리의 다른 글
| 알고리즘 기법 정리 (0) | 2024.01.31 |
|---|---|
| 코딩테스트에서 문자열을 한번에 입력을 하는 방법 (백준 11382) (1) | 2023.12.26 |
| 자료구조 개요 (0) | 2023.08.17 |
| (JavaScript) 코테를 위한 기본적으로 알아야할 문법 (0) | 2023.08.03 |
| 코딩테스트 개요 (0) | 2023.08.03 |