STL #2 List
배열과 비슷하게 선형으로 나열한다는 점에서 벡터와 비슷하다.
⭐그런데 벡터는 동적배열인 반면 리스트는 노드방식이다.⭐
크게 사용하진 않지만 트리구조를 이해하는데 도움이 되고 벡터와 비교해 많이 단골문제로 나타난다.
연결리스트.
list<int> li;
for(int i=0;i<100;i++)
li.push_back(i);
li.push_front(-1);
//동적배열 형태가 아니므로 용량의 개념인 li.capacity();가 불가능하다.
// li.capacity();
// 첫번째 데이터와 마지막 데이터를 추출할 수 있다.
int first = li.front();
int last = li.back();
// 벡터처럼 임의접근을 허용하지 않는다.
// li[3] = 10;
// 반복자 iterator
list<int>::iterator itBegin = li.begin();
list<int>::iterator itEnd = li.end();
for(list<int>::iterator it = li.begin(); it!= li.end(); it++)
cout<< *it <<endl;
// 원하는 위치에 삽입과 삭제
li.insert(itBegin,100);
li.erase(li.Begin()); // li.pop_front();와 동일하다. 처음과 끝에서 pop을 많이 쓴다.
li.remove(10); // 벡터와 구분되게 remove기능이 있다. 인자에 있는 모든 값을 삭제한다.
// (벡터는 중간 삽입과 삭제가 매우 비효율적이라 없다)동작원리
vector는 동적배열로 이루어진 container로 연속된 공간을 사용하다가 capacity가 차면 대략 1.5배를 새로운 위치에 증설하여 기존 데이터를 복사하는 방식으로 동작한다. 이어져 있어서 임의 접근이 가능하다.
list는 연결리스트로 또 단일 / 이중 / 원형 으로 구분할 수 있다.
단일 연결 리스트를 기준으로 설명해보자면 밀어 넣는 순서대로 배치된다는 특정이 있다. 그런데 연속된 공간이 아니라 분리된 공간에 있어 다음 데이터가 어디에 있는지만 알고 있다.
단일 연결 리스트 : [1] -> [2] -> [3] -> [4] -> [5] ...
각 원소의 하나하나를 노드라고 한다.
class Node
{
public:
Node* _next; // 다음 데이터의 위치 주소.
int _data; // 현재 노드의 값.
}
참고로 이중 연결 리스트 : [1] <-> [2] <-> [3] <-> [4] <-> [5] 특정 노드롤 기준으로 앞 뒤로 움직일 수 있다.
class Node2
{
public:
Node2* _next;
Node2* _prev;
TYPE _data;
}원형리스트는 이중 연결 리스트에 맨 뒤와 맨 앞을 연결하면 되는 것이다.
중간 삽입/삭제
동적배열(vector)의 경우엔 중간에 삽입하거나 삭제하려면 그 뒤의 원소들을 다 이사시켜야하므로 큰 비용이 들었다.
리스트는 연속된 공간에 없으므로 그냥 포인터만 앞 뒤로 바꿔주면 된다. 마찬가지로 처음과 끝 삽입도 쉽다.
그러나 벡터를 더 많이 사용하는데에는 이유가 있다. 임의접근을 생각해보면 i번째 데이터는 어디에 있는지 찾으려면 주소계산이 안되어 처음부터 타고 가야한다.
처음/끝 삽입/삭제
push_back()/ push_front()
push_front 가 효율적으로 동작하기 때문에 존재하는 것!
일괄적으로 데이터를 지우는 vector에는 remove기능이 없었는데 list에는 존재하는 것도 동작원리가 그렇기 때문이다.
임의 접근
실제 코드에서 메모리 접근하여 보기
실제로는 list가 이중 연결 리스트로 구현되어 있다.
itBegin을 주소창에 쳐서 들어가면 3개의 값이 있는걸 알 수 있다. 첫번째와 두번째는 컨테이너에 대한 정보이고 마지막에 있는 것이 다음 노드에 있는 정보이다. 그래서 0135daf0을 따라가면 첫번째 노드에 다한 정보를 찾을 수 있었다. 마찬가지로 마지막번째의 정보에 00000000이 있어 처음에 삽입한 0이 들어있었다.
0135dfa0에도 첫번째 값을 따라가면 다음 노드에 대한 정보가 있을 것이다. 두번째 값은 이전 노드에 대한 정보로
Node* _next;
Node* _prev;
TYPE _data;
와 같은 형태로 이루어져있다는 걸 알수 있다.
그런데 itBegin은 처음에 값을 가지고 있는게 아니라 첫번째 노드의 주소 정보를 가지고 잇었다. 또 list<int> li의 첫번째 값인 &(li.front()) 주소(0x0135dfa0)를 보면 두번째에 이전 노드의 정보 0135ddc8이 들어있다..?
이는 리스트이 헤드에 해당하는 정보이다. 헤드에 해당하는 곳으로 옮겨가면 또 이전 노드에 대한 정보를 볼 수 있는데 이는 리스트의 마지막 원소에 대한 정보이다.
즉, 리스트는 이중 연결리스트로
[1] <-> [2] <-> [3] <-> [4] <-> [5] ...
이렇게 만들어져 있으나 STL에서 이를 만들 때 가상 노드를 추가적으로 만들어
[1] <-> [2] <-> [3] <-> [4] <-> [5] ... <-> [_MyHead : end()]
_MyHead라는 이름으로 들어있는데 리스트에서 end()를 할 때 들어잇는 노드이다. 이렇게 더미를 만들어 유효범위를 파악하는데 쓰인다.
li.end(); 해서 추출하는 반복자도 이 더미 노드인 것이다.