리스트

List는 비연속적인 메모리 할당을 허용하는 내장 C++ 시퀀스 컨테이너입니다. 우리가 list에 대해 이야기할 때, 그것은 이중 연결 리스트(doubly linked list)를 의미합니다. forward list라고 불리는 또 다른 유형의 리스트가 있는데, 이는 단일 연결 리스트(singly linked list)를 의미합니다. 

모든 것을 명확히 하기 위해 설명하자면, 
vector 데이터 구조는 연속적인 메모리 할당을 허용하며, 이는 모든 요소가 메모리 상에서 이전 요소 바로 뒤에 위치함을 의미합니다.
반면, linked list 데이터 구조는 데이터 부분(실제 값)과 리스트의 다음 요소의 메모리 주소를 포함하는 포인터를 가진 요소들로 구성됩니다.

C++에는 두 가지 유형의 연결 리스트가 있습니다:

• 이중 연결 리스트(doubly linked list) - list
• 단일 연결 리스트(singly linked list) - forward list

이중 연결 리스트와 단일 연결 리스트의 주요 차이점은 단일 연결 리스트는 정방향으로만 반복(iterate)할 수 있다는 것입니다. 즉, 모든 요소는 자신의 값과 다음 요소의 메모리 주소만 가지고 있습니다. 반면 이중 연결 리스트 요소는 리스트에서 다음 요소와 이전 요소의 위치를 찾는 방법에 대한 정보를 모두 유지합니다.

우리는 파일에 다음과 같이 포함하여 list(이중 연결 리스트)와 forward list(단일 연결 리스트)를 사용합니다:

#include <list>
#include <forward_list>

또는 단순히 bits/stdc++.h 헤더 파일만 포함할 수도 있습니다.

Forward List

먼저 forward list에 대해 알아보겠습니다. forward list에는 많은 메서드가 있지만, 가장 유용한 것들에 대해 이야기하겠습니다.
우리는 vector나 deque에서 했던 것과 똑같이 forward list를 선언합니다.

forward_list<int> flist = {1, 2, 3};

push_front() 메서드를 사용하여 요소를 추가할 수 있고, pop_front()를 사용하여 맨 앞의 요소를 제거할 수 있습니다.

flist.push_front(5);
for (int &x : flist) // 매 반복마다 값이 증가하는 포인터를 사용하여 요소를 출력합니다.
	cout << x << " ";
cout << endl;

flist.pop_front();
for (int &x : flist)
	cout << x << " ";

Output:
5 1 2 3
1 2 3

Forward List 메서드

List

다음은 list입니다. list 데이터 구조에도 많은 메서드가 사용되지만, 가장 유용한 것들을 소개해 드리겠습니다. 
먼저, .cpp 파일 상단에 포함시킨 후 list를 선언하는 방법을 배우게 됩니다. 

list<int> list1 = {1, 2, 3};

push_front() 또는 push_back() 메서드를 사용하여 리스트에 요소를 추가할 수 있습니다.
마찬가지로, pop_front()와 pop_back() 메서드를 사용하여 각각 첫 번째와 마지막 요소를 제거할 수 있습니다.

list1.push_back(4);
list1.push_front(0);
for (int &x : list1)
	cout << x << " ";
cout << endl;

list1.pop_front();
list1.pop_back();
for (int &x : list1)
	cout << x << " ";

Output:
0 1 2 3 4
1 2 3

List 메서드