데이터 구조-순환 연결 목록

순환 연결 목록은 첫 번째 요소가 마지막 요소를 가리키고 마지막 요소가 첫 번째 요소를 가리키는 연결 목록의 변형입니다. 단일 연결 목록과 이중 연결 목록을 모두 순환 연결 목록으로 만들 수 있습니다.

단일 연결 목록을 원형으로

단일 연결 목록에서 마지막 노드의 다음 포인터는 첫 번째 노드를 가리 킵니다.

이중 연결 목록을 원형으로

이중 연결 목록에서 마지막 노드의 다음 포인터는 첫 번째 노드를 가리키고 첫 번째 노드의 이전 포인터는 양방향으로 원형을 만드는 마지막 노드를 가리 킵니다.

위의 그림에 따라 고려해야 할 중요한 사항은 다음과 같습니다.

마지막 링크의 다음은 단일 연결 목록과 이중 연결 목록의 두 경우 모두 목록의 첫 번째 연결을 가리 킵니다.
이중 연결 목록의 경우 첫 번째 링크의 이전이 목록의 마지막을 가리 킵니다.

기본 작동

다음은 순환 목록에서 지원하는 중요한 작업입니다.

insert − 목록의 시작 부분에 요소를 삽입합니다.
delete − 목록의 시작 부분에서 요소를 삭제합니다.
display − 목록을 표시합니다.

삽입 작업

다음 코드는 단일 연결 목록을 기반으로하는 순환 연결 목록의 삽입 작업을 보여줍니다.

예

insertFirst(data):
Begin
   create a new node
   node -> data := data
   if the list is empty, then
      head := node
      next of node = head
   else
      temp := head
      while next of temp is not head, do
      temp := next of temp
      done
      next of node := head
      next of temp := node
      head := node
   end if
End

삭제 작업

다음 코드는 단일 연결 목록을 기반으로하는 순환 연결 목록에서 삭제 작업을 보여줍니다.

deleteFirst():
Begin
   if head is null, then
      it is Underflow and return
   else if next of head = head, then
      head := null
      deallocate head
   else
      ptr := head
      while next of ptr is not head, do
         ptr := next of ptr
      next of ptr = next of head
      deallocate head
      head := next of ptr
   end if
End

표시 목록 작업

다음 코드는 순환 연결 목록에서 표시 목록 작업을 보여줍니다.

display():
Begin
   if head is null, then
      Nothing to print and return
   else
      ptr := head
      while next of ptr is not head, do
         display data of ptr
         ptr := next of ptr
      display data of ptr
   end if
End

C 프로그래밍 언어로 구현하는 방법에 대해 알아 보려면 여기 를 클릭하십시오 .