STL - list
list (연결 리스트)
기본적으로 list는 vector와 유사하지만 기본적으로 차이점이 존재한다.
vector는 동적 배열 방식을 사용하고 list는 노드 방식을 사용한다.
list는 동적 배열이 아니기 때문에 capacity를 사용하지 않는다.
list는 vector와 다르게 push_front를 지원한다.
list는 vector처럼 배열의 특정 인덱스에 접근하여 값을 수정하거나 가져올 수 없다.
list는 front 함수와 back 함수를 사용해 처음 데이터와 마지막 데이터를 가져올 수 있다.
vector와 마찬가지로 begin과 end 함수를 사용할 수 있다.
등등~
list 또한 다음과 같은 부분을 이해하는 것이 중요하다.
- list 동작 원리
- 중간 삽입/삭제
- 처음, 끝 삽입/삭제
- 임의 접근
기본적으로 vector와 그게 다르지 않게 사용할 수 있다.
다른 점이 있다면 중간 삽입/삭제 등이 vector보다 수월하다는 것이다.
라인 24~29번까지 여러 기능들을 지원하고 vector에서는 지원하지 않는 기능들까지 지원하는 걸
알 수 있다.
list 원리 이해하기
vector는 데이터를 연속된 공간에 배치해야 하는 강제사항이 존재한다.
하지만 list는 그런 강제사항이 없다. 그래서 데이터들을 연속되지 않는 공간에 배치할 수 있다.
그러면 list 같은 경우 다음 데이터의 위치를 어떻게 알고 이동하는 것일까?
기본적으로 list는 포인터를 이용해서 다음 데이터의 위치 주소를 가지고 있다.
예를 들어 첫 번째 데이터는 본인의 데이터와 두 번째 데이터의 위치 주소를 가지고 있다는 소리이다.
list에서는 이러한 데이터와 주소를 저장하는 칸 단위를 '노드'라고 부른다.
한쪽 방향으로만 노드에서 노드로 이동할 수 있다면 단일 list
노드끼리 양방향으로 이동할 수 있다면 이중 list
노드끼리 양방향 이동뿐만 아니라 첫 번째 노드와 마지막 노드끼리도 이동할 수 있다면 원형 list
라고 한다. (STL - list는 이중 list로 구현되어 있다.)
처음, 중간, 끝 삽입/삭제
vector에서의 중간 삽입/삭제는 연속된 저장 공간에 데이터를 할당해야 하는 강제성 때문에
많은 양의 데이터를 한 칸씩 밀어내거나 당겨야 하는 매우 비효율적인 상황이 발생한다고 했다.
하지만 list에서는 노드라는 개념을 사용하기 때문에 데이터가 연속된 저장 공간에 할당되어 있지 않고
이전과 이후 데이터의 위치 주소를 가지고 해당 데이터로 이동하게 된다.
그러므로 list에서 삽입/삭제는 vector보다 매우 효율적으로 작동하게 되고 실제로 데이터 배열 중간에
새로운 데이터를 삽입한다고 했을 때 이전 데이터의 주소와 이후 데이터의 주소를 맞춰주기만 하면 된다.
하지만 이러한 노드 방식 또한 단점이 존재한다. 바로 임의 접근이다.
vector의 경우 연속된 저장 공간에 데이터가 할당되어 있기 때문에 특정 데이터에 바로 접근할 수 있지만
list의 경우 특정 데이터에 접근하려면 별다른 효율적인 방법이 없기 때문에 처음부터 주소를 타고 이동해가면서
찾는 방법 밖에 없다.
위와 같은 특징 때문에 list는 여러 칸을 연속해서 이동하는 기능들은 막혀있다.
한 가지 중요한 개념이 있다.
list는 중간 삽입/삭제가 빠르지만 임의 접근은 느리다.
그렇다면 중간에 특정 데이터를 삭제하려고 했을 때 결국엔 임의 접근을 사용해서 그 데이터에
접근해야 하기 때문에 전체적으로 보면 느린 것이 아닐까?
맞는 말이다.
특정 위치에 있는 데이터를 중간에 삽입/삭제하는 것은 임의 접근을 사용해야 해서 비효율적이다.
그러면 어째서 중간 삽입/삭제는 빠르다고 하는 것일까
그 이유는 데이터를 push_back 할 때 특정 데이터의 정보를 iterator에 보관할 수 있고
이렇게 iterator에 보관한 데이터 정보를 이용해서 나중에 특정 데이터에 빠르게 접근하여
중간 삽입/삭제를 할 수 있다. 이런 방법을 이용하기 때문에 중간 삽입/삭제가 빠르다는 것이지
아무런 정보도 없이 임의 접근을 해서 중간 삽입/삭제를 하는 것은 비효율적이다.