#circular linked list

Circular Linked List || Insertion at the End | Dronacharya College of Engineering, Gurugram

The Josephus Problem is presented in the sources as a classic mathematical and computer science problem. It is often discussed in the context of data structures, particularly linked lists, due to its circular nature.

Here's a detailed discussion of the Josephus Problem based on the sources:

• Problem Scenario and Core Challenge

    ◦ The problem describes a situation where 'n' people are standing in a circle, numbered from 1 to 'n'.

    ◦ Starting from person number 1 and moving in a clockwise direction, every second living person is eliminated (killed).

    ◦ This process continues until only one person remains.

    ◦ The core challenge of the Josephus problem is to determine the position (number) of the last person remaining. Josephus himself was one of 41 Jews trapped in a cave by Romans and, deciding to commit suicide instead of surrendering, calculated his position to be the last survivor.

• Illustrative Examples of Elimination Sequence The sources provide examples of the elimination sequence for specific values of 'n':

    ◦ For n = 5: The sequence of people eliminated leads to 3 being the last survivor. The steps are: (1, 2, 3, 4, 5) -> (1, 3, 4, 5) -> (1, 3, 5) -> (3, 5) -> (3).

    ◦ For n = 6: The sequence of eliminations leads to 5 being the last survivor. The steps are: (1, 2, 3, 4, 5, 6) -> (1, 3, 4, 5, 6) -> (1, 3, 5, 6) -> (1, 3, 5) -> (1, 5) -> (5).

• Mathematical Solutions The sources present two methods to solve the Josephus Problem:

    1. Recursive Relation: The problem can be defined by a recursive relationship, f(n):

        ▪ Base Case: If there is only one person, f(1) = 1.

        ▪ Recursive Step for even 'n': If n is an even number, f(n) = 2f(n/2) - 1.

        ▪ Recursive Step for odd 'n': If n is an odd number, f(n) = 2f((n-1)/2) + 1.

An example calculation for f(10) is provided using this relation:

        ▪ f(1) = 1

        ▪ f(2) = 2 * f(1) - 1 = 2 * 1 - 1 = 1

        ▪ f(5) = 2 * f((5-1)/2) + 1 = 2 * f(2) + 1 = 2 * 1 + 1 = 3

        ▪ f(10) = 2 * f(10/2) - 1 = 2 * f(5) - 1 = 2 * 3 - 1 = 5.

    2. Direct Formula: A direct formula provides a more efficient way to find the solution:

        ▪ The formula is f(n) = 2(n - k) + 1.

        ▪ Here, k is defined as the largest power of 2 that is less than or equal to 'n' (k = 2^floor(log2(n))).

        ▪ For example, to calculate f(10) using this method: n = 10. The largest power of 2 less than or equal to 10 is k = 8 (since 2^3 = 8).

        ▪ Substituting these values into the formula: f(10) = 2 * (10 - 8) + 1 = 2 * 2 + 1 = 5.

        ▪ Another example for n = 1000 is given: k = 512 (the largest power of 2 less than 1000). The result would be 2 * (1000 - 512) + 1 = 977.

int f (L) { if (L -> next == L) return L -> data; L -> next = L -> next -> next; return f (L -> next); }

The int f(L) function simulates the process of the Josephus Problem using a circular linked list. The Josephus Problem involves 'n' people in a circle, where every second person is eliminated until only one remains, and the goal is to find the position of the last survivor.

Here's a detailed explanation of the function's behavior:

• Function Signature and Input:

    ◦ The function int f(L) takes a parameter L, which is presumed to be a pointer to a node in a circular linked list. In the context of the Josephus Problem, L represents a person in the circle.

• Base Case (Termination Condition):

    ◦ if (L -> next == L): This is the base case for the recursion. In a circular linked list, if a node's next pointer points back to itself, it means that this node is the only node remaining in the circle.

    ◦ return L -> data;: When the base case is met, the function returns the data stored in that last remaining node. This data represents the "position" or "number" of the last survivor in the Josephus Problem.

• Recursive Step (Elimination Process):

    ◦ L -> next = L -> next -> next;: This is the core operation that simulates the elimination of a person from the circle.

        ▪ L -> next refers to the node immediately following the current node L.

        ▪ L -> next -> next refers to the node after the one immediately following L.

        ▪ By setting L -> next = L -> next -> next;, the node that was originally at L -> next is effectively skipped or "removed" from the circular linked list. The current node L now directly points to the node that was two steps ahead, simulating the elimination of the "second living person" (the one L was originally pointing to) as described in the Josephus Problem.

환형 링크드 리스트(Circular Linked List)

환형 링크드 리스트(Circular Linked List) 머리가 꼬리를 문다! 여태까지 단순 연결 리스트, 이중 연결 리스트에 대해 알아봤습니다. 이번에는 원형 연결 리스트(Circular Linked List)에 대해 알아보도록 하겠습니다. 원형 연결 리스트의 특징은 머리와 꼬리가 연결되어 순환(Circular) 구조를 지닙니다. 즉, 꼬리(Tail, 테일) 노드의 다음 노드는 머리(Head, 헤드) 노드를 가리킵니다. 여기서는 환형 더블 링크드 리스트가 아닌 환형 싱글 링크드 리스트 기준으로 다루도록 하겠습니다. 환형 싱글 링크드 리스트는 싱글 링크드 리스트에서 헤드와 테일을 연결한 것입니다. 환형 링크드 리스트(Circular Linked List) 위의 그림을 보면 알 수 있듯이, 원형…

Creating Circular Linked List in C (in English)

http://www.knowsh.com Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop. http://knowsh.com/Notes/160274/Detect-If-Linked-List-Has-A-Loop