Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Playlist Manager

Problem Statement

Write a Java program that simulates a music playlist using a singly linked list. Each node in the list represents a song with a string name. The program should allow users to add songs (insert at the head or tail of the list), remove songs (delete by value, removing the first occurrence), and print the playlist. Test the implementation with various sequences of operations, including adding and removing songs, handling empty playlists, and dealing with duplicate song names. You can visualize this as managing a playlist where songs are added to the beginning or end, removed by name, and displayed as a sequence of song titles.

Input:

  • A sequence of operations, where each operation is:
    • Add at head: Insert a song name at the start of the playlist.
    • Add at tail: Insert a song name at the end of the playlist.
    • Remove: Delete the first occurrence of a song by name.
    • Print: Display the current playlist. Output: For each operation, print the action performed (e.g., "Added song at head", "Removed song", or the playlist as a string). If a song to remove is not found, print an appropriate message. Constraints:
  • The playlist size is between 0 and 10^5.
  • Song names are non-empty strings of length up to 100 characters.
  • The playlist may be empty or contain duplicate song names. Example:
  • Input: Operations = [addHead("Song1"), addTail("Song2"), addHead("Song3"), print, remove("Song2"), print]
  • Output: 
    Added Song1 at head
Added Song2 at tail
Added Song3 at head
Playlist: Song3 Song1 Song2
Removed Song2
Playlist: Song3 Song1
  • Input: Operations = [remove("Song1"), print]
  • Output: 
    Song Song1 not found
Playlist: []

Pseudocode

CLASS Node
    SET song to string
    SET next to Node (null by default)
ENDCLASS

CLASS PlaylistManager
    SET head to null

    FUNCTION addHead(song)
        CREATE newNode as new Node(song)
        SET newNode.next to head
        SET head to newNode
    ENDFUNCTION

    FUNCTION addTail(song)
        CREATE newNode as new Node(song)
        IF head is null THEN
            SET head to newNode
            RETURN
        ENDIF
        SET current to head
        WHILE current.next is not null
            SET current to current.next
        ENDWHILE
        SET current.next to newNode
    ENDFUNCTION

    FUNCTION removeSong(song)
        IF head is null THEN
            RETURN false
        ENDIF
        IF head.song equals song THEN
            SET head to head.next
            RETURN true
        ENDIF
        SET current to head
        WHILE current.next is not null
            IF current.next.song equals song THEN
                SET current.next to current.next.next
                RETURN true
            ENDIF
            SET current to current.next
        ENDWHILE
        RETURN false
    ENDFUNCTION

    FUNCTION toString()
        IF head is null THEN
            RETURN "[]"
        ENDIF
        CREATE result as new StringBuilder
        SET current to head
        WHILE current is not null
            APPEND current.song to result
            IF current.next is not null THEN
                APPEND " " to result
            ENDIF
            SET current to current.next
        ENDWHILE
        RETURN result as string
    ENDFUNCTION
ENDCLASS

FUNCTION testPlaylist(operations)
    CREATE playlist as new PlaylistManager
    FOR each operation in operations
        IF operation.type equals "addHead" THEN
            CALL playlist.addHead(operation.song)
            PRINT added song at head
        ELSE IF operation.type equals "addTail" THEN
            CALL playlist.addTail(operation.song)
            PRINT added song at tail
        ELSE IF operation.type equals "remove" THEN
            IF playlist.removeSong(operation.song) THEN
                PRINT removed song
            ELSE
                PRINT song not found
            ENDIF
        ELSE IF operation.type equals "print" THEN
            PRINT playlist using toString
        ENDIF
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences
    FOR each testCase in testCases
        PRINT test case details
        CALL testPlaylist(testCase)
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a Node class with: a. A string song for the song name. b. A next pointer to the next node.
  2. Define a PlaylistManager class with: a. addHead: Insert a new node with the song at the start. b. addTail: Traverse to the end and append a new node. c. removeSong: Remove the first node with the given song name, return true if found. d. toString: Convert the playlist to a space-separated string.
  3. In testPlaylist: a. Create a PlaylistManager. b. For each operation:
    • Add at head: Call addHead, print action.
    • Add at tail: Call addTail, print action.
    • Remove: Call removeSong, print success or failure.
    • Print: Call toString, print playlist.
  4. In main, test with sequences including adds, removes, empty playlists, and duplicates.

Java Implementation

import java.util.*;

public class PlaylistManager {
    // Node class for the linked list
    static class Node {
        String song;
        Node next;

        Node(String song) {
            this.song = song;
            this.next = null;
        }
    }

    // PlaylistManager class to manage songs
    static class Playlist {
        private Node head;

        public void addHead(String song) {
            Node newNode = new Node(song);
            newNode.next = head;
            head = newNode;
        }

        public void addTail(String song) {
            Node newNode = new Node(song);
            if (head == null) {
                head = newNode;
                return;
            }
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }

        public boolean removeSong(String song) {
            if (head == null) {
                return false;
            }
            if (head.song.equals(song)) {
                head = head.next;
                return true;
            }
            Node current = head;
            while (current.next != null) {
                if (current.next.song.equals(song)) {
                    current.next = current.next.next;
                    return true;
                }
                current = current.next;
            }
            return false;
        }

        public String toString() {
            if (head == null) {
                return "[]";
            }
            StringBuilder result = new StringBuilder();
            Node current = head;
            while (current != null) {
                result.append(current.song);
                if (current.next != null) {
                    result.append(" ");
                }
                current = current.next;
            }
            return result.toString();
        }
    }

    // Helper class for operations
    static class Operation {
        String type;
        String song;

        Operation(String type, String song) {
            this.type = type;
            this.song = song;
        }
    }

    // Tests playlist operations
    public void testPlaylist(List<Operation> operations) {
        Playlist playlist = new Playlist();
        for (Operation op : operations) {
            if (op.type.equals("addHead")) {
                playlist.addHead(op.song);
                System.out.println("Added " + op.song + " at head");
            } else if (op.type.equals("addTail")) {
                playlist.addTail(op.song);
                System.out.println("Added " + op.song + " at tail");
            } else if (op.type.equals("remove")) {
                if (playlist.removeSong(op.song)) {
                    System.out.println("Removed " + op.song);
                } else {
                    System.out.println("Song " + op.song + " not found");
                }
            } else if (op.type.equals("print")) {
                System.out.println("Playlist: " + playlist.toString());
            }
        }
    }

    // Main method to test playlist manager
    public static void main(String[] args) {
        PlaylistManager manager = new PlaylistManager();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal operations
        testCases.add(Arrays.asList(
            new Operation("addHead", "Song1"),
            new Operation("addTail", "Song2"),
            new Operation("addHead", "Song3"),
            new Operation("print", null),
            new Operation("remove", "Song2"),
            new Operation("print", null)
        ));
        
        // Test case 2: Empty playlist
        testCases.add(Arrays.asList(
            new Operation("remove", "Song1"),
            new Operation("print", null)
        ));
        
        // Test case 3: Single song
        testCases.add(Arrays.asList(
            new Operation("addHead", "Song1"),
            new Operation("print", null),
            new Operation("remove", "Song1"),
            new Operation("print", null)
        ));
        
        // Test case 4: Duplicates
        testCases.add(Arrays.asList(
            new Operation("addHead", "Song1"),
            new Operation("addTail", "Song1"),
            new Operation("addHead", "Song2"),
            new Operation("print", null),
            new Operation("remove", "Song1"),
            new Operation("print", null)
        ));

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            System.out.println("Test case " + (i + 1) + ":");
            manager.testPlaylist(testCases.get(i));
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1:
Added Song1 at head
Added Song2 at tail
Added Song3 at head
Playlist: Song3 Song1 Song2
Removed Song2
Playlist: Song3 Song1

Test case 2:
Song Song1 not found
Playlist: []

Test case 3:
Added Song1 at head
Playlist: Song1
Removed Song1
Playlist: []

Test case 4:
Added Song1 at head
Added Song1 at tail
Added Song2 at head
Playlist: Song2 Song1 Song1
Removed Song1
Playlist: Song2 Song1

Explanation:

  • Test case 1: Adds Song1 (head), Song2 (tail), Song3 (head), prints "Song3 Song1 Song2", removes Song2, prints "Song3 Song1".
  • Test case 2: Attempts to remove Song1 from empty playlist, prints not found, prints "[]".
  • Test case 3: Adds Song1, prints "Song1", removes Song1, prints "[]".
  • Test case 4: Adds Song1 (head), Song1 (tail), Song2 (head), prints "Song2 Song1 Song1", removes first Song1, prints "Song2 Song1".

How It Works

  • Node: Stores a string song name and a next pointer.
  • Playlist:
    • addHead: Inserts new node at the start in O(1).
    • addTail: Traverses to end, appends node in O(n).
    • removeSong: Removes first occurrence of song, returns true if found, O(n).
    • toString: Returns space-separated song names, "[]" for empty.
  • testPlaylist: Executes operations, printing actions and results.
  • Example Trace (Test case 1):
    • addHead("Song1"): head=Song1→null.
    • addTail("Song2"): head=Song1→Song2.
    • addHead("Song3"): head=Song3→Song1→Song2.
    • print: "Song3 Song1 Song2".
    • remove("Song2"): head=Song3→Song1.
    • print: "Song3 Song1".
  • Main Method: Tests normal operations, empty playlist, single song, and duplicates.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Add HeadO(1)O(1)
Add TailO(n)O(1)
Remove SongO(n)O(1)
To StringO(n)O(n)

Note:

  • n is the number of nodes in the playlist.
  • Time complexity: O(1) for addHead; O(n) for addTail and removeSong (traverse list); O(n) for toString (traverse list).
  • Space complexity: O(1) for operations (constant pointers); O(n) for toString (StringBuilder).
  • Worst case: O(n) time, O(n) space for output with large playlists.

✅ Tip: Use a linked list for flexible playlist management, with head insertion for quick additions and tail insertion for appending. Test with duplicates to ensure correct removal of the first occurrence.

⚠ Warning: Handle empty playlist cases to avoid null pointer exceptions. Ensure removal checks all nodes to find the target song.