STL에서 제공하는 자료 구조 중 하나인 list는 연결리스트 개념을 바탕으로 만들어졌습니다.
따라서 list를 사용하기 위해서는 연결리스트란 무엇인지 알아야합니다.
-연결 리스트
연결리스트는 배열과 비슷하게 생긴 자료구조지만, 몇가지 특징을 통해 뚜렷하게 구별됩니다.
아래는 배열과 연결리스트를 간단하게 표현한 모습입니다.
첫번째는 배열의 구조를 나타낸 것이고,
두번째와 세번째는 각각 연결 리스트의 종류 중 하나인 단방향 연결 리스트와 양방향 연결 리스트입니다.
배열은 index를 이용하여 거북이나 사자, 호랑이, 햄스터에 접근할 수 있습니다.
하지만 연결리스트는 이와 같이 index로 직접 접근하지 않습니다.
연결리스트는 node(노드)라 불리는 하나의 데이터에서 다음 node의 위치를 찾아 접근합니다.
node란, 내가 저장하고자 하는 데이터 + 다음 노드(연결리스트 종류 중 단방향의 경우)를 저장한 하나의 집합체입니다.
따라서 node안에는 내가 저장할 데이터 뿐만 아니라 다음 노드가 어디에 있는지 그 위치 또한 저장해야합니다.
예시로, '호랑이'라는 데이터를 가져 오고 싶다고 가정해봅시다.
배열의 경우에는 array[2] 로 접근하면 바로 '호랑이'라는 데이터를 가져올 수 있습니다.
하지만 연결리스트는 다음과 같이 동작합니다.
head node 에서 다음 node로 찾아감. => '거북이' data가 있는 node에서 다음 node로 찾아감.
=>'사자' data가 있는 node로 찾아감. => '호랑이' data가 있는 node에 도착함.
얼핏 보면 연결리스트가 배열보다 복잡하고 더 불편해 보이지만, 연결리스트는 다음과 같은 장점을 갖고 있습니다.
1. 배열과 같이 길이가 고정되지 않아 자유자재로 크기를 변경할 수 있다.
학생을 저장하기 위한 배열 student를 만들고, 총 학생이 20명일 것을 예상하여 student[20] 으로 배열의 크기를 정했다고 가정합시다.
그러나 어느 시점부터 학생수가 점점 늘어나서 20명을 초과한다면,
이전의 배열은 꽉 차서 더 저장할 수 없기 때문에 더 큰 크기의 배열을 만들고, 이전 정보를 옮겨야합니다.
반대로, 학생이 총 100명 들어올 것이라고 생각하여 student[100]으로 배열의 크기를 정했는데,
예상과 다르게 학생이 10명만 들어왔다면 나머지 90만큼의 메모리는 사용되지 않으므로 낭비됩니다.
연결리스트는 배열와 다르게 노드가 생길때 이전 노드의 뒤에 마치 기차놀이와 같은 형태로 연결되기 때문에,
길이가 고정되지 않고 가변적이기 때문에 필요할때 마다 길이를 늘릴수 있습니다.
2. 중간에 데이터를 삽입하고 삭제하는 것이 편하다.
총 80명의 학생 정보를 저장하는 배열이 있다고 가정합시다.
만약 새로운 학생이 들어왔는데 이 학생을 배열의 46번째 index에 넣고싶다고 하면,
기존의 46번째 index에 있던 학생을 47번째로, 47번째에 있는 학생을 48번째로 계속해서 밀어야만
중간에 학생 데이터를 넣을 수 있게 됩니다.
그러나 연결리스트는 아래와 같이 데이터를 삽입할 수 있습니다.
삽입 이전에 '사자' data가 있는 node가 다음 node로 '호랑이' data가 담겨있는 node를 가리키고 있었는데,
이것을 새로 삽입할 '하마' data가 있는 node를 가리키도록 합니다.
그리고 새로 삽입된 '하마' data가 있는 node는 다음 node로 호랑이를 가리킵니다.
다음 node를 가리킴으로써 각각의 데이터가 연결되어 리스트의 형태를 갖는 특성때문에
간단하게 가리키는 node만 변경함으로써 중간에 data 삽입이 가능해지는 것입니다.
삭제 또한 삽입과 유사한 방법으로 수행됩니다.
- STL : list
list는 이중 연결리스트 구조를 가진 STL이며, 단일 연결리스트 구조는 foward_list를 사용해야합니다.
아래는 list에서 자주 사용되는 주요 멤버 함수들입니다.
| iterator | begin() | 첫번째 원소를 가리키는 반복자 | |||||
| end() | 마지막 원소를 가리키는 반복자 | ||||||
| rbegin() | 역 방향으로 첫번째 원소를 가리키는 반복자 | ||||||
| rend() | 역 방향으로 마지막 원소를 가리키는 반복자 | ||||||
| member function | begin | 첫번째 위치를 가리킴 | |||||
| end | 마지막 위치의 다음을 가리킴 | ||||||
| rbegin | 역 방향으로 첫번째 위치를 가리킴 | ||||||
| rend | 역 방향으로 마지막 위치를 가리킴 | ||||||
| push_front | 제일 앞에 데이터 추가 | ||||||
| pop_front | 제일 앞의 데이터 삭제 | ||||||
| push_back | 마지막 위치에 데이터 추가 | ||||||
| pop_back | 마지막 위치의 데이터 삭제 | ||||||
| front | 첫 번째 데이터의 참조 리턴 | ||||||
| back | 마지막 데이터의 참조 리턴 | ||||||
| clear | 저장하고 있는 데이터 모두 삭제 | ||||||
| empty | 저장한 데이터 없으면 true 리턴 | ||||||
| size | 저장하고 있는 데이터 개수 리턴 | ||||||
| insert | 지정된 위치에 데이터 삽입 | ||||||
| erase | 지정된 범위에 있는 데이터 삭제 | ||||||
| remove | 지정된 값과 일치하는 모든 데이터 삭제 | ||||||
| remove_if | 함수객체의 조건을 만족하는 모든 데이터 삭제 | ||||||
| sort | 데이터 정렬 | ||||||
'프로그래밍 언어 > c++' 카테고리의 다른 글
| [C++] STL 프로그래밍 (1) - 템플릿 (0) | 2020.07.27 |
|---|