[C++ STL] List

1. List?

C언어로 자료구조를 했던 사람이라면, 연결리스트를 구현하는데 굉장한 스트레스를 받았던 적이 한번 쯤은 있을 것 이다.

 

구조체를 만들고, 포인터로 연결해주고, 삽입/삭제 등 기능을 일일이 구현하는 것은 굉장히 껄끄러운 작업이다.

 

게다가 이중연결리스트로 구현하라고 하면, 코드가 길어지고 생각해야할 부분이 많아진다..

 

여기서 포인터가 이상한 곳을 가르치고 있다면 컴파일 에러가 뜨는데, 오류 위치를 찾는 것은 정말 번거롭다.

 

다행히도 C와는 다르게 C++ STL은 이중연결리스트를 기반으로 하고 있는 list를 제공한다.

 

헤더는 #include<list> 에 포함되어있다.

---

2.  구현 및 기능

L.push_back(x) : x를 list 맨 뒤에 추가해준다.

L.push_front(x) : x를 list 맨 앞에 추가해준다.

L.erase(it) : 해당 iterator의 값을 지워준다. 반환값은 지운 원소값의 다음 iterator 값이다.

L.insert(it, x) : 해당 iterator 앞에 x를 추가해준다.

 

설명보다 직접 코드를 보고 실습하는 것이 이해하기 더 빠르다.

---

3.  코드

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)

using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	list<int> L = { 1,2,3,4,5 };
	list<int>::iterator it = L.begin();
	cout << *it <<'\n';

	L.push_back(6);
	for (auto e : L)
		cout << e << ' '; // 1 2 3 4 5 6
	cout << '\n';
	
	L.push_front(5);
	for (auto e : L)
		cout << e << ' '; // 5 1 2 3 4 5 6
	
	cout << '\n' << *it << '\n'; // 1
	it = L.erase(it); // 해당 위치를 지워준다.
	for (auto e : L)
		cout << e << ' '; // 5 2 3 4 5 6
	// 그렇다면 it의 위치는?
	cout << '\n'<< * it << '\n'; // 2

	L.insert(it, 9);
	for (auto e : L)
		cout << e << ' '; // 5 9 2 3 4 5 6
}

 

코드에서 iterator의 위치를 잘 살펴봐야한다.

 

iterator은 포인터처럼 주소를 가르치는 것이 아니라 리스트, 배열 등의 순서를 내포하고 있다고 생각하면 편하다.

 

사실 알고리즘 문제에서 list를 사용할 일이 그렇게 많지는 않지만(나와 같은 경우 vector와 array를 자주 사용한다.) , 가끔 삽입과 삭제에 적은 시간복잡도를 원하는 문제에서는 list로 구현해야한다. 따라서 알아두면 나쁘지 않을 것 같다.