list

 

list(연결 리스트)

• list의 동작원리
• 중간 삽입/삭제
• 처음/끝 삽입 ,삭제
• 임의 접근

 

#include <list> 작성해줘야함

push_front 지원

capacity 는 없음

 

front 와 back 기능으로 처음과 끝 데이터 추출 가능

 

 

#include <iostream>
#include <vector>
#include <list>
using namespace std;


int main()
{
	list<int> li;

    for (int i = 0; i < 100; i++)
    {
    	li.push_back(i);
    }

    li.push_front(10);
    int size = li.size();
    //li.capacit()//없음

    int first = li.front();
    int last = li.back();

    //li[3] = 10; // 불가

    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();//첫 데이터 삭제
    li.pop_back();//맨 뒷 데이터 삭제
    li.remove(10); // 해당 값이랑 같은 데이터 삭제

    return 0;

}

 

동작 원리:

단일 / 이중 / 원형

 

단일

class Node

{

 

 public:

Node* _next;

int _data;

 

};

 

이중

class Node

{

 

public:

Node* _next;

Node* _prev;

int _data;

 

};

• 중간 삽입/삭제 (Good / Good)
• 처음/끝 삽입 ,삭제 (Good / Good)
• 임의 접근 (Bad) / 노드를 타고타고 데이터가 있기때문에 1번째 부터 접근해야함

 

 

시작 -> …..끝 -> Myhead -> 시작 이런식으로 노드가 연결되어있음

 

 

만약 특정 50번째 값을 지운다고 한다면

 

//50번 인덱스 삭제해보자,

list<int>::iterator it = li.begin();
for (int i = 0; i < 50; i++)
++it;

li.erase(it);

 

이렇게 할수 있다. 하지만 50번째까지 타고가야하고

 

list<int> li;
list<int>::iterator itRemember;


for (int i = 0; i < 100; i++)
{
	if (i == 50)
	{
		itRemember = li.insert(li.end(), i);
	}
    else
    {
    	li.push_back(i);
    }
}

li.erase(itRemember);

 

 

이렇게 선언할때 50번째 값을 기억해 두었다가 삭제하는것이 효율적