C++에서 목록을 통해 반복
이 간단한 프로그래밍 튜토리얼은 C++에서 널리 사용되는 데이터 구조, 즉 List
에 대해 설명합니다. C++ 표준 템플릿 라이브러리(STL)에는 이 데이터 구조에 사용할 수 있는 list
클래스가 있습니다.
목록에 대해 여러 작업을 수행하는 데 사용할 수 있는 기능 번들과 함께 제공됩니다. 이 기사의 뒷부분에서 목록을 탐색하고 목록을 보거나 편집하는 방법에 대해 설명합니다.
C++로 나열
목록 또는 연결 목록은 데이터 컨테이너 역할을 하고 데이터를 메모리에 저장할 수 있는 선형 데이터 구조입니다. 벡터 및 배열과 달리 목록의 데이터는 인접한 메모리 위치에 저장되지 않습니다.
대신 데이터는 임의의 메모리 위치에 저장됩니다. 목록에 삽입된 각 요소를 노드
라고 합니다.
목록의 각 노드
에는 목록의 다음 요소를 가리키는 포인터가 포함됩니다. 이것이 목록의 요소가 인접한 위치에 저장되지 않는 이유입니다. 따라서 연결 목록이라고도 합니다.
목록은 두 가지 유형으로 분류할 수 있습니다.
- 단일 연결 리스트
- 이중 연결 리스트
단일 연결 목록
이러한 유형의 링크 목록에서 모든 노드는 두 부분으로 구성됩니다. 하나는 데이터용이고 다른 하나는 다음 노드를 가리키는 포인터를 저장하기 위한 것입니다. 두 번째 부분은 목록의 다음 노드 주소를 저장합니다.
이중 연결 목록
이 유형의 링크 목록에서 모든 노드는 3개의 부분으로 구성되며, 첫 번째 부분은 이전 노드에 대한 포인터, 두 번째 부분은 데이터 저장, 세 번째 부분은 목록의 다음 요소를 참조하는 포인터를 포함합니다.
STL의 list
클래스에는 이중 연결 목록이 포함되어 있습니다. 배열과 마찬가지로 이 목록 유형의 삽입 및 삭제에는 선형 시간이 걸립니다.
그러나 목록에는 전염성 메모리 블록이 필요하지 않습니다. 게다가 한 번에 하나의 목록 노드를 연결하여 목록을 늘리는 것이 전체 동적 배열을 재할당하는 것보다 더 쉽고 합리적입니다(벡터에 의해 수행됨).
따라서 배열 및 벡터와 같은 다른 데이터 구조보다 유연한 데이터 구조로 간주됩니다.
또 다른 데이터 구조인 forward_list
는 한 방향으로만 반복할 수 있으며 단일 연결 목록입니다. 다른 데이터 구조와 비교할 때 목록 및 순방향 목록의 주요 단점은 배열과 같이 위치를 지정하여 목록 요소에 직접 액세스할 수 없다는 것입니다.
예를 들어, 목록의 다섯 번째 요소에 액세스하려면 끝점에서 시작하거나 해당 위치까지 시작해야 하며 선형 시간이 걸립니다. 목록은 또한 추가 RAM을 사용하여 각 요소에 대한 연결 정보를 저장합니다.
C++에서 목록을 통해 반복
표준 템플릿 라이브러리 C++의 iterator
클래스를 사용하여 목록 요소를 탐색할 수 있습니다. 이에 대한 구문은 다음과 같습니다.
std::list<int>::iterator itr;
목록에는 다양한 반복 방법이 있습니다.
기능 이름 | 설명 |
---|---|
itr.begin() |
목록의 첫 번째 노드에 대한 포인터를 제공합니다. |
itr.end() |
목록의 마지막 노드에 대한 포인터를 제공합니다. |
목록 클래스의 다른 기능을 사용하는 아래 코드를 살펴보겠습니다.
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <list>
using namespace std;
void displaylist(list<int> l) // print function to show list
{
list<int>::iterator myitr;
for (myitr = l.begin(); myitr != l.end(); ++myitr) cout << " " << *myitr;
cout << endl;
}
int main() {
list<int> mylist1;
for (int a = 0; a < 10; ++a) {
int r = 1 + (rand() % 50);
mylist1.push_back(r);
}
cout << "\nData of List 1 : ";
displaylist(mylist1);
cout << "\nList first element : " << mylist1.front();
cout << "\nAfter we pop first element: ";
mylist1.pop_front();
displaylist(mylist1);
cout << "\nWhen we sort the list: ";
mylist1.sort();
displaylist(mylist1);
return 0;
}
출력:
Data of List 1 : 34 37 28 16 44 36 37 43 50 22
List first element : 34
After we pop first element: 37 28 16 44 36 37 43 50 22
When we sort the list: 16 22 28 36 37 37 43 44 50