[C++] list 템플릿 클래스

1. list 클래스

- list 클래스란 무엇인가? list 클래스는 표준 시퀀스 컨테이너 중 하나이며 선형적 구조를 띠며, 노드 기반 컨테이너이다.

- 동적으로 list 클래스를 통해 데이터를 추가할 수 있으며, 그 데이터를 저장할 때 프로그래머는 메모리를 신경쓰지 않아도 된다.

- 그럼 vector와 차이가 무엇일까? vector는 데이터를 연속적인 메모리공간에 저장하는 구조로 중간에 데이터를 추가하거나 제거한다는 상황에서 데이터를 다루는 방법이 list와 차이를 보인다.

 

- vector는 중간에 있는 요소를 추가한다고 가정하면, 추가하고자 하는 요소의 주소값에 공간을 확보하기 위해 그 뒤에 있는 인덱스 요소값들을 모조리 인덱스를 하나 추가한 주소값으로 옮겨버린다. 그리고 공간이 확보된 요소의 주소값에 추가하고자 하는 값을 저장하는 것이다.

- 삭제라고 크게 다르지 않다. 삭제하고자 하는 요소가 중간에 있다면 그 요소를 제거하고 그 뒤에 있는 인덱스 값들을 땡겨서 빈 요소를 채우는 방식을 쓴다.

 

- list는 노드 기반 컨테이너로, 연속된 메모리 공간이 아닌 데이터 하나를 하나의 메모리에 저장하고 그 다음 노드의 주소값을 저장하고 있는 방식이다.

- 그래서 list에서 데이터의 추가와 제거는 곧 노드의 추가와 제거를 이르는 말인데, 노드의 추가는 추가하고자 하는 요소의 이전 노드가 저장할 주소값에 추가할 노드의 주소값을 저장하고, 추가할 노드가 저장할 주소값에 다음 노드의 주소값을 저장하면 된다.

- 제거 또한 간단하다. 노드를 제거하고, 이전 노드가 저장한 주소값을 제거한 노드의 다음 노드의 주소값을 저장하면 된다.

 

- 이처럼 배열 기반, 노드 기반에서 다른 점을 보인다. 데이터의 추가, 삭제가 빈번하게 일어나는 데이터를 다뤄야 한다면 list를 추천한다고 한다.

- 반면 vector는 list가 못하는 빠른 데이터 참조가 가능하다. 원소 탐색 시 [] 연산자가 오버로딩되어 있어 원하는 원소에 바로 접근 가능하지만, list는 반복자를 이용한 순차 탐색만이 가능하다.

 

2. list의 또다른 특징

- 원소를 탐색할 때, [] 연산자는 불가능하다.

- 양방향 반복자(++, --)를 이용해 탐색을 한다.

- push_front(), push_back(), pop_front(), pop_back() 멤버 함수를 이용해서 list 양 끝에 삽입과 삭제가 가능하다.

- insert(), erase() 멤버 함수로 노드 중간 삽입 삭제도 가능하다.

 

3. list의 구조

- 이는 단방향 리스트를 예로 가지고 왔다.

- list는 다수의 node라는 데이터 구조로 이루어져있다.

- node는 값을 저장하는 data와 그 다음 노드의 주소값을 저장할 next로 이루어져있다.(여기서 이름은 임의로 지정한 것이다.)

- node는 그 다음 노드의 주소를 가리켜서 그 다음 노드를 접근할 수 있다.

- 그렇게 연속적으로 접근하면 가장 마지막 노드까지 접근할 수 있을 것이다.

- 이런 접근으로 데이터를 저장하고 다루는 것이 list이다.

- head는 가장 앞에 있는 노드이며 특정한 data를 지니지 않고 가장 앞 노드라는 의미를 지니기 위해 쓰는 노드이다.

- head의 다음 노드는 실질적 데이터를 저장할 첫 요소가 될 것이다.

- tail은 가장 마지막에 있는 노드이며 특정한 data를 지니지 않고 가장 마지막 노드라른 의미를 지니기 위해 쓰는 노드이다.

- tail을 이용해 이 tail 노드를 다음 주소값으로 가리키는 노드는 실질적 데이터를 지니는 마지막 노드임을 알 수 있다.

 

4. list의 선언

- list를 사용하기 위해서는 <list> 헤더파일을 포함해야한다.

#include<list>
list lt; // 비어있는 list를 생성
list lt(10); // 0으로 값 초기화된 원소 10개 가진 list 생성
list lt(3, 2); // 2 값으로 초기화된 원소 3개를 가진 list 생성
list lt2(lt1); // list lt1을 lt2로 복사

5. list의 멤버함수

- lt는 list 컨테이너로 생성된 객체를 의미한다.

- 매개변수는 그 자료형에 맞는 임의의 수로 대신 넣었다.

멤버 함수	설명
lt.assign(3, 4)	4로 초기화된 3개의 원소를 할당
lt.front()	맨 앞의 원소를 반환, 참조
lt.back()	맨 뒤의 원소를 반환, 참조
lt.begin()	맨 앞의 원소를 가리키는 iterator를 반환
lt.end()	맨 마지막의 다음 원소를 가리키는 iterator를 반환
lt,rbegin()	뒤에서부터 원소를 순차적으로 접근, begin() 사용 동일
lt.rend()	뒤에서부터 원소를 순차적으로 접근, end() 사용 동일
lt.push_back(k)	뒤쪽으로 원소 k를 삽입
lt.push_front(k)	앞쪽으로 원소 k를 삽입
lt.pop_back()	맨 마지막 원소를 제거
lt.pop_front()	맨 첫번째 원소를 제거
lt.insert(iter, k)	iter가 가리키는 위치에 원소 k를 삽입 삽입한 원소를 가리키는 iterator 반환
lt.erase(iter)	iterator가 가리키는 원소를 삭제 삭제한 원소의 다음 원소를 가리키는 iterator 반환
lt.size()	원소의 개수를 반환
lt.remove(k)	k와 같은 원소를 모두 제거
lt.remove_if(Predicate)	단항 조건자(함수) Predicate에 해당하는 원소를 모두 제거
lt.reverse()	원소들의 순차열을 뒤집는다.
lt.sort()	모든 원소를 오름차순 정렬
lt2.swap(lt1)	lt2와 lt1을 바꾼다. vector 글 참고
lt2.splice(iter2, lt1)	lt2에서 iter2가 가리키는 곳에 lt1의 모든 원소를 잘라 붙인다.
lt2.splice(iter2, lt1, iter1)	lt2의 itr2가 가리키는 곳에서 lt1의 iter1이 가리키는 원소를 잘라 붙인다.
lt2.splice(iter2, lit1, iter1_1, iter1_2)	lt2의 iter2가 가리키는 곳에 lt1의 iter1_1~iter1_2까지의 원소를 잘라 붙인다
lt.unique()	인접한 양 옆의 원소가 같으면 그 하나만 빼고 삭제
lt2.merge(lt1)	lt1을 lt2 내부로 합병 정렬, 오름차순이 기본

- 함수에 대한 설명은 https://blockdmask.tistory.com/76 이 곳의 설명을 가져왔다.

- 함수에 대한 예제는 위의 링크를 타고 들어가서 보도록 하자.

 

출처 : 

https://blockdmask.tistory.com/76

[C++] list container 정리 및 사용법

https://ssinyoung.tistory.com/46

다시 정리하는 C++ STL 자료구조 list