[ComputerScience] c++와 list

이 게시글은

서울대학교 데이터사이언스대학원

조요한 교수님의

데이터사이언스 응용을 위한 컴퓨팅 강의를

학습을 위해 재구성하였습니다.

---

저번시간에는 vector에 대해 공부했고

이번 시간에는 list에대해 정리해보려한다

 

 

c++의 list는 python의 List와는 다르다

python의 list와 비슷한건 c++의 vector이다

c++의 list는 python의 list와는 다르게

non-contiguous(비연속) memory 구조이다

 

메모리 공간을 비연속적으로 할당받으니

linked list처럼 다음 element의 위치정보를

담는 pointer를 갖고있어야한다

 

c++의 List는

이전 element와 다음 element까지

2개의 포인터를 갖고있다

 

따라서 어느 위치에서나

insertion과 deletion이 가능하지만

random access는 불가능하다

 

 

 

c++의 list가 어떻게 생겼는지

개념적으로 도식화해 본 것이다

 

list는 doubly linked list를 내부적으로 갖고있어서

서로가 서로의 위치를 갖고있는 형태가 된다

그런 데이터들이 모두 heap에 저장이 된다

 

이때, list는 시작과 끝을 표시하는 특별한 노드인

sentinel node를 갖고있다

 

이게 sentinel node를 기점으로

계속 cycle을 도는 구조라고 한다

 

그리고 list 역시

현재 element가 몇 개인지 나타내는

size를 담고있다

 

 

 

list의 initialization이다

 

헤더에 #include <list>를 선언해준다

그다음에 list에 담을 element들의

데이터타입을 선언해준다

 

std::list<std::string> list1;

string element들을 담을 빈 list1을 선언했다

std::list<std::string> list2 = {"app", "bee", "cat"};

app, bee, cat을 담은 List2를 선언했다

std::list<std::string> list3(5, "dog");

dog라는 element를 담은 size 5의 list3을 선언했다

 

 

 

list의 insertion과 deletion이다

push_back은 뒤에 원소 삽입

push_front는 앞에 원소 삽입

pop_back과 pop_front도 마찬가지이다

 

std::advance(it, -4)는

iterator를 4칸 이동시킨다는 의미이다

 

 

 

list에서의 iterator이다

 

Forward iteration은 vector에서 했던 것과 유사하다

Reverse Iteration이 있는데

rbegin()과 rend()를 사용한다

rbegin()은 begin의 Reverse이기때문에

마지막 iterator를 가리키고

rend()는 처음 iterator를 가리킨다

 

 

그럼 여기서 의문이 생길 수 있다

이전에 iterator에서 배웠듯이

end()는

마지막 원소가 아닌 마지막 원소의 다음 요소를 가리키고

rend()는

첫번째 원소의 이전 요소를 가리켜야하는데

이게 노드에서 어떻게 작동하는 것일까?

 

앞서 말했듯이 c++의 list는

doubly linked list구조를 갖고있다

따라서 이는 처음노드와 마지막노드를

표시하는 특별한 노드인 sentinel node를 갖고있는데

sentinel node를 통해

end()나 rend()를 정의할 수 있지만

 

c++의 구현에 따라 

sentinel node를 가리킬수도 있고

일반 이상한 node를 가리킬수도 있어서

end나 rend를 불러와서 프로그래밍을 하는게

좋은 방법은 아니라고한다

 

 

 

list의 메모리 구조이다

iterator를 돌면서 lst라는 List의

메모리 주소들을 찍은 모습이다

 

위 ppt에 있는 코드를 확인해보면

1, 2, 3, 4, 5는 모두

주소들 앞이 0x78dfbf로 시작하는

어딘가에 저장되어있음을 확인할 수 있다

 

하지만 end나 rend의 iterator가

위치한 메모리주소를 확인해보면

0x7ff7b3b로 시작하면서

다른 element들과는 다른 주소로

시작하는 것을 확인할 수 있다

 

이는 1, 2, 3, 4, 5는 비슷한 위치의

어느 메모리 구역에 저장되어있지만

end나 rend는 혼자

다른 동떨어진 곳에 저장되어있다는 뜻이다

 

물리적으로 다른 곳에 위치해있다는 소리이다

 

이렇게 되는 이유는

list의 element들은 heap에 저장이되지만

list가 초기화되면서 함께 생성되는

처음과 끝 노드의 정보를 담고있는

sentinel node는 stack에 저장되기 때문이다

 

 

 

마지막으로 list에서 쓸 수 있는

메소드들을 훑어보고

마무리!