[STL] list

list의 동작원리
단일/이중/원형 등으로 다양한 종류의 링크드리스트가 있다
데이터의 위치가 불연속적이고
하나의 노드가 

1) 데이터

2) 이전이나 다음의 데이터 위치

를 알고 있는 형태이다

 

 

C++ STL list 동작원리

C++ STL list에서는

마지막 데이터가 포함된 노드에

추가적으로 NULL이 들어가는 end() 노드가 연결되어 있다

 

주의할 점으로는

1. 마지막 데이터 노드와 end() 노드가 서로 연결돼 있다

따라서, end() 노드에서 마지막 데이터 노트로 접근 가능

마지막 데이터 노드에서 end() 노드로 접근은 가능, 수정은 불가능

 

2. begin() 노드와 end() 노드가 서로 연결돼 있다

end() 노드의 next 노드로는 begin() 노드가

begin() 노드의 previous 노드로는 end() 노드로 서로 이어져있긴 하다

하지만, begin() 노드와 end() 노드가 서로를 자유롭게 접근해서 사용하는 경우는

불가능하도록 STL에서 막아놓았다

 

list 간단 사용법 및 vector와의 차이점

push_back, push_front를 지원하고
size 또한 지원한다
하지만 capacity는 지원하지 않는다

list 특성상 여유공간이 필요 없고 데이터가 추가될 때마다

노드만 추가하는 형태이기 때문이다

 

front, back 역시 가능하다
li[2] = 3; 처럼 임의 접근은 불가능하다

그 이유는 임의 접근을 하게 되면 시간이 너무 오래 걸리며 비효율적이기 때문이다

list<int>::iterator도 당연히 사용가능하고
for문과 함께 응용이 가능하다

insert, erase, pop_front 등도 지원한다
특정 데이터를 일괄 삭제하는 remove도 지원하며,

이는 vector에서 for문을 돌면서 데이터를 삭제하는 행위를 대체한다 

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

void main(void)
{
	list<int> li;

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

	li.push_front(100);
	
	cout << li.size() << endl;

	// li.capacity();//capacity는 따로 존재하지 않음

	cout << li.front() << " " << li.back() << endl;

	li.insert(li.begin(), 1000);

	li.erase(--li.end());

	li.pop_front();

	li.remove(5);// 일괄 삭제

	
	for (list<int>::iterator it = li.begin(); it != li.end(); ++it)
	{
		cout << *it << " ";
	}
}

list의 효율
1) 중간 삽입/삭제

list의 동작원리에 따라서

결국 노드의 연결만을 제어해 주면 쉽게 중간 삽입/삭제가 가능하다 

삽입

삭제

2) 처음/끝 삽입/삭제

중간 삽입/삭제처럼 결국 처음과 끝 또한

노드의 연결만을 제어해 주면 쉽게 처음/끝 삽입/삭제가 가능하다

 

3) 임의 접근
N번째에 접근하기 위해서는

N번째만큼 노드의 Next 혹은 Previous를 계속 타고 가야 하기 때문에

효율이 매우 좋지 않다

4) 중간 삽입/삭제의 진실

중간 삽입/삭제를 한다고 하면
사실상 중간의 데이터를 찾아서 삽입/삭제를 해야 한다
따라서, "임의 접근 + 중간 삽입/삭제"가 필요하다는 것이고
이는

중간 삽입/삭제가 빠를 뿐이고

데이터를 찾는 임의접근은 느리기에

전체 과정을 효율적이라고 보기는 힘들다

 

하지만

아래의 코드처럼

중간의 데이터의 위치를 미리 iterator를 통해  
알고 있는 상황이라면

중간 삽입/삭제만 이루어지기 때문에 효율적이다

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

void main(void)
{
	list<int> li;

	list<int>::iterator itRemember;

	for (int i = 0; i < 10; ++i)
	{
		if (i == 5)
		{
			itRemember = li.insert(li.end(), i);
		}

		else
		li.push_back(i);
	}

	// 임의 접근을 for문을 돌면서 비효율적으로 찾는 법
	// list<int>::iterator it = li.begin();
	// for (int i = 0; i < 5; ++i)
	// {
	//	 ++it;
	// }
	// li.erase(it);

	// 위치를 미리 알고 있다면 쉽게 삽입 및 삭제 가능
	li.erase(itRemember);

	// Debug용
	for (list<int>::iterator it = li.begin(); it != li.end(); ++it)
	{
		cout << *it << " ";
	}
}