C++ STL 프로그래밍(연결 리스트)

4. 연결 리스트
- STL은 C++클래스 템플릿을 사용해 만든 표준 라이브러리
- STL컨테이너는 list, vector, deque, map, set

4.1 list의 자료구조
- '연결 리스트'를 템플릿으로 구현한 것

4.2 연결 리스트의 특징
1) 배열에 비해 길이가 가변적 : 동적으로 크기 변경
2) 중간 데이터 삽입, 삭제가 용이
3) 랜덤하게 접근할 수 없다.

4.3 STL list 를 사용하면 좋은 점
4.3.2 list를 사용해야 하는 경우
1) 저장할 데이터 개수가 가변적일 때
2) 중간 데이터 삽입 삭제가 빈번할 때
3) 데이터 개수가 많고, 검색을 자주하면 다른 컨테이너 라이브러리 쓸 것
- list보다 map, set, hash_map이 검색 빠르다
4) 데이터를 랜덤하게 접근하는 경우가 많지 않을 때
- list는 순차 접근만 가능하기 때문에 iterator 를 통해 접근해야 한다.
- 아이템 정보는 빈번하게 랜덤접근하므로 list 보다 배열이 좋다.

4.4 list 사용방법
- 헤더 파일 포함 #include <list>
- 선언 : list<자료형> 변수명;
- 동적할당 : list<자료형>* 변수이름 = new list<자료형>;

4.4.2 반복자(iterator)
- 포인터의 일반화된 개념
- 포인터와 비슷하게 ++, --로 이동하고 대입, 비교 가능
- STL의 반복자 선언 : 컨테이너<자료형>::iterator 변수이름;
- STL의 역반복자 선언 : 컨테이너<자료형>::reverse_iterator 변수이름;