<STL> List

List의 특성

• List는 Node 기반 컨테이너이다. 
• List는 이중 연결 리스트(Doubly Linked List)로 구현되어 있다.
  • 이중 연결 리스트 구조로 인해 임의의 위치에 있는 요소에 바로 접근할 수 없다.
  • 원소의 시작과 끝 위치만 기억하기 때문에 임의의 위치에 있는 요소에 접근하기 위해서는 링크를 하나씩 따라가야한다.

  itr++    // itr ++
  itr--  // --itr 가능
  
  itr + 5  // 불가능!

• List는 Vector와 달리 노드 기반으로 서로 연결되어 있어 원소를 삽입하거나 삭제할 때 모든 원소를 밀어내지 않아 속도가 빠르다.
• 삭제시 반복자가 가리키는 원소 자체를 삭제해야 원소가 사라지며, 동작자체에서 반복자를 무효화 시키지 않는다.
• List는 이중 연결 리스트로 구현되어 있여 원소가 저장되어 있는 공간이 불연속적이다. 

이중 연결 리스트

• 연결 리스트에는 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.
• 이중 연결 리스트의 Node는 단순 연결 리스트의 Node에 1개의 주소 필드가 추가된다.
  • 단순 연결 리스트는 Next라는 다음 노드를 가리키는 주소 필드만 존재
  • 이중 연결 리스트는 Prev라는 이전 노드를 가리키는 주소 필드도 존재한다.
• 이중 연결 리스트는 단순 연결 리스트의 중간에 값을 삽입할 수 없는 문제를 해결할 수 있다.
• 이중 연결 리스트는 삽입과 삭제 함수의 일관성을 위해 header와 tailer라는 dummy node가 존재한다.
  • header의 prev와 tailer의 next는 모두 NULL 값을 가리키고 있다.
• 이중 연결 리스트의 prev와 next 포인터가 가리키는 Node를 변경 시키며 삽입 및 삭제를 구현할 수 있다.

삽입&삭제

• List는 STL 컨테이너이므로 삽입 및 삭제를 위한 멤버 함수를 제공한다.
  • push_back() 과 pop_back() 등을 제공

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

int main() {
	list<int> l;

	l.push_back(30);
	l.push_back(20);
	l.push_back(40);
	l.push_front(10); 

	for (list<int>::iterator iter = l.begin(); iter != l.end(); ++iter) {
		cout << (*iter) << '\n';
	}
	cout << "=================" << '\n';

	l.pop_back();
	l.pop_front();
	for (list<int>::iterator iter = l.begin(); iter != l.end(); ++iter) {
		cout << (*iter) << '\n';
	}
	cout << "=================" << '\n';
	list<int> l2(l);
	for (list<int>::iterator iter = l2.begin(); iter != l2.end(); ++iter) {
		cout << (*iter) << '\n';
	}
	cout << "=================" << '\n';

	l2.sort();
	for (list<int>::iterator iter = l2.begin(); iter != l2.end(); ++iter) {
		cout << (*iter) << '\n';
	}
	cout << "=================" << '\n';


	return 0;
}

// 출력
10
30
20
40
=================
30
20
=================
30
20
=================
20
30
=================

• push_back()
  • 마지막 위치에 원소를 삽입
• insert()
  • 현재 반복자가 가리키는 위치에 원소를 삽입
• push_front()
  • 처음 위치에 원소를 삽입
• pop_back()
  • 마지막 위치의 원소를 제거
• pop_front()
  • 처음 위치의 원소를 제거
• erase()
  • 현재 반복자가 가리키는 위치의 원소를 제거
• remove()
  • 주어진 조건을 만족하는 모든 원소를 제거한다.
• push_x(), pop_x(), insert(), erase() 함수는 이중 연결 리스트의 특징으로 인해 O(1)의 시간 복잡도를 가진다.
• remove() 함수는 모든 Node를 순회해야하기 때문에 O(N)의 시간 복잡도를 가진다.

 

출처

https://bunnnybin.tistory.com/entry/C-STL-vector-list-%EA%B7%B8%EB%A6%AC%EA%B3%A0-%EB%B0%98%EB%B3%B5%EC%9E%90

[C++] STL 벡터(vector), 리스트(list), 덱(deque) 그리고 반복자

https://cow-coding.tistory.com/39

[Data Structure] Vector and List (벡터와 리스트)

https://saynot.tistory.com/entry/C-STL-list-%EA%B3%B5%EB%B6%80

[C++] STL - list 공부