[자료구조] C++ list자료구조 정리/list 함수/list예시

C++ 리스트(list)

 

C++의 List는 양방향 Container 자료구조이다. 리스트는 비슷한 정보를 논리적으로 연결시켜놓은 구조이다. 논리적으로 연결되어 있다는 말은, 물리적이지 않다는 것, 즉 내부의 자료들이 물리적으로 인접하지 않는다는 것이다.

 

물리적으로 연속된 자료구조의 예로 메모리 공간에 순차적으로 정렬하는 배열이 있다.

 

반면 List는 인접한 값들을 주소의 형태로 저장하여 가지고 있다. 즉, 서로 다른 위치에 존재하는 원소들이 pointer정보를 이용해 논리적으로 연결되어 있다.

 

리스트 선언, 생성

헤더: #include<list>

 

list<T> listName;

list<T> listName(개수); //‘개수’의 크기를 가지는 리스트 생성, int형의 디폴트 값은 0, char은 ‘ ’ ...etc

list<T> listName = {1, 2, 3, 4, 5}//1, 2, 3, 4, 5 값을 저장한 리스트 생성

list<T> listName(개수, 값); //1을 5개 채운 리스트 생성

 

*forward_list

속도를 위해 리스트에서 필요한 기능만을 빼고 남은 것이다.

std::list가 양방향이라고 한다면, forward_list는 단방향이다.

또한 성능 유지를 위해 임의의 위치에 대한 접근을 허용하지 않으며, 전체 리스트의 크기를 바로 알 수 없다.

front()함수는 지원하나 back()함수는 지원하지 않는다.

size()함수, erase()함수 등을 지원하지 않는다.

 

리스트의 각종 함수들

 

리스트 삽입 삭제 함수

 

list.assign(개수, 값)

리스트에 값을 개수만큼 할당한다.

 

list.push_back(a)

리스트 맨 뒤에 원소a를 추가한다.

 

list.push_front(a)

리스트 맨 앞에 원소a를 추가한다.

 

list.pop_back()

리스트 제일 뒤의 원소를 삭제한다.

 

list.pop_front()

리스트 제일 앞의 원소를 삭제한다.

 

list.insert(iterator, element)

iterator가 가르키는 부분에 원소를 추가한다. 기존의 원소는 뒤로 한 칸씩 밀리게 된다.

리턴 값 : 삽입한 원소의 위치

 

list.erase(iterator)

리스트에서 이터레이터에 해당하는 값을 삭제한다. 리스트에서 이터레이터를 사용할 경우 리턴 값을 다시 이터레이터로 받아주어야한다. (이터레이터가 있던 주소가 삭제되었기 때문에 다음 주소를 찾기 위함)

리턴 값 : 삭제한 원소 다음 원소를 가르키는 이터레이터

 

list.clear()

모든 원소를 제거한다.

 

 

크기 관련

 

list.size()

리스트의 크기를 반환한다.

 

list.empty()

리스트가 비어있으면 true, 그렇지 않으면 false반환

 

iterator(반복자) 관련

 

list.begin()

시작 주소값을 가르키는 beginning iterator를 반환한다.

*list::iterator는 ++, -- 가 아닌 +3, -3같은 연산자를 지원하지 않는다(vector 등의 iterator는 가능)

*iterator와 역참조 연산조 연산자를 이용해 값 삽입이 가능하다.

 

 

list.end()

리스트의 마지막 주소값을 가르키는 end ierator를 반환한다.

 

리스트 사용 예시

 

반복자 이동(입력 받은 값만큼 이터레이터 이동)

#include <iostream>
#include <list>
#include <algorithm>
#include <bits/stdc++.h>
 
using namespace std;
 
//iterator 이동
int main(){
    list<int> li(10);
    iota( begin(li), end(li), 1) ;
    auto itr = li.begin();
    int m;
    int i;
 
    while(1){
        cin>>m;
        if(m > 0){
            for( i = 0; i < m;i++){//정방향 이동
                itr++;
                if(itr == li.end()){ //마지막에 다다르면 첫 요소로 이동(li.end()의 iterator는 마지막 요소가 아닌 그 뒤를 가르킨다.
                    itr = li.begin();
                }
            }
        }
        else{
            for(i = 0; i < -m;i++){//역방향 이동
                if(itr==li.begin()){//li.begin()의 iterator는 첫 요소를 가르킨다.
                    itr = li.end();
                    itr--;//li.end()는 마지막 요소를 가르키는 것이 아니기 때문에 마지막 요소를 가르키기 위해 삽입
                }
                else{
                    itr--;//이터레이터 앞으로 이동
                }
            }
        }
 
        cout<<"*itr = "<<*itr<<endl;
    }
 
 
return 0;
 
}
 

결과값

 

 

Insert함수 이용 요소 삽입

list insert 요소 삽입

출력결과

 

조건 통과시 이전 요소의 값 삭제(iterator와 erase)

#include <iostream>
#include <list>
 
using namespace std;
 
int main(void){
    list<int> list1 = {1, 2, 3, 4, 5};
    cout<<"before erase"<<endl;
    for(auto l:list1){
        cout<<l<<" ";
    }
    cout<<endl;
    cout<<"after erase"<<endl;
    for(auto itr = list1.begin(); itr!=list1.end(); itr++){
        if(*itr == 3){
            itr = list1.erase(--itr);//erase 2
            cout<<"*(returned itr) : "<<*itr<<endl;
        }
    }
    cout<<"after erase"<<endl;
    for(auto l:list1){
        cout<<l<<" ";
    }
 
 
 
return 0;
}