List

오늘은 지난 번 Deque 정리에 이어서 List 정리를 해본다.

LIST 란?

리스트는 벡터와 디큐와 마찬가지로 순차 선형 콘테이너이다. 그래서 외부에서 볼 때에는 벡터와 완전히 동일한 듯 보이지만, 구조 자체부터 크게 다르다.

벡터는 순차 배열 형태였다면, 리스트는 이중 연결 리스트로 구현된다. 다음 그림과 같이 말이다.

위와 같은 이중 연결 리스트로 구현되어 있기 때문에 벡터에서의 순회 방법에서 아주 조금의 차이가 있다. begin() 부터 end() 까지 주소 값 비교를 통한 순회가 의미가 없기 때문이다. 무조건 노드의 링크를 타고 가는 방식의 포인터 연산으로 접근해야한다. ( 이는 연산자들이 오버로딩되어 자동으로 포인터 연산 되도록 구현되어 있음.)

또한 링크드 리스트로 구현되어 있기 때문에 인덱스가 없다. 그렇단 소리는 임의 접근이 불가능하다는 소리이고, 탐색을 할 때는 모든 노드를 링크를 타고 순회해야한다.

다만, 삽입이나 삭제를 할 때, 벡터에서는 요소들의 인덱스 재 조정 그리고 추가 메모리 공간 확장 및 복사/확장이 필요하지만 리스트에서는 링크를 변경하면 되므로 삽입/삭제 시에는 속도가 빠르다는 장점이 있다.

결국, 중간에서의 삽입 및 삭제가 빈번한 경우 사용하면 적합할 것 같다.

s

#include <iostream>
#include <list>
 
using namespace std;
 
void print_list(list<int>& l)
{
    list<int>::iterator list_it;
    for (list_it = l.begin(); list_it != l.end(); list_it++) // 링크드리스트이기 때문에 <, > 연산이 의미가 없다.
        cout << "list iterator value : " << *list_it << endl;
    return;
}
bool cond(int n) // 기본 조건에 의한 삭제를 위한 함수.
{
    return n > 901;
}
bool desc(int a, int b) // sort의 내림차순을 위함.
{
    return a > b;
}
 
int main(void)
{
    list<int> my_list;
    list<int> new_list;
 
    cout << "push_front, push_back 함수 호출 --- --- ---" << endl;
    my_list.push_back(100);
    my_list.push_back(200);
    my_list.push_front(900);
    print_list(my_list); // 900 100 200
    
    cout << "insert 함수 호출 --- --- ---" << endl;
    my_list.insert(--(my_list.end()), 999); 
    print_list(my_list); // 900 100 999 200
 
    cout << "remove & remove_if 함수 호출 --- --- ---" << endl;
    my_list.remove_if(cond); // 901 제거
    my_list.remove(100); // 100 제거
    print_list(my_list); // 900 200
 
    cout << "reverse 함수 호출 --- --- ---" << endl; // 원소들을 뒤집어서 나열
    my_list.reverse();
    print_list(my_list); // 200 900
 
    cout << "sort 함수 호출 오름차순 --- --- ---" << endl;
    my_list.sort();
    print_list(my_list); // 200 900
 
    cout << "sort 함수 호출 내림차순 --- --- ---" << endl; // 식을 함수 형태로 주어 내림차순 구현
    my_list.sort(desc);
    print_list(my_list); // 200 900
 
    cout << "unique 함수 호출 --- --- --- " << endl; // 인접한 데이터 중에 중복되는 요소들을 제거한다.(연속적으로 나오는 중복을 허용 X)
    new_list.insert(new_list.begin(), 55);
    new_list.insert(new_list.begin(), 33);
    new_list.insert(new_list.begin(), 55);
    new_list.insert(new_list.begin(), 55);
    new_list.unique();
    print_list(new_list); // 실행결과 : 55 33 55
 
    cout << "merge 함수 호출 --- --- --- " << endl;
    new_list.sort();
    my_list.sort(); // 각각의 리스트들은 꼭 정렬되어 있어야 한다.
 
    new_list.merge(my_list); // 복사(copy)하는 것이 아니라 요소의 이동(move)이다.
    print_list(new_list); // 실행결과 : 33 55 55 200 900
    print_list(my_list); // 실행결과 : 비어 있음 -> 이동했기 때문에
 
    cout << "splice 함수 호출 --- --- --- " << endl;
    my_list.push_front(300);
    my_list.push_front(100);
    my_list.splice(my_list.begin(), new_list); // 복사(copy)하는 것이 아니라 요소의 이동(move)이다.
    print_list(new_list); // 실행결과 : 비어 있음 -> 이동했기 때문에
    print_list(my_list); // 실행결과 :  33 55 55 200 900 100 300
 
    return 0;
}

s간단한 설명을 붙이자면,

34번 라인처럼 insert시, 임의 접근이 불가능하므로 포인터 연산(오버로딩된)을 통해 위치를 명시한다.
그리고 remove_if 함수를 통해 조건부 삭제가 가능한데, 이 때 조건은 13번 라인의 bool 반환 타입의 함수 형태로 기입한다. 함수의 이름을 적으면 된다. 

50번 라인에서 sort 함수를 통해 기본적인 오름차순 정렬이 가능한데, 내림차순이나 다른 형태의 정렬을 위해선 remove_if 처럼 조건을 전달해야한다. 17번 라인의 함수 이름을 전달하면 된다.

59번 라인의 unique 함수는 인접한 데이터 중에 중복 요소가 있으면 중복을 제거한다. 내가 가만히 보니, 11/11/22/22 는 11/22 로 중복을 제거하지만 11/22/11/22인 경우는 중복이 제거가 되지 않는다... 참으로 이상하다

62번 라인과 70번 라인의 merge와 splice는 병합의 기능을 하는데, 참으로 불편한게 이 두 함수를 사용하기 위해서는 병합할 두 요소들이 모두 일정한 방법으로 정렬이 되어 있어야 한다는 점이다. 참으로 딱하구나... 또한 병합할 때에는 요소들 간의 복사가 이루어지는게 아니라 잘라내기&붙혀넣기 즉, 요소의 이동이 이루어지기 때문에 병합하는 쪽은 merge() 및 splice() 함수 호출 후에는 텅 비어있다.. 그런데 이것은 뭐 당연하다고 생각된다. 링크를 바꾸는 것이기 때문에!

이상 list^^