c++ 리스트1 List 간단 정의 성질 및 종류 list : 노드형 시퀀스 컨테이너 연결 리스트의 성질 1. K번째 원소를 확인/변경하기 위해 O(k)가 필요함 2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트 종류 1. 단일 연결 리스트(Singly Linked List) 2. 이중 연결 리스트(Doubly Linked List) 3. 원형 연결 리스트(Circular Linked List) 배열 vs 리스트 배열 리스트 k번째 원소의 접근 O(1) O(k) 임의 위치에 원소 추가 / 제거 O(N) O(1) 메모리 상의 배치 연속 불연속 추가적으로 필요한 공간 (Overhead) - O(N) c++/자료구조 간단 이론 2022. 8. 23. 이전 1 다음
