linked list를 직접 구현하는 것은 어렵지 않습니다. 하지만, c++ 링크드리스트 stl 을 사용하면 꽤 간단하게 구현할 수 있습니다.
- 자료구조 링크드리스트에 대해 알아봅시다.
- c++ stl을 이용한 linked list 구현하기 [현재글]
- 배열과 리스트의 차이를 알아봅시다.
- 리스트를 이용해서 lru cache를 구현해 봅시다.
이 글에서는 stl을 이용해서 구현해 봅시다. 실습에 사용될 코드를 단계별로 분리해 봅니다.
iterator 이동하기
먼저, 리스트는 insert, delete 할 위치를 알고 있을 때, 굉장히 효율적으로 동작한다고 했어요. 이 위치를 관리하려면 iterator를 잘 가지고 놀아야 합니다. 이 방법부터 배워봅니다.
먼저 begin()은 리스트의 맨 처음 위치를, end()는 마지막 위치를 가리킵니다. 정확하게, end는 마지막 위치는 아니고, 마지막의 다음 위치를 가리킵니다. 예를 들어, 리스트의 맨 뒤에 2, 4, 5를 추가했다고 해 보겠습니다.
이 경우, begin()은 2를 가리킵니다. 그리고, end()는 5의 next에 있는 원소를 가리키게 됩니다. 이 그림이 이해되셨다면, 아래 그림을 보겠습니다.
cur는 list의 iterator라고 해 보겠습니다. 이제, cur = li.begin(); 문장을 생각해 봅시다. 이는 리스트 li의 첫 번째 위치를 cur가 가리키라는 의미입니다. 즉, 그림에서 군청색 부분을 cur가 가리키게 됩니다. 이제, cur++을 해 보겠습니다.
그러면, 2 다음에 있는 원소 4를 가리키게 됩니다. cur는 iterator 였습니다. 리스트의 iterator를 증가시킨다는 의미는, 다음 원소로 이동한다는 의미입니다. 반대로, 감소시키면, 이전 원소로 이동하겠지요.
이제, 코드의 시작 부분을 보겠습니다. 리스트를 하나 선언하는데요. 9번째 줄과 10번째 줄에 -1을 뒤에 추가했습니다.
그러면, 리스트는 이런 상태일 겁니다. 다음 12번째 줄에 iterator cur를 정의했는데요. (–li.end())라고 되어 있습니다. 무슨 이야기일까요?
- li.end()는 회색 부분을 가리키고 있습니다.
- 이것의 이전으로 가는 것이 감소 연산자이니, 2번째 원소 -1을 가리키게 됩니다.
이를 그림으로 그리면 아래와 같습니다.
이건 굳이 왜 하냐면, 맨 앞과 뒤에 더미 노드를 두기 위함입니다. 생각보다 더미 트릭은 많이 쓰이니 알아두시면 좋습니다. 이 과정까지 이해되셨다면 2번째 문단으로 가 보겠습니다.
insert할 위치를 알고 있을 때 추가 하기
리스트는, 추가할 위치를 알고 있을 때, insert 하는 연산을 매우 효율적으로 수행할 수 있습니다. 삭제 연산 또한 마찬가지입니다. 이러한 연산을 insert 메서드가 제공해 줍니다. 제가 많이 쓰는 insert 메서드가 가지고 있는 인자는 아래와 같습니다.
- iterator
- iterator가 가리키는 위치 앞에 원소가 추가됩니다.
- 넣을 원소
iterator와 넣을 원소. 이 둘만 알면 됩니다?
예를 들어, 위 그림과 같은 상황에서, iterator 인자를 cur, 넣을 원소를 나타내는 인자를 6으로 했다고 해 보겠습니다. 이 경우, insert(cur, 6)을 호출하면, 아래와 같이 동작합니다.
cur가 가리키는 곳 바로 앞에, 새로운 원소인 6이 추가되었습니다.
그러면, 이 코드도 해석할 수 있습니다. 현재 li에는 -1, -1이 들어가 있습니다. cur는 2번째 -1을 가리키고 있는 상황이고요. 2번째 -1 앞에 3을 추가하면 어떻게 될까요?
2번째 -1 앞에 3이 추가됩니다. cur는 변화가 없습니다. 다음에, 2와 5 순으로 추가되는데요.
- 2도 cur 앞에 추가됩니다.
- 5도 cur 앞에 추가됩니다.
고로, -1, 3, 2, 5, -1 순으로 리스트에 수가 들어가 있을 겁니다.
16번째 줄까지 수행된 결과입니다. 다음에, cur–; 문을 2번 수행하였습니다. 이러면, 현재 cur가 가리키는 곳으로부터 이전 원소로 2번 돌아갑니다.
20번째 줄까지 수행하면 위 그림과 같이 됩니다.
삭제할 위치를 알고 있을 때 erase 하기
삭제할 위치를 알고 있다면, erase 역시 매우 효율적으로 수행할 수 있습니다. 삭제할 위치만 넘겨주면요.
- iterator
이것 역시, insert와 마찬가지로 iterator를 받게 됩니다. 주의할 점은, 참조자 무효화가 될 수 있다는 것입니다. 이것이 어떻게 동작하는지 봅시다. 리스트가 아래와 같이 있다고 해 보겠습니다.
cur가 가리키는 원소를 삭제합니다. 즉, li’.erase(cur); 문장을 수행합니다. 이후에는 어떻게 될까요?
cur가 가리키는 원소는 삭제됩니다. 문제는, cur에서 노란색 원소로 가는 방법이 없다는 것입니다. 적어도, 삭제된 후에 cur가 가리키는 원소는 무효화 됩니다. 이를 반복자 무효화라고 합니다. 이 현상을 방지하기 위해서는 어떻게 해야 할까요?
삭제해야 할 위치와, 보존해야 할 위치 2개를 가지고 갑니다. 이 때, 보존해야 할 위치는, 삭제해야 할 원소의 이전이나 다음 원소를 가리키게 하면 됩니다.
22번째 줄부터 보겠습니다. iterator rm_pos에 cur를 대입하였습니다.
그러면 cur와 rm_pos가 군청색으로 칠한 원소를 가리키게 됩니다. 다음, cur++로, cur를 이동시켰습니다.
그러면 rm_pos가 가리키는 원소와, cur가 가리키는 원소가 다름을 알 수 있어요. 이제, 24번째 줄의 문장 li.erase(rm_pos); 을 호출해 보겠습니다.
그러면 rm_pos가 가리키는 원소가 삭제됨을 알 수 있습니다. cur가 가리키는 원소는 삭제되지 않았으므로, 무효화 되지 않습니다. c++ 링크드리스트 stl 구현할 때 조심해야 하는 부분 중 하나입니다.