Circular Linked List Explained — Structure, Operations and Real-World Use Cases

// Demonstrates the node structure and basic circular wiring of a singly circular linked list
public class CircularLinkedListStructure {

    // A single node in our circular linked list
    static class Node {
        int data;
        Node next; // points to the next node — or back to head if this is the tail

        Node(int data) {
            this.data = data;
            this.next = null; // wired up properly after insertion
        }
    }

    public static void main(String[] args) {
        // Create four nodes manually to show the circular wiring clearly
        Node playerOne   = new Node(1);
        Node playerTwo   = new Node(2);
        Node playerThree = new Node(3);
        Node playerFour  = new Node(4);

        // Wire them in sequence
        playerOne.next   = playerTwo;
        playerTwo.next   = playerThree;
        playerThree.next = playerFour;

        // THE KEY LINE: tail points back to head — this is what makes it circular
        playerFour.next  = playerOne;

        // We'll hold a reference to the tail (playerFour) for efficient appending
        Node tail = playerFour;

        // Verify the circle: head is reachable from tail in one hop
        System.out.println("Head data  : " + tail.next.data);       // 1
        System.out.println("Head's next: " + tail.next.next.data);  // 2

        // Confirm it actually circles back
        System.out.println("Is tail.next the head? " + (tail.next == playerOne)); // true

        // Traverse the ring once — stop when we're back at head
        Node current = tail.next; // start at head
        System.out.print("Traversal: ");
        do {
            System.out.print(current.data + " → ");
            current = current.next;
        } while (current != tail.next); // stop condition: we've lapped back to head
        System.out.println("(back to start)");
    }
}

// A circular linked list used to manage player turns in a round-robin card game.
// Players are added, the game cycles through them, and eliminated players are removed.
public class CardGameTurnManager {

    static class PlayerNode {
        String playerName;
        PlayerNode next;

        PlayerNode(String playerName) {
            this.playerName = playerName;
            this.next = null;
        }
    }

    static class CircularPlayerList {
        PlayerNode tail = null; // we track the TAIL for O(1) access to both ends
        int size = 0;

        // --- INSERT AT END (append a new player to the game) ---
        void addPlayer(String name) {
            PlayerNode newPlayer = new PlayerNode(name);

            if (tail == null) {
                // Case 1: empty list — node points to itself
                newPlayer.next = newPlayer;
                tail = newPlayer;
            } else {
                // Case 3: insert at end
                newPlayer.next = tail.next; // new player's next = current head
                tail.next      = newPlayer; // old tail now points to new player
                tail           = newPlayer; // advance tail to the new node
            }
            size++;
        }

        // --- INSERT AT BEGINNING (add a player who joins mid-game, goes first next) ---
        void addPlayerAtFront(String name) {
            PlayerNode newPlayer = new PlayerNode(name);

            if (tail == null) {
                // Same as Case 1 above
                newPlayer.next = newPlayer;
                tail = newPlayer;
            } else {
                // Case 2: new node points to old head, tail points to new node
                newPlayer.next = tail.next; // new node → old head
                tail.next      = newPlayer; // tail → new node (making it the new head)
                // tail itself does NOT move — the new node is the head, not the tail
            }
            size++;
        }

        // --- DELETE A PLAYER (they've been eliminated) ---
        void eliminatePlayer(String name) {
            if (tail == null) {
                System.out.println("No players in game.");
                return;
            }

            PlayerNode current  = tail.next; // start at head
            PlayerNode previous = tail;       // track the node before current

            for (int i = 0; i < size; i++) {
                if (current.playerName.equals(name)) {
                    if (size == 1) {
                        // Only one player — list becomes empty
                        tail = null;
                    } else if (current == tail) {
                        // Deleting the tail — previous becomes the new tail
                        previous.next = tail.next; // previous now points to head
                        tail          = previous;
                    } else {
                        // Deleting a middle or head node
                        // previous skips over current and links to current.next
                        previous.next = current.next;
                    }
                    size--;
                    System.out.println(current.playerName + " has been eliminated.");
                    return;
                }
                previous = current;
                current  = current.next;
            }
            System.out.println(name + " not found in game.");
        }

        // --- PRINT all players in turn order starting from head ---
        void printTurnOrder() {
            if (tail == null) {
                System.out.println("No players.");
                return;
            }
            PlayerNode current = tail.next; // head
            System.out.print("Turn order: ");
            do {
                System.out.print(current.playerName);
                if (current != tail) System.out.print(" → ");
                current = current.next;
            } while (current != tail.next); // one full lap
            System.out.println(" → (loops back)");
        }

        // --- SIMULATE n rounds of turns ---
        void simulateRounds(int numberOfRounds) {
            if (tail == null) return;
            PlayerNode current = tail.next; // start at head
            System.out.println("\n--- Simulating " + numberOfRounds + " turns ---");
            for (int turn = 1; turn <= numberOfRounds; turn++) {
                System.out.println("Turn " + turn + ": " + current.playerName + "'s move");
                current = current.next; // advance to next player, wraps automatically
            }
        }
    }

    public static void main(String[] args) {
        CircularPlayerList game = new CircularPlayerList();

        // Add four players to the card game
        game.addPlayer("Alice");
        game.addPlayer("Bob");
        game.addPlayer("Charlie");
        game.addPlayer("Diana");
        game.printTurnOrder();

        // Simulate 6 turns (wraps around the 4-player circle)
        game.simulateRounds(6);

        // Charlie is eliminated mid-game
        System.out.println();
        game.eliminatePlayer("Charlie");
        game.printTurnOrder();

        // A new player joins at the front
        game.addPlayerAtFront("Eve");
        game.printTurnOrder();
    }
}

// A doubly circular linked list simulating a music player playlist.
// Supports next track, previous track, and adding/removing songs.
public class MusicPlayerPlaylist {

    static class TrackNode {
        String songTitle;
        TrackNode next; // points to the next song in the playlist
        TrackNode prev; // points to the previous song — key addition for doubly circular

        TrackNode(String songTitle) {
            this.songTitle = songTitle;
            this.next = null;
            this.prev = null;
        }
    }

    static class DoublyCircularPlaylist {
        TrackNode head = null;
        int totalTracks = 0;

        void addTrack(String title) {
            TrackNode newTrack = new TrackNode(title);

            if (head == null) {
                // Single node: both next and prev point to itself
                newTrack.next = newTrack;
                newTrack.prev = newTrack;
                head = newTrack;
            } else {
                TrackNode tail = head.prev; // tail is always head.prev in a doubly circular list

                // Wire the new track into the circle
                newTrack.next = head;     // new track → head
                newTrack.prev = tail;     // new track ← tail
                tail.next     = newTrack; // old tail → new track
                head.prev     = newTrack; // head ← new track (new track is now the tail)
            }
            totalTracks++;
        }

        void removeTrack(String title) {
            if (head == null) return;

            TrackNode current = head;
            for (int i = 0; i < totalTracks; i++) {
                if (current.songTitle.equals(title)) {
                    if (totalTracks == 1) {
                        head = null; // playlist is now empty
                    } else {
                        // Bypass the current node in both directions
                        current.prev.next = current.next; // node before skips current
                        current.next.prev = current.prev; // node after skips current
                        if (current == head) {
                            head = current.next; // move head forward if we removed it
                        }
                    }
                    totalTracks--;
                    System.out.println("Removed: " + title);
                    return;
                }
                current = current.next;
            }
            System.out.println(title + " not found in playlist.");
        }

        // Simulate a DJ session: navigate forward and backward through the playlist
        void simulateSession(int[] steps) {
            // steps: positive = next, negative = previous
            if (head == null) return;
            TrackNode current = head;
            System.out.println("\n--- DJ Session ---");
            System.out.println("Now playing: " + current.songTitle);

            for (int step : steps) {
                if (step > 0) {
                    current = current.next; // forward one track, wraps via circular pointer
                    System.out.println(">> Next track : " + current.songTitle);
                } else {
                    current = current.prev; // backward one track — only possible with prev pointer
                    System.out.println("<< Prev track : " + current.songTitle);
                }
            }
        }

        void printPlaylist() {
            if (head == null) { System.out.println("Playlist is empty."); return; }
            TrackNode current = head;
            System.out.print("Playlist: ");
            for (int i = 0; i < totalTracks; i++) {
                System.out.print("[" + current.songTitle + "]");
                if (i < totalTracks - 1) System.out.print(" ⇄ ");
                current = current.next;
            }
            System.out.println(" ⇄ (circular)");
        }
    }

    public static void main(String[] args) {
        DoublyCircularPlaylist playlist = new DoublyCircularPlaylist();

        playlist.addTrack("Bohemian Rhapsody");
        playlist.addTrack("Hotel California");
        playlist.addTrack("Stairway to Heaven");
        playlist.addTrack("Comfortably Numb");
        playlist.printPlaylist();

        // Navigate: forward 2, back 1, forward 3 (wraps around the circle)
        playlist.simulateSession(new int[]{1, 1, -1, 1, 1, 1});

        System.out.println();
        playlist.removeTrack("Hotel California");
        playlist.printPlaylist();
    }
}