[자료구조] Circularly Linked List

2호선 내선순환선처럼, 'Circularly' 라는 표현 그대로 element들이 시작과 끝 지점이 없이 서로가 서로에게 연결되어 있는 자료구조이다. 즉, tail.next = head이다. 

게임개발을 하면서, 오브젝트 풀링을 통해 생성해 둔 오브젝트들을 게임이 진행됨에 따라서 꾸준히 스폰해 줘야 할 일이 있었는데, 나는 이 때 array+index 를 활용했다. 즉 간략하게 쓰자면

void LocateObstacles(Vector3 targetPos)
{
    _obstaclesArr[_obstacleIdx].SetActive(true);
    _obstacleArr[_obstacleIdx].transform.position = targetPos;
    
    _obstacleIdx++;
    if(_obstacleIdx>=_obstaclesArr.Length())
    {
    	_obstacleIdx = 0;
    }
}

이런 류의 method를 만들어서 사용했었다. 그래서 Circularly Linked List를 처음 봤을 때 이 자료구조가 굳이 필요한지 의문을 가졌었다. 반복해서 순회해야 한다면, 인덱스만 잘 움직여 주면 되는 것 아닌가? 하는 생각이 들었기 때문이다.

 

교재의 설명에 따르면 Circularly Linked List는 OS가 round-robin scheduling을 할 때 사용된다고 한다. 후에 OS 관련해서도 따로 자세히 공부하고 포스팅을 해야겠지만 round-robin scheduling은 OS가 여러 task들을 일정 time-slice만큼 잘게 쪼개서 수행하는 것인데, 전통적인 List로 해당 알고리즘을 구현하는 것보다 Circularly Linked List를 사용하는 것이 더 효율적이다. 전통적인 List를 이용한 round-robin scheduling은 removeFirst -> 해당 process를 time slice만큼 수행 -> addLast의 순서로 이루어지는데, 아래 설명하는 Circularly Linked List의 방식으로 비효율성을 개선할 수 있다. 

 

Circularly Linked List는 tail을 tail.next로 한 칸 미루고, 새로운 tail의 next가 새로운 head가 되게 할 수 있다. 이를 rotate 연산이라 하고, O(1) 시간에 수행되기 때문에 round-robin scheduling을 하는 데 더 효율적이다. 즉, Circularly Linked List를 사용한 round-robin scheduling은 time slice만큼 수행 -> rotate() 를 반복하는 방식으로 구현된다.