[C++ STL] list

double linked list 로 구현되어 있어 앞 뒤 모두 추가 삭제가 가능하다

list<int> l;
l.push_back(3);
l.push_front(5);

 

노드기반 컨테이너이므로 vector에 비해 임의의 위치에 데이터 추가,삭제가 빠르다

 

하지만 Random Access가 불가능(iterator 로만 참조가능하다)

 

데이터 추가 삭제가 빈번하다면 list를 사용하면 된다

 

---

[c++ list]

 

c++ 의 list는 노드기반의 Double-Linked List 로 구현되어있다.

 

따라서 한 개의 노드에서 양방향으로 이동이 가능함.

iterator++ ,  iterator-- 가 가능함

 

Linked List로 구성되어 있기에 삽입과 삭제의 시간복잡도가 O(1)임

 

일반 Linked List 가 필요하면 forward_list 를 쓰면 된다

( 그냥 List 보다 성능이 약간 좋다 )

 

---

[ List 특징 ]

 

1. Sequence Container 

2. Node-Based Container

3. Double-Linked List

4. remove, sort, merge, splice 함수 존재

5. 원소 탐색 시 Random Access로 접근 불가!

6. 어느 위치에서든 삽입과 삭제가 매우 효율적 ( O(1) )

 

vector와의 차이점

1. push_front 와 pop_front 와 같이 vector에선 할 수 없었던 앞쪽에 추가하는 것을 O(1) 시간복잡도로 할 수 있음

2.  하지만 Random Access로 접근 불가능

 

---

[ vector vs list ]

 

동적배열인 vector와 연결리스트 list 의 가장 큰 차이점은 다음과 같다

 

1. 삽입과 삭제

 

vector = O(N) 다 한칸씩 밀어줘야하므로

 

list = O(1) 노드기반이므로

 

2. 임의의 원소에 접근하는 시간 (Random Access 의 유무)

 

vector = O(1)

삽입과 삭제를 할 일이 없거나, 배열의 끝에서만 하면 될 경우에는

vector를 쓰는게 맞음.

임의의 원소에 빠르게 접근할 수 있을 뿐만 아니라

원소들이 메모리에 연속해 배치되어 있기때문에 CPU 캐시 효율도 더 높여주기 때문이다

 

list = O(N)

하지만 만약 임의의 원소를 접근하는 것이 아니라

모든 원소들을 순회하며 삽입과 삭제를 빈번하게 해야되는 경우

이때는 list가 좋은 선택이다.

 

---

[list functions]

// 빈 list 생성
list<int> lst1;

// 0으로 초기화된 원소 5개 list
list<int> lst2(5);

// 3으로 초기화된 원소 10개 list
list<int> lst3(10, 3);

 

push_front(x)  O(1)

pop_front()  O(1)

push_back(x)  O(1)

pop_back()  O(1)

 

front() 맨 앞 원소 return

back() 맨 뒤 원소 return

assign(n,val) 모든 원소 삭제 후, val값으로 n개 할당 ( 초기화 )

 

insert(iter,x) O(1) iter가 가리키는 위치에 x 삽입

erase(iter) O(1) iter가 가리키는 원소 삭제

remove(val) O(N) val값 원소 모두 삭제

 

empty() 

size()

 

sort() 리스트 정렬(default 오름차순)

sort(greater<>()) 리스트 정렬(내림차순)

unique() 중복원소 제거한 리스트 만들어줌

 

reverse() 리스트 뒤집기

splice(iterator,list) 해당 list의 iterator에 인자로 들어온 list를 이어 붙이기

merge(list) 인자로 들어온 list와 합병 두번째 인자로 정렬기준 받을 수 도 있음. 

 

 

list<int>::iterator it;

for (it=l.begin(); it!=l.end(); it++) {
	cout << *it<<" ";
}

 

 

list<int> l;
	
	l.push_back(10);
	l.push_back(20);
	l.push_back(30);
	l.push_back(40);
	l.push_back(50);
	l.push_back(60);
	l.push_back(70);
	l.push_back(80);

	auto it = l.begin();
	while (it != l.end()) {
		cout << *it << " ";
		it = next(it);
	}

	cout << "\n";

	auto front = l.begin();
	auto rear = prev(l.end());
	cout << *rear << "\n";

	cout << distance(front, rear) << "\n";
	cout << distance(front, rear) / 2 << "\n";
	auto mid = next(front, distance(front, rear) / 2);
	cout << *next(front, distance(front, rear) / 2) << "\n";
	l.insert(mid, 999);
	
	it = l.begin();
	while (it != l.end()) {
		cout << *it << " ";
		it = next(it);
	}