원형연결리스트

1. 원형연결리스트 원형연결리스트 (Circular Lilnked List)는 마지막 노드가 첫 노드와 연결된 단순연결리스트 원형연결리스트에서는 마지막 노드의 레퍼런스가 저장된 last가 단순연결리스트의 head와 같은 역할 마지막 노드와 첫 노드를 O(1) 시간에 방문할 수 있는 장점 리스트가 empty가 아니면 어떤 노드도 null 레퍼런스를 가지고 있지 않으므로 프로그램에서 null 조건을 검사하지 않아도 되는 장점 원형연결리스트에서는 반대 방향으로 노드들을 방문하기 쉽지 않으며, 무한 루프가 발생할 수 있음에 유의할 필요 [원형연결리스트의 응용] 여러 사람이 차례로 돌아가며 하는 게임을 구현하는데 적합한 자료구조 많은 사용자들이 동시에 사용하는 컴퓨터에서 CPU 시간을 분할하여 작업들에 할당하는 운영체제에 사용 이항힙(Binomial Heap)이나 피보나치힙(Fibonacci Heap)과 같은 우선순위큐를 구현하는 데에도 원형연결리스트가 부분적으로 사용 2. 원형연결리스트를 ...

원문링크 : 원형연결리스트