순환 연결 목록: 장점과 단점

순환 연결 목록이란 무엇입니까?

원형 연결 리스트는 각 노드를 다시 연결할 수 있도록 배열된 노드들의 시퀀스입니다.trac각 "노드"는 자기 참조적인 요소이며, 바로 인접한 하나 또는 두 개의 노드를 가리키는 포인터를 가지고 있습니다.

아래는 3개의 노드로 구성된 원형 연결 리스트를 보여줍니다.

여기서 각 노드가 다시 생성되는 것을 볼 수 있습니다.trac자기 자신과 연결 가능합니다. 위 예시는 원형 단일 연결 리스트입니다.

참고: 가장 간단한 원형 연결 리스트는 다음 포인터가 있는 단일 노드로 구성됩니다. trac아래 그림과 같이 원래 모습으로 돌아갑니다.

Basic Opera원형 연결 리스트의 tions

원형 연결 리스트에 대한 세 가지 기본 연산은 다음과 같습니다.

1. 삽입
2. 삭제 및
3. 순회

• 삽입은 순환 연결 리스트의 특정 위치에 노드를 배치하는 프로세스입니다.
• 삭제는 연결된 목록에서 기존 노드를 제거하는 프로세스입니다. 노드는 해당 값의 발생이나 위치로 식별할 수 있습니다.
• 원형 연결 리스트의 순회는 연결 리스트의 전체 내용을 표시하고 다시 표시하는 과정입니다.trac소스 노드로 되돌아갑니다.

다음 섹션에서는 삽입이 어떻게 작동하는지, 그리고 원형 단일 연결 리스트에서 가능한 두 가지 유형의 삽입에 대해 설명합니다.

삽입 Opera기

먼저 아래 그림과 같이 다음 포인터가 자기 자신을 가리키는 노드를 하나 생성합니다. 이 시드 노드가 없으면 첫 번째 삽입이 리스트의 첫 번째 노드가 됩니다.

다음으로 두 가지 가능성이 있습니다.

• 원형 연결 리스트의 현재 위치에 삽입합니다. 이는 일반적인 단일 연결 리스트의 시작 또는 끝에 삽입하는 것과 같습니다. 원형 연결 리스트에서는 시작과 끝이 동일합니다.
• 색인화된 노드 뒤에 삽입합니다. 노드는 해당 요소 값에 해당하는 인덱스 번호로 식별되어야 합니다.

원형 연결 리스트의 시작이나 끝, 즉 최초 노드가 추가된 위치에 노드를 삽입하려면 다음 단계를 따르십시오.

• 기존 노드에 대한 기존 자체 링크를 끊어야 합니다.
• 새 노드의 다음 포인터는 기존 노드에 연결됩니다.
• 마지막 노드의 다음 포인터는 삽입된 노드를 가리킵니다.

참고: 원의 시작 또는 끝을 나타내는 포인터는 임의의 노드로 재할당할 수 있습니다. 하지만 이 경우에도 순회는 동일한 노드로 되돌아옵니다. 이에 대해서는 이 문서 뒷부분에서 자세히 설명합니다.

(a) i-iii의 단계는 다음과 같습니다.

(기존 노드)

단계 1) 기존 링크 끊기

단계 2) 정방향 링크 생성(새 노드에서 기존 노드로)

단계 3) 첫 번째 노드에 대한 루프 링크 생성

다음으로 노드 뒤에 삽입을 시도합니다.

예를 들어, 시작점이 "VALUE0"을 가진 노드라고 가정할 때, "VALUE0"을 가진 노드 뒤에 "VALUE2"를 삽입합니다.

• 첫 번째 노드와 두 번째 노드 사이의 연결을 끊고, "VALUE2"라는 노드를 그 사이에 배치합니다.
• 첫 번째 노드의 다음 포인터는 새 노드를 가리키고, 새 노드의 다음 포인터는 이전에 두 번째 노드였던 곳을 가리킵니다.
• 나머지 구성은 변경되지 않습니다. 모든 노드가 재설정됩니다.trac스스로에게 가능하다.

참고: 배열이 순환적이므로 노드를 삽입하는 절차는 어느 위치를 선택하든 동일합니다. 순환을 닫는 포인터는 목록의 다른 포인터와 마찬가지로 동작합니다.

이는 아래와 같습니다.

(노드가 XNUMX개만 있다고 가정해 보겠습니다. 이는 사소한 경우입니다.)

단계 1) 연결된 노드 사이의 내부 링크를 제거합니다.

단계 2) 왼쪽 노드를 새 노드에 연결

단계 3) 새 노드를 오른쪽 노드에 연결합니다.

삭제 Opera기

3개의 노드로 이루어진 원형 연결 리스트를 가정해 봅시다. 삭제의 두 가지 경우는 다음과 같습니다.

• 현재 요소 삭제
• 요소 이후 삭제.

시작/끝 삭제:

1. 마지막 노드에서 첫 번째 노드로 이동합니다.
2. 리스트의 끝에서 삭제하려면 마지막 노드에서 첫 번째 노드로 이동하는 단 한 번의 순회 단계만 필요합니다.
3. 마지막 노드와 첫 번째 노드 사이의 링크를 삭제합니다.
4. 마지막 노드를 첫 번째 노드의 다음 요소에 연결합니다.
5. 첫 번째 노드를 해제합니다.

(기존 설정)

단계 1) 원형 링크를 제거하세요

단계 2) 첫 번째와 다음 노드 사이의 링크를 제거하고 마지막 노드를 첫 번째 노드 다음 노드에 연결합니다.

단계 3) 첫 번째 노드를 해제/할당 해제합니다.

노드 삭제:

1. 삭제할 노드가 다음 노드가 될 때까지 순회합니다.
2. 다음 노드로 이동하여 이전 노드에 포인터를 놓습니다.
3. 다음 포인터를 사용하여 이전 노드를 현재 노드 뒤의 노드에 연결합니다.
4. 현재(링크 해제된) 노드를 해제합니다.

단계 1) 'VALUE1'이 있는 노드를 삭제해야 한다고 가정해 보겠습니다.

단계 2) 이전 노드와 현재 노드 사이의 링크를 제거한 다음, 이전 노드를 현재 노드의 다음 포인터가 가리키는 노드(VALUE1 다음 노드)에 직접 연결합니다.

단계 3) 현재 노드를 해제하거나 할당을 취소합니다.

순환 연결 목록 순회

마지막 포인터에서 시작하여 원형 연결 리스트를 순회하려면 먼저 마지막 포인터가 NULL인지 확인합니다. NULL이 아니면 리스트에 요소가 하나만 있는지 확인합니다. 그렇지 않으면 아래 애니메이션에서처럼 임시 포인터를 사용하여 마지막 포인터에 다시 도달할 때까지 리스트를 순회합니다.

순환 연결 리스트의 장점

순환 연결 목록의 장점 중 일부는 다음과 같습니다.

1. 코드에 NULL 할당이 필요하지 않습니다. 순환 목록은 완전히 할당이 해제되지 않는 한 NULL 포인터를 가리키지 않습니다.
2. 원형 연결 리스트는 시작과 끝이 일치하기 때문에 리스트 끝 연산에 유리합니다. Algorithms 라운드 로빈 스케줄링과 같은 방식은 큐에 대기 중인 프로세스를 깔끔하게 처리하여, 유효하지 않은 포인터나 NULL 포인터를 만나지 않도록 할 수 있습니다.
3. 원형 연결 리스트는 단일 연결 리스트의 모든 일반적인 연산을 지원합니다. 이중 연결 리스트 심지어 요소를 찾기 위해 전체 목록을 순회할 필요성을 없앨 수도 있습니다. 최악의 경우에도 목표 요소는 시작 포인터의 반대편에 있으므로 목록의 절반만 순회하면 됩니다.

순환 연결 목록의 단점

순환 연결 리스트를 사용할 때의 단점은 다음과 같습니다.

1. 원형 리스트는 보다 복잡합니다. 단일 연결 리스트.
2. Rev원형 리스트를 뒤집는 것은 단일 연결 리스트나 이중 연결 리스트를 뒤집는 것보다 더 복잡합니다.
3. 루프 종료를 신중하게 처리하지 않으면 순회 코드가 무한 루프에 빠질 수 있습니다.
4. 목록의 끝을 찾고 올바른 루프 제어 조건을 작성하는 것이 더 어렵습니다.
5. 리스트 맨 처음에 삽입하려면 (구현 관점에서) 마지막 노드에 도달하기 위해 전체 리스트를 순회해야 합니다.

순환 연결 리스트로서의 단일 연결 리스트

아래 C 코드를 읽고 구현해 보시기 바랍니다. 이 코드는 원형 단일 연결 리스트와 관련된 포인터 연산을 보여줍니다.

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

코드 설명:

1. 코드의 처음 두 줄은 필요한 포함 헤더 파일입니다.
2. 다음 섹션에서는 각 자기 참조 노드의 구조를 정의합니다. 이 구조는 값과 구조체와 동일한 유형의 포인터를 포함합니다.
3. 각 구조체 인스턴스는 동일한 유형의 다른 구조체 객체와 연결됩니다.
4. 다음과 같은 다양한 기능 프로토타입이 있습니다.
   1. 빈 연결리스트에 요소 추가하기
   2. 에 삽입 현재 지적되고 있는 순환 연결 리스트의 위치
   3. 특정 뒤에 삽입 색인 연결리스트의 값
   4. 특정 이후 제거/삭제 색인 연결리스트의 값
   5. 순환 연결 리스트의 현재 가리키는 위치에서 제거
5. 마지막 함수는 연결된 목록의 모든 상태에서 순환 순회를 통해 각 요소를 인쇄합니다.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
  
struct node *insertCurrent(struct node *last, int data)

코드 설명:

1. addToEmpty 코드의 경우 malloc() 함수를 사용하여 빈 노드를 할당합니다.
2. 들어오는 데이터를 임시 노드에 저장합니다.
3. 임시 노드를 마지막 노드로 지정하고 다음 포인터를 자기 자신으로 설정하여 단일 노드가 다시 자기 자신을 가리키도록 합니다.
4. 마지막 포인터를 main() / 애플리케이션 컨텍스트로 반환합니다.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

코드 설명

1. 리스트가 비어 있으면 addToEmpty() 함수로 전달하고 제어권을 반환합니다.
2. 현재 노드 뒤에 배치할 임시 노드를 생성합니다.
3. 위 그림과 같이 포인터를 연결하십시오.
4. 이전 함수에서 사용된 패턴과 일치하는 마지막 포인터를 반환합니다.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

코드 설명:

1. 목록이 비어 있으면 검색 키를 무시하고 현재 항목을 목록에 유일한 노드로 추가한 다음 제어권을 반환합니다.
2. do-while 루프의 각 반복에서 이전 포인터는 마지막으로 순회한 결과를 저장합니다.
3. 그래야만 다음 순회 단계가 진행됩니다.
4. do-while 문은 목표 데이터가 발견되거나 temp 변수가 마지막 포인터에 다시 도달하면 종료됩니다. 다음 코드 블록은 발견된 항목을 어떻게 처리할지 결정합니다.

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

코드 설명:

1. 전체 목록을 모두 탐색했지만 항목을 찾지 못한 경우 "요소를 찾을 수 없습니다"라는 메시지를 표시하고 호출자에게 제어권을 반환합니다.
2. 대상 노드를 찾았으면 삽입할 값을 위해 새 노드를 할당합니다.
3. (링크) 이전 노드에서 새 노드로 이동하고, 새 노드의 다음 포인터를 temp(순회 변수)에 연결합니다.
4. 이렇게 하면 새 요소가 원형 연결 리스트에서 대상 노드 바로 뒤에 추가됩니다. 그런 다음 제어권이 호출자에게 돌아갑니다.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

코드 설명

1. 현재 노드를 제거하려면 먼저 리스트가 비어 있는지 확인합니다. 리스트가 비어 있으면 어떤 요소도 제거할 수 없습니다.
2. 임시 변수가 한 링크 앞으로 이동합니다.
3. 마지막 포인터를 첫 번째 노드 다음 노드에 연결합니다.
4. 연결 해제된 노드의 메모리를 해제하려면 임시 포인터를 해제하십시오.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

코드 설명

1. 이전의 제거 기능과 마찬가지로, 먼저 리스트가 비어 있는지 확인합니다. 리스트가 비어 있으면 요소를 제거할 수 없습니다.
2. 두 포인터 삭제할 요소를 찾을 수 있는 특정 위치가 할당됩니다.
3. 포인터는 이전 트레일 임시 값에 따라 하나씩 순차적으로 이동합니다.
4. 탐색은 목표 요소를 찾거나 다음 포인터가 다시 마지막 노드에 도달할 때까지 계속됩니다.

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

프로그램 설명

1. 연결 리스트 전체를 탐색했지만 원하는 요소를 찾지 못하면 "요소를 찾을 수 없습니다"라는 메시지가 표시됩니다.
2. 그렇지 않으면 3단계와 4단계에서 해당 요소의 연결이 해제되고 해제됩니다.
3. 이전 포인터는 temp의 다음 포인터가 가리키는 노드(삭제되는 노드 다음 노드)에 연결됩니다.
4. 그러면 임시 포인터가 해제됩니다.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;  
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

코드 설명

1. 노드가 하나도 없는 경우에는 미리 보기 탐색이 불가능합니다. 사용자는 먼저 노드를 할당하거나 삽입해야 합니다.
2. 노드가 하나만 있는 경우 순회할 필요가 없습니다. 노드의 내용이 직접 출력되고 while 루프는 실행되지 않습니다.
3. 노드가 두 개 이상인 경우, temp는 마지막 요소까지 모든 항목을 출력합니다.
4. 마지막 요소에 도달하는 순간 루프가 종료되고 함수는 main() 함수로 제어권을 반환합니다.

순환 연결 목록의 응용

• 시스템 프로세스에서는 라운드 로빈 스케줄링을 구현하고 고속 그래픽에서는 순환 스케줄링을 구현합니다.
• 컴퓨터 네트워크에서의 토큰링 스케줄링.
• 디지털 전광판과 같이 지속적인 데이터 전송이 필요한 디스플레이 장치에 사용됩니다.

자주 묻는 질문