"Circular Linked List"(단일 또는 이중) 데이터 구조가 필요한 이유는 무엇입니까?

"Circular Linked List"(단일 또는 이중) 데이터 구조가 필요한 이유는 무엇입니까?

"Circular Linked List"(단일 또는 이중) 데이터 구조가 필요한 이유는 무엇입니까?

단순한 링크 리스트(단일 또는 이중)로 해결할 수 있는 문제는 무엇입니까?

간단한 예는 멀티플레이어 보드게임에서 누구 차례인지 추적하는 것이다.모든 플레이어를 원형 연결 목록에 넣습니다.플레이어의 차례가 되면, 리스트의 다음의 플레이어로 넘어갑니다.이로 인해 프로그램 주기가 플레이어 간에 무기한으로 반복됩니다.

순환 링크 리스트를 이동하려면 첫 번째 요소에 포인터를 저장합니다.해당 요소가 다시 표시되었을 때 목록 전체를 통과한 것입니다.

void traverse(CircularList *c) {
  if (is_empty(c)) {
    return;
  }
  CircularList start = c;
  do {
    operateOnNode(c);
    c = c->next;
  } while(c != start);
}

사용하는 이유는 다음 두 가지입니다.

1) 일부 문제 영역은 본질적으로 순환형입니다.

예를 들어, 모노폴리 보드의 정사각형을 원형으로 연결된 목록으로 표현하여 고유한 구조에 매핑할 수 있습니다.

2) 효율화를 위해 일부 솔루션을 순환 링크 목록에 매핑할 수 있습니다.

예를 들어, 지터 버퍼는 (예를 들어) 비디오 또는 오디오플레이어가 순서대로 재생할 수 있도록 네트워크로부터 번호부 패킷을 가져와 순서대로 배치하는 버퍼의 일종입니다.속도가 너무 느린(지연성이 높은) 패킷은 폐기됩니다.

슬롯이 재생되면 다시 사용할 수 있기 때문에 메모리 할당 및 할당 해제 없이 순환 버퍼로 나타낼 수 있습니다.

링크드 리스트를 사용하여 구현할 수 있지만 (가격이 저렴한) 상수를 대체하는 것이 아니라 목록에 지속적으로 추가 및 삭제가 있을 것이다.

구글에서 찾은 거.

단일 링크 순환 목록은 목록의 마지막 노드가 목록의 첫 번째 노드를 가리키는 링크된 목록입니다.순환 목록에는 NULL 포인터가 포함되어 있지 않습니다.

순환 링크 리스트를 사용해야 하는 어플리케이션의 좋은 예는 운영체제에 의해 해결된 시분할 문제입니다.

시분할 환경에서는 운영체제는 현재 사용자의 목록을 유지하고 각 사용자가 한 번에 한 명의 사용자씩 CPU 시간을 조금씩 사용할 수 있도록 해야 합니다.operating system은, 유저를 선택해, 소량의 CPU 시간을 사용하게 한 후, 다음의 유저에게 넘어갑니다.

이 어플리케이션에서는 CPU 시간을 요구하는 사람이 전혀 없는 한 NULL 포인터는 존재하지 않습니다.

적용들

할 수 . 1) 엔트리가회전하는 어플리케이션입니다.
2) 로빈 알고리즘의 입니다.2) 라운드 로빈 스케줄링의 순환 링크 리스트.

원형 링크 리스트를 효과적으로 사용하여 큐(FIFO) 또는 디큐(전면 및 후면에서 효율적으로 삽입 및 제거)를 작성할 수 있습니다.http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked 를 참조해 주세요.

순환 링크 목록은 태스크를 반복해야 하는 응용 프로그램이나 시간 공유 응용 프로그램에서 널리 사용됩니다.순환 큐는 수행된 태스크와 수행해야 하는 태스크를 추적할 수 있습니다. 특정 태스크가 완료되면 다음 태스크로 이동하고 전체 태스크 세트가 완료되면 다시 첫 번째 태스크로 이동하여 나머지 작업을 완료합니다.실제 사용: 시스템에서 여러 애플리케이션을 열면 해당 애플리케이션의 메모리가 원형으로 저장됩니다. 응용 프로그램 전환 시 win+tab/alt+tab을 계속 누르면 이를 확인할 수 있습니다.또한 멀티플레이어 보드게임에서는 각 플레이어는 링크 리스트의 노드에 할당되어 로테이션이 이루어집니다.

순환 링크 리스트(단일 또는 이중)는 각 노드를 균등하게 방문해야 하며 목록이 증가할 수 있는 애플리케이션에 유용합니다.리스트의 사이즈가 고정되어 있는 경우는, 순환 큐를 사용하는 것이 훨씬 효율적입니다(속도와 메모리).

순환 링크 리스트를 사용해야 하는 어플리케이션의 좋은 예는 운영체제에 의해 해결된 시분할 문제입니다.

순환 리스트는 일반적인 이중 링크 리스트보다 단순합니다.Adpend는 앞에 한 번 붙이고 앞으로 한 번 이동하며 Pop back은 뒤로 한 번 이동하고 앞쪽으로 이동하면 됩니다.양끝을 함께 연결하면 단일 끝 목록의 운영 구현 비용으로 이중 끝 목록을 얻을 수 있습니다.

자원 풀링에서는 순환 링크 리스트를 사용할 수 있습니다.많은 사용자가 공유 리소스를 사용하는 경우 순환 링크 목록을 사용하여 해당 리소스를 할당할 수 있습니다.

언급URL : https://stackoverflow.com/questions/3589772/why-exactly-do-we-need-a-circular-linked-list-singly-or-doubly-data-structur