2.2.4 원형 연결 리스트 (Circular Linked List)

2.2.4 원형 연결 리스트

  2.2.4.1 원형 연결 리스트의 개념

                                                                 

 

      

    

              -> 원형 연결리스트란 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트이다.

 

2.2.4.2 원형 연결 리스트의 장, 단점

장점	단점
한 노드에서 다른 모든 노드로의 접근이 가능하다.  (노드의 삽입, 삭제가 단순해진다.)	노드의 삽입, 삭제시 선행 노드의 포인터가 필요하다.

 

 

2.2.4.3 변형된 원형 연결 리스트의 개념

 

 

      

                 -> 헤드 포인터가 마지막 노드를 가리키도록 구성한 연결 리스트이다.

                 -> 마지막 노드는 헤드 포인터인 head가 가리키고, 첫번째 노드는 head -> link가 가리킨다.

                 -> 그러므로 리스트의 마지막에 노드를 삽입, 삭제시 맨 끝까지 힘들게 가지 않아도 된다. 

 

2.2.4.4 변형된 원형 연결 리스트의 삽입

  

  (1) 원형 연결 리스트의 첫번째 노드로 삽입

             

 

               

                  1) 먼저 새로운 노드의 링크인 node->link가 첫번째 노드를 가리키게 한다.

                  2) 다음 마지막 노드의 링키가 node를 가리키게 한다.

                  3) 헤드 포인터인 head가 마지막 노드를 가리키는 것만 잊지 않으면 된다.

 

 

 

 

 

 

 

    (2) 원형 연결 리스트의 마지막 노드로 삽입

 

             1) (1)의 알고리즘에 *phead = node 한 문장만 추가하면 된다.

             2) 원형 연결리스트는 어차피 원형으로 연결되어 있으므로 어디가 처음이고 끝인지 불분명하다.

             3) 그러므로 head의 위치만 새로운 노드로 바꾸여주면 새로운 노드가 마지막 노드가 된다.

 

 

 

 

 

 

2.2.4.5 원형 연결 리스트의 출력

 

 

    1) 마지막 노드의 링크가 NULL이 아니기 때문에, 리스트 끝에 도달했는지 검사하기 위해선

       헤드 포인터와 비교 해야 한다.

 

    2) 또한 while 루프 대신에 do-while 루프를 써야 한다.

       (while을 쓸 경우 초기 p의 값이 head라 검색을 더이상 진행 하지 않는다.)