Home » 자료구조 » c++ 링크드리스트 stl 이용해서 간단하게 구현해 봅시다.

c++ 링크드리스트 stl 이용해서 간단하게 구현해 봅시다.

linked list를 직접 구현하는 것은 어렵지 않습니다. 하지만, c++ 링크드리스트 stl 을 사용하면 꽤 간단하게 구현할 수 있습니다.

이 글에서는 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를 증가시킨다는 의미는, 다음 원소로 이동한다는 의미입니다. 반대로, 감소시키면, 이전 원소로 이동하겠지요.

[그림 1] 코드에서 list 초기화 하기

이제, 코드의 시작 부분을 보겠습니다. 리스트를 하나 선언하는데요. 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이 추가되었습니다.

[그림 2] 3, 2, 5를 추가하기

그러면, 이 코드도 해석할 수 있습니다. 현재 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개를 가지고 갑니다. 이 때, 보존해야 할 위치는, 삭제해야 할 원소의 이전이나 다음 원소를 가리키게 하면 됩니다.

[그림 3] 2를 제거하기

22번째 줄부터 보겠습니다. iterator rm_pos에 cur를 대입하였습니다.

그러면 cur와 rm_pos가 군청색으로 칠한 원소를 가리키게 됩니다. 다음, cur++로, cur를 이동시켰습니다.

그러면 rm_pos가 가리키는 원소와, cur가 가리키는 원소가 다름을 알 수 있어요. 이제, 24번째 줄의 문장 li.erase(rm_pos); 을 호출해 보겠습니다.

그러면 rm_pos가 가리키는 원소가 삭제됨을 알 수 있습니다. cur가 가리키는 원소는 삭제되지 않았으므로, 무효화 되지 않습니다. c++ 링크드리스트 stl 구현할 때 조심해야 하는 부분 중 하나입니다.

Leave a Comment

1 + 1 =