연결 리스트 - 반복자(Iterator)

연결 리스트에서 같은 위치에 여러번 삽입/삭제가 일어나는 경우 해당 위치를 기억하고 싶을 때는 어떻게 해야 할까요? 배열에서의 index와 같은 역할을 하는 것이 있으면 편하게 사용할 수 있지 않을까요? 이러한 역할을 해주는 것이 바로 반복자(Iterator) 입니다. 오늘은 연결리스트에서 사용하는 반복자(Iterator)에 대해서 알아보도록 하겠습니다.

 

🔎 반복자란?

반복자는 특정 노드의 위치를 지정해줄 수 있습니다. 연결 리스트 형태에서 삽입/삭제를 하려면 해당 노드의 위치까지 탐색 과정을 먼저 거쳐야 합니다. 이는 $O(n)$의 시간복잡도가 필요한데요, 동일한 위치에 삽입/삭제가 반복적으로 일어나는 경우 반복자를 이용하여 해당 위치를 지정해두면 탐색 없이 삽입/삭제 연산이 가능하게 됩니다.

 

 

🧮 반복자와 삽입/삭제 연산

🔷 Iterator 없이 삽입하는 경우

노드가 2개일 때 맨 뒤에 새로운 노드를 넣는 상황을 가정해 보도록 하겠습니다.

 

마지막 노드를 찾기 위해 Tail까지 탐색을 한 후, 맨 뒤에 노드를 넣어줍니다. 이 때의 시간복잡도는 탐색 $O(n)$, 삽입 $O(1)$ 입니다. 이후에 3번째 노드 앞에 새로운 노드를 넣으려면 어떻게 될까요?

 

3번째 노드인 Tail을 찾기 위해 다시 한번 탐색을 한 후, Tail 앞에 새로운 노드를 생성해야 합니다. 이 때의 시간복잡도 또한 $O(n)$, 삽입 $O(1)$ 입니다.

 

따라서 삽입할 때 마다 탐색으로 $O(n)$의 시간복잡도가 되는 것을 확인할 수 있습니다.

 

🔷 Iterator가 있을 때 삽입하는 경우

그러면 Iterator가 있는 경우 어떻게 달라지게 되는지 알아보겠습니다.

첫 삽입에서는 똑같이 두번째까지 탐색을 실행하여 Tail 뒤에 노드를 넣어주게 됩니다. Iterator는 Head 노드부터 한칸씩 뒤로 이동하여 두번째 노드를 가리키고 있게 됩니다. 이 때의 시간복잡도는 탐색 $O(n)$, 삽입 $O(1)$ 입니다.

이후 3번째 데이터 앞에 새로운 노드를 넣어야 합니다. 이 때, Iterator가 이미 두 번째 노드를 가리키고 있기 때문에 바로 다음 노드가 3번째 노드가 됩니다.

따라서 3번째 노드는 Iterator.next로 구할 수 있습니다. 이 경우 시간복잡도는 탐색(이동) $O(1)$, 삽입 $O(1)$ 이 됩니다.

 

이와 같이 이전 위치와 연관된 곳에 삽입/삭제가 일어나는 경우 Iterator를 이용하면 탐색 시간이 감소합니다.

 

✏️ Iterator의 구현

Iterator의 구현은 복잡한 것이 아니고 변수를 하나 만들어 Head 노드를 저장하면 그것이 Iterator가 됩니다.

/*
  DoublyLinkedList라는 이중 연결 리스트 클래스가 있다고 가정
  pushBack() : 리스트의 가장 뒤에 노드를 삽입하는 함수
  begin() : 리스트의 head를 리턴하는 함수
  end() : 리스트의 tail을 리턴하는 함수
*/

const dll = new DoublyLinkedList(); //이중 연결 리스트 선언

dll.pushBack('test1');
dll.pushBack('test2');
dll.pushBack('test3');

iterator = dll.begin(); //반복자 설정
while(iterator !== dll.begin()) {
    console.log(iterator.data);
    iterator = iterator.next;
}

 

위의 코드를 보면, iterator라는 변수에 리스트의 head 노드를 넣어주었습니다. iterator 변수는 while문을 돌면서 다음 위치의 노드들을 가리킵니다. 노드 자체를 넣어준 것이기 때문에 다른 노드들과 같이 prev, next 를 통해 앞 뒤의 노드로 이동하는것이 가능하며, data 를 통해 저장된 데이터를 반환할 수도 있습니다.