[C++ STL] LIST

아 .. 원래 나만보려고 했는데... ㅋㅋㅋㅋㅋㅋ^-^

이론 시간에 딴짓하다가 어떤 애도 같이 본다고 해서 뒤늦게 집중한거 안비밀... 건방지다 나자신

암튼 내용 매우 러프함 주의

 

"Sequence List"
장점은 다음과 같다. 
- random access(데이터를 비 연속적으로 접근하는 것)가 용이하다. 
- 자료구조를 빠른 속도로 정렬할 수 있다. 
- 정렬이 가능하다면 binary search를 사용할 수 있고, 시간복잡도 O(NlogN)으로 데이터 탐색이 가능하다. 
- 연산 시간은 O(1) 이다.

"List"
- doubly linked list 이다(양방향으로 데이터를 접근하는 것이 가능).
- 데이터를 빈번하게 추가, 삽입하거나 삭제하는 경우 유용하다. 
- 한편 이러한 동작을 벡터에서 하게 되면, 삭제된 위치를 기준으로 나머지 자료들을 앞으로 당기거나 뒤로 미는 작업이 필요하다. 이러한 경우 연산량이 많아질 수 있다.

#include <iostream>
#include <link>		// link header가 필요하다. 

using namespace std;

list<int> Link;

int main()
{
	// 0. 초기화
    // 참고로 컨테이너 어답터(스택, 큐, .. 등)들은 clear 메서드가 제공되지 않는다. 
    // 반면 컨테이너는 clear 메서드가 제공된다. 
    Link.clear();
    
    
    
    // 1. 데이터 추가 
    // 생성한 List의 iterator의 정확한 타입은 list<int>::iterator 이다. 
    // begin() : head의 바로 뒷 노드
    // 	=> prev(begin()) 안된다. head의 앞은 존재하지 않는다. 
    // 	=> 해당 메서드의 iterator를 가지고 iterator--를 하면 안된다. 
    // end() : tail 위치
    // 	=> next(end()) 안된다. tail의 뒤는 존재하지 않는다. 
    // 	=> 해당 메서드의 iterator를 가지고 iterator++를 하면 안된다. 
    
    // prev() : 앞 자료의 iterator를 리턴값으로 준다. 
    // next() : 뒷 자료의 iterator를 리턴값으로 준다. 
    
    // 1-1. 뒤에 추가 
    // push_back() : end() 메서드의 바로 앞에 추가된다. 
    for (int i = 1; i <= 3; i++){
    	Link.push_back(i);
    }
    
    for (auto iter = List.begin(); iter != List.end(); iter++) {
    	cout << *iter << " ";
    }
    
    // 1-2. 앞에 추가 
    // push_front() : begin() 메서드의 리턴 iterator가 가리키는 노드 앞에 추가된다. 
    Link.push_front(10);
    for (auto iter = List.begin(); iter != List.end(); iter++) { 
    	cout << *iter << " ";
    }
    
    
    
    // 2. 데이터 삭제
    // 2-1. 앞 노드 삭제 (pop)
   	Link.pop_front();
  
    // 2-2. 뒷 노드 삭제 (pop)
    Link.pop_back();
    
    // 2-3. 원하는 값을 가진 모든 노드 제거 (remove)
    Link.push_front(3);
    Link.push_front(3);
    Link.push_front(3);
    Link.push_back(3);
    Link.push_back(3);
    
	Link.remove(3);
    
    // 2-4. 원하는 값을 가진 노드 제거 (erase)
    // 탐색하려는 대상을 이미 알려주었기 때문에 시간복잡도가 O(1) 이다. 
    // erase 메서드의 리턴값은 iter가 가리키는 노드의 다음 노드이다. 
    for (auto iter = Link.begin(); iter != Link.end(); ) {	// 이때 iter를 증가시켜주면 데이터를 건너뛰게 된다. 
    														// 따라서 삭제에 실패하여 iter가 다음노드를 가리키지 못할 때만 증가시켜주어야 한다. 
    	if (*iter == 2) {
        	iter = Link.erase(iter);
        }
        else iter++;
    }
    
    
    
    // 3. 데이터를 원하는 노드 앞에 삽입 (insert)
    // iter가 가리키는 노드 앞쪽에 1004를 추가시킨다. 
    // insert 메서드의 리턴값은 새로 추가된 노드의 iterator이다. 
    // 한편 push_front와 push_back의 리턴은 없다. 각각 begin 메서드의 리턴, end 메서드의 prev로 얻을 수 있기 때문이다.  
    for (auto iter = Link.begin(); iter != Link.end(); iter++){
    	if (*iter == 4) {
        	Link.insert(iter, 1004);
            break;
        }
    }
    
    
    
    // 4. 요소를 원본 목록에서 제거한 다음 대상 목록에 삽입 (slice)
    // (어디에 가져다 붙일 것인지, 무엇을 가져다 붙일 것인지)
    // end() 메서드가 가리키는 노드 앞쪽에 가져가 붙여라. Link4 리스트를 통채로
    // 만약 begin() 메서드로 했다면, begin()이 가리키는 노드 앞쪽에 붙였을 것이다.
    // 해당 작업은 시간복잡도 O(1), 즉 단일 시간 내에 수행할 수 있다. 
    list<int> Link2{1, 2, 3};
    list<int> Link3{10, 9, 8};
    
    Link2.splice(Link2.end(), Link4);
}

---

[백준 1406] 에디터

https://www.acmicpc.net/problem/1406

1406번: 에디터

#include <cstdio>
#include <iostream>
#include <string>
#include <list>
int N;

using namespace std;
list<char> Link;
string str;

int main()
{
	cin >> str;
	for (int i = 0; i < str.size(); i++) {
		Link.push_back(str[i]);
	}

	auto iter = Link.end();		// 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치 
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		char cmd;
		cin >> cmd;
		if (cmd == 'L') {
			if (iter == Link.begin()) continue;	// 커서가 문장의 맨 앞이면 무시됨 
			iter--;	// 커서를 왼쪽으로 한 칸 옮김
		}
		else if (cmd == 'D') {
			if (iter == Link.end()) continue;	// 커서가 문장의 맨 뒤이면 무시됨
			iter++;	// 커서를 오른쪽으로 한 칸 옮김
		}
		else if (cmd == 'B') {
			if (iter == Link.begin()) continue;	// 커서가 문장의 맨 앞이면 무시됨
			Link.erase(prev(iter));	// 커서의 왼쪽에 있는 문자 삭제
		}
		else if (cmd == 'P') {
			char c;
			cin >> c;
			Link.insert(iter, c);	// 입력받은 문자 c를 커서 왼쪽에 추가
		}
	}

	for (auto iter = Link.begin(); iter != Link.end(); iter++) {
		cout << *iter;
	}
	return 0;
}

main에 때려박는거 싫어하는데,,, iterator 넘겨주기 귀찮아서,,,