STL - 9 (연결리스트-1)

• STL은 C++ 템플릿을 사용해 만든 표준 라이브러리이다.
• STL중에서 가장 많이 사용되는 라이브러리는 컨테이너 라이브러리이다. 컨테이너는 말 그대로 무엇인가를 담는 것이다. 컨테이너는 int, float 등의 자료형이나 구조체, 클래스 같은 사용자 정의형을 담는다. (list, vector, deque, map, set)

1. list 자료구조

• list는 자료구조 중 '연결리스트'를 템플릿으로 구현한 것이다. 그래서 list를 알려면 '연결리스트'라는 자료구조의 이해가 꼭 필요하다!
  

2. 연결 리스트의 특징

• 고정 길이인 '배열'에 비해 길이가 가변적이다.
  '배열'은 처음에 설정한 크기 이외에는 더 이상 데이터를 담을 수 없지만, '연결 리스트'는 동적으로 크기를 변경할 수 있다!
• 중간에 데이터 삽입, 삭제가 용이하다.
  데이터를 중간 삽입할 때 '배열'은 넣으려는 곳 뒤의 데이터들을 모두 뒤로 이동시켜야 한다. (연결리스트에 비해 상대적으로 비용낭비)
• '연결리스트'는 '배열'에 비해서 크기가 가변적이고, 중간에 데이터 삽입, 삭제에 용이하다는 장점이 있다. 그러나 단점으로는 배열에 비해서 데이터의 삽입, 삭제를 구현하기 어렵고 내부 절차가 복잡하다. '배열'은 랜덤하게 접근(Read)할 수 있지만, '연결리스트'는 랜덤하게 접근할 수 없다.

특징을 잘 파악한 후 알맞은 곳에 사용하자!