순환 연결 목록: 장점과 단점
사라 첸
순환 연결 목록이란 무엇입니까?
순환 연결 리스트는 각 노드가 자신에게 되돌아갈 수 있도록 배열된 일련의 노드입니다. 여기서 "노드"는 바로 근처에 있는 하나 또는 두 개의 노드를 가리키는 포인터가 있는 자체 참조 요소입니다.
아래는 3개의 노드로 구성된 원형 연결 리스트를 보여줍니다.
여기에서 각 노드가 자체적으로 재추적 가능하다는 것을 알 수 있습니다. 위에 표시된 예는 순환 단일 연결 목록입니다.
참고: 가장 간단한 원형 연결 목록은 표시된 것처럼 자신만 추적하는 노드입니다.
Basic Opera순환 연결 목록의 옵션
원형 연결 리스트의 기본 연산은 다음과 같습니다.
- 삽입
- 삭제 및
- 순회
- 삽입은 순환 연결 리스트의 특정 위치에 노드를 배치하는 프로세스입니다.
- 삭제는 연결된 목록에서 기존 노드를 제거하는 프로세스입니다. 노드는 해당 값의 발생이나 위치로 식별할 수 있습니다.
- 순환 연결 목록의 순회는 연결 목록 전체의 내용을 표시하고 소스 노드로 다시 추적하는 프로세스입니다.
다음 섹션에서는 노드 삽입과 순환 단일 연결 목록에서 가능한 삽입 유형을 이해합니다.
삽입 Opera기
처음에는 이 이미지에 표시된 대로 자신을 가리키는 하나의 노드를 만들어야 합니다. 이 노드가 없으면 삽입 시 첫 번째 노드가 생성됩니다.
다음으로 두 가지 가능성이 있습니다.
- 순환 연결 리스트의 현재 위치에 삽입합니다. 이는 일반 단일 연결 목록의 끝 부분에 삽입하는 것과 같습니다. 순환 연결 리스트에서는 시작과 끝이 동일합니다.
- 색인화된 노드 뒤에 삽입합니다. 노드는 해당 요소 값에 해당하는 인덱스 번호로 식별되어야 합니다.
순환 연결 리스트의 시작/끝, 즉 처음으로 노드가 추가된 위치에 삽입하려면,
- 기존 노드에 대한 기존 자체 링크를 끊어야 합니다.
- 새 노드의 다음 포인터는 기존 노드에 연결됩니다.
- 마지막 노드의 다음 포인터는 삽입된 노드를 가리킵니다.
참고: 토큰 마스터인 포인터 또는 원의 시작/끝은 변경될 수 있습니다. 앞서 설명한 대로 순회 시 동일한 노드로 계속 돌아갑니다.
(a) i-iii의 단계는 다음과 같습니다.
(기존 노드)
1 단계) 기존 링크 끊기
2 단계) 정방향 링크 생성(새 노드에서 기존 노드로)
3 단계) 첫 번째 노드에 대한 루프 링크 생성
다음으로 노드 뒤에 삽입을 시도합니다.
예를 들어 'VALUE2'이 있는 노드 뒤에 'VALUE0'를 삽입해 보겠습니다. 시작점이 "VALUE0"인 노드라고 가정하겠습니다.
- 첫 번째 노드와 두 번째 노드 사이의 줄을 끊고 그 사이에 'VALUE2'가 있는 노드를 배치해야 합니다.
- 첫 번째 노드의 다음 포인터는 이 노드에 연결되어야 하며, 이 노드의 다음 포인터는 이전 두 번째 노드에 연결되어야 합니다.
- 나머지 배열은 변경되지 않습니다. 모든 노드는 자체적으로 재추적 가능합니다.
참고: 순환 배열이 있으므로 노드를 삽입하려면 모든 노드에 대해 동일한 절차가 필요합니다. 사이클을 완료하는 포인터는 다른 노드와 마찬가지로 사이클을 완료합니다.
이는 아래와 같습니다.
(노드가 XNUMX개만 있다고 가정해 보겠습니다. 이는 사소한 경우입니다.)
1 단계) 연결된 노드 사이의 내부 링크를 제거합니다.
2 단계) 왼쪽 노드를 새 노드에 연결
3 단계) 새 노드를 오른쪽 노드에 연결합니다.
삭제 Opera기
3노드 순환 연결 리스트를 가정해 보겠습니다. 삭제사례는 아래와 같습니다.
- 현재 요소 삭제
- 요소 이후 삭제.
시작/끝 삭제:
- 마지막 노드에서 첫 번째 노드로 이동합니다.
- 끝에서 삭제하려면 마지막 노드에서 첫 번째 노드까지 순회 단계가 하나만 있어야 합니다.
- 마지막 노드와 다음 노드 사이의 링크를 삭제합니다.
- 마지막 노드를 첫 번째 노드의 다음 요소에 연결합니다.
- 첫 번째 노드를 해제합니다.
(기존 설정)
STEP 1) 순환 링크를 제거하십시오.
2단계) 첫 번째와 다음 노드 사이의 링크를 제거하고 마지막 노드를 첫 번째 노드 다음 노드에 연결합니다.
3 단계) 첫 번째 노드 해제/할당 취소
노드 삭제:
- 다음 노드가 삭제될 노드가 될 때까지 순회합니다.
- 다음 노드로 이동하여 이전 노드에 포인터를 놓습니다.
- 다음 포인터를 사용하여 이전 노드를 현재 노드 뒤의 노드에 연결합니다.
- 현재(링크 해제된) 노드를 해제합니다.
1 단계) 'VALUE1'이 있는 노드를 삭제해야 한다고 가정해 보겠습니다.
2 단계) 이전 노드와 현재 노드 사이의 링크를 제거합니다. 이전 노드를 현재 노드(VALUE1)가 가리키는 다음 노드와 연결합니다.
3 단계) 현재 노드를 해제하거나 할당을 취소합니다.
순환 연결 목록 순회
원형 연결 리스트를 탐색하려면 마지막 포인터에서 시작하여 마지막 포인터 자체가 NULL인지 확인합니다. 이 조건이 거짓이면 요소가 하나만 있는지 확인합니다. 그렇지 않으면 아래 GIF에 표시된 대로 마지막 포인터에 다시 도달할 때까지 임시 포인터를 사용하여 탐색하거나 필요한 만큼 탐색합니다.
순환 연결 리스트의 장점
순환 연결 목록의 장점 중 일부는 다음과 같습니다.
- 코드에 NULL 할당이 필요하지 않습니다. 순환 목록은 완전히 할당이 해제되지 않는 한 NULL 포인터를 가리키지 않습니다.
- 원형 연결 리스트는 시작과 끝이 일치하기 때문에 끝 작업에 유리합니다. Algorithms 예를 들어 라운드 로빈 스케줄링은 댕글링 또는 NULL 참조 포인터를 만나지 않고 순환 방식으로 대기열에 있는 프로세스를 깔끔하게 제거할 수 있습니다.
- 순환 연결 목록은 단일 연결 목록의 모든 일반 기능도 수행합니다. 실제로는 원형 이중 연결 리스트 아래에 설명된 방법을 사용하면 요소를 찾기 위해 전체 길이 순회가 필요하지 않을 수도 있습니다. 해당 요소는 기껏해야 시작 부분과 정반대에 있을 뿐이며 연결 목록의 절반만 완료합니다.
순환 연결 목록의 단점
순환 연결 리스트를 사용할 때의 단점은 다음과 같습니다.
- 원형 목록은 다음과 같은 경우에 복잡합니다. 단일 연결 리스트.
- Rev순환 목록은 단일 또는 이중 목록에 비해 복잡합니다.
- 주의 깊게 처리하지 않으면 코드가 무한 루프에 빠질 수 있습니다.
- 목록 및 루프 제어의 끝을 찾는 것이 더 어렵습니다.
- 시작 부분에 삽입하면 마지막 노드를 찾기 위해 전체 목록을 탐색해야 합니다. (구현 관점)
순환 연결 리스트로서의 단일 연결 리스트
아래 코드를 읽고 구현해 보시기 바랍니다. 순환 연결 목록과 관련된 포인터 연산을 제공합니다.
#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()
{
...
코드 설명:
- 코드의 처음 두 줄은 필요한 포함 헤더 파일입니다.
- 다음 섹션에서는 각 자체 참조 노드의 구조를 설명합니다. 여기에는 구조체와 동일한 유형의 값과 포인터가 포함됩니다.
- 각 구조는 동일한 유형의 구조 객체에 반복적으로 연결됩니다.
- 다음과 같은 다양한 기능 프로토타입이 있습니다.
- 빈 연결리스트에 요소 추가하기
- 에 삽입 현재 지적되고 있는 순환 연결 리스트의 위치
- 특정 뒤에 삽입 색인 연결리스트의 값
- 특정 이후 제거/삭제 색인 연결리스트의 값
- 순환 연결 리스트의 현재 가리키는 위치에서 제거
- 마지막 함수는 연결된 목록의 모든 상태에서 순환 순회를 통해 각 요소를 인쇄합니다.
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)
코드 설명:
- addEmpty 코드의 경우 malloc 함수를 사용하여 빈 노드를 할당합니다.
- 이 노드의 경우 데이터를 임시 변수에 배치합니다.
- 유일한 변수를 임시 변수에 할당하고 연결합니다.
- 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;
…
코드 설명
- 삽입할 요소가 없으면 빈 목록에 추가하고 컨트롤을 반환해야 합니다.
- 현재 요소 뒤에 배치할 임시 요소를 만듭니다.
- 그림과 같이 포인터를 연결합니다.
- 이전 함수와 마찬가지로 마지막 포인터를 반환합니다.
...
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");
...
코드 설명:
- 목록에 요소가 없으면 데이터를 무시하고 현재 항목을 목록의 마지막 항목으로 추가하고 컨트롤을 반환합니다.
- do-while 루프의 모든 반복에 대해 마지막으로 탐색한 결과를 보유하는 이전 포인터가 있는지 확인하십시오.
- 그래야만 다음 순회가 발생할 수 있습니다.
- 데이터가 발견되거나 temp가 마지막 포인터에 다시 도달하면 do-while이 종료됩니다. 코드의 다음 섹션에서는 항목으로 수행해야 할 작업을 결정합니다.
...
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)
...
코드 설명:
- 전체 목록을 탐색했지만 항목을 찾을 수 없으면 "항목을 찾을 수 없음" 메시지를 표시한 다음 호출자에게 제어권을 반환합니다.
- 발견된 노드가 있거나 해당 노드가 아직 마지막 노드가 아닌 경우 새 노드를 만듭니다.
- (링크) 이전 노드를 새 노드로 만듭니다. 현재 노드를 temp(순회 변수)와 연결합니다.
- 이렇게 하면 요소가 순환 연결 목록의 특정 노드 뒤에 배치됩니다. 발신자에게 돌아갑니다.
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)
코드 설명
- 마지막(현재) 노드만 제거하려면 이 목록이 비어 있는지 확인하세요. 그렇다면 요소를 제거할 수 없습니다.
- 임시 변수는 한 링크 앞으로 이동합니다.
- 마지막 포인터를 첫 번째 포인터 뒤의 포인터에 연결합니다.
- 임시 포인터를 해제합니다. 연결되지 않은 마지막 포인터의 할당을 해제합니다.
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");
...
코드 설명
- 이전 제거 기능과 마찬가지로 요소가 없는지 확인합니다. 이것이 사실이라면 어떤 요소도 제거할 수 없습니다.
- 포인터 삭제할 요소를 찾을 수 있는 특정 위치가 할당됩니다.
- 포인터는 한 단계씩 발전합니다. (온도보다 이전)
- 요소를 찾을 때까지 프로세스가 계속되거나 다음 요소가 마지막 포인터로 되돌아갑니다.
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;
프로그램 설명
- 연결 리스트 전체를 탐색한 후에 해당 요소를 찾은 경우, 해당 항목을 찾을 수 없다는 오류 메시지가 표시됩니다.
- 그렇지 않으면, 해당 요소는 3단계와 4단계에서 연결 해제되고 해제됩니다.
- 이전 포인터는 삭제할 요소(temp)가 "다음"으로 가리키는 주소에 연결됩니다.
- 따라서 임시 포인터는 할당 해제되고 해제됩니다.
...
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;
}
}
코드 설명
- 필요한 것이 XNUMX이면 엿보기 또는 순회가 불가능합니다. 사용자가 노드를 할당하거나 삽입해야 합니다.
- 노드가 하나만 있으면 순회할 필요가 없으며 노드의 내용을 인쇄할 수 있으며 while 루프가 실행되지 않습니다.
- 노드가 두 개 이상인 경우 임시는 마지막 요소까지 모든 항목을 인쇄합니다.
- 마지막 요소에 도달하는 순간 루프가 종료되고 함수는 기본 함수에 대한 호출을 반환합니다.
순환 연결 목록의 응용
- 시스템 프로세스에서는 라운드 로빈 스케줄링을 구현하고 고속 그래픽에서는 순환 스케줄링을 구현합니다.
- 컴퓨터 네트워크에서의 토큰 링 스케줄링.
- 이는 지속적인 데이터 탐색이 필요한 상점 게시판과 같은 디스플레이 장치에 사용됩니다.
