Singly Linked List: 🚀Let's build simple music playlist🎵

Francis Kikulwe — Tue, 16 Jan 2024 09:55:11 +0000

Hello everyone,

I'm excited to share my first technical article with you all! I've always wanted to talk about what I learn in development, and finally, here we are.

In this article, we'll delve into the basics of linked lists, focusing on the simplest form – the singly linked list. If you're wondering what a linked list is, don't worry; I've got you covered!

Understanding Linked List?

Simply, we can say that a linked list is a collection of nodes linked to each other. Think of it as a chain of objects. A node is basically an object containing data and a pointer to the next node in the chain.

There are two main types of linked list:

Singly linked list
Doubly linked list

Now, as I said earlier, our main focus today is on singly as we build a simple music playlist using Java but feel free to re-implement the concept using a programming language of your choice.

Exploring Singly Linked Lists

A singly linked list is a collection of nodes where each node has its data value and the pointer to the next node in the collection. But you might ask what are the advantages of using such a data structure and does it have it have drawbacks. Let's see those in the next section.

Advantages of singly linked list

Dynamic Size:
Singly linked lists can dynamically adjust their size during runtime, making them flexible for scenarios where the number of elements is not known in advance.
Memory Efficiency:
Singly linked lists are memory-efficient as they only require space for the data and a single pointer per node, reducing the overhead compared to other data structures like arrays.
Ease of Insertion and Deletion:
Insertion and deletion operations are more efficient than arrays because, in singly linked lists, adding or removing an element only involves adjusting pointers, without the need to shift or resize the entire structure.
Simple Implementation:
The implementation of singly linked lists is relatively simple and straightforward compared to other complex data structures, making them easier to understand and maintain.

Disadvantages of singly linked list

No Random Access:
Singly linked lists do not support direct access to elements using indices. Traversal from the head is required to reach a specific element, making random access inefficient.
Wasted Memory:
Each node in a singly linked list contains a pointer, which adds overhead and can lead to wasted memory, especially when dealing with a large number of small nodes.
Traversal Overhead:
Traversing the entire list is necessary for various operations, which can result in a higher time complexity for certain tasks compared to data structures that support random access.

Singly Linked List implementation

I thought it is a better idea if we implement a real world application of how we can use singly linked list in our programs. For this case, we are going to build a simple music playlist using the singly linked list data structure in Java programming language.

LinkedList interface
First, we'll start by creating an interface with the necessary methods for performing operations on our linked list.

package com.kiks;

public interface LinkedList <T> {
    public void add(T data);
    public boolean contains(T data);
    public void remove(T data);
    public int size();
    public void displayItems();
}

The interface uses generics so we can be able to reuse our linked list data structure with different data types. For this case, music objects.

As you might have guessed, we'll need to have a Music class so we can create different music objects with your favorite albums, songs, artists etc.

Music class implementation

package com.kiks;

public class Song{
    private String title;
    private String artist;
    private int year;

    public Song(String title, String artist, int year) {
        this.title = title;
        this.artist = artist;
        this.year = year;
    }

    // getters and setters
    public String getTitle() {
        return title;
    }

    public String getArtist() {
        return artist;
    }

    public int getYear() {
        return year;
    }

    public boolean equals(Object o) {
        if (o instanceof Music) {
            Music other = (Music) o;
            return this.title.equals(other.title) && this.artist.equals(other.artist) && this.year == other.year;
        }
        return false;
    }

    public String toString() {
        return title + " by " + artist + " (" + year + ")";
    }
}

The Music class is a simple POJO class with three attributes defining the artist, title and release year of a particular music.

Now, the next thing is to define our singly linked list data structure. Remember that a singly linked list have nodes, so we have to define a basic implementation of the linked list class with nodes.

package com.kiks;

public class SinglyLinkedList<T> implements LinkedList {
    Node head;
    int size;

    public SinglyLinkedList() {
        head = null;
        size = 0;
    }

    @Override
    public void add(T data) { }

    @Override
    public boolean contains(T data) { return false; }

    @Override
    public void remove(T data) { }

    @Override
    public int size() { return 0; }

    @Override
    public void displayItems() { }
}

class Node<T> {
    T data;
    Node next;

    public Node(T data) {
        this.data =  data;
    }
}

Here we have overridden all the methods from the interface and as you can notice that our Singly Linked List constructor initializes the head to a null value and sets the list's size to 0.

Now let's define the methods from the interface starting with the add method:

public void add(T data) {
    // Create a new node with the given data.
    Node newNode = new Node(data);

    // Check if the linked list is empty.
    if (head == null) {
        // If it's empty, set the new node as the head of the list and update the size to 1.
        head = newNode;
        size = 1;
    } else {
        // If the list is not empty, find the last node.
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        // Add the new node to the end of the list and update the size.
        current.next = newNode;
        size++;
    }
}

This add method is used to add a new node with the specified data to the end of a singly linked list. If the list is empty, it sets the new node as the head; otherwise, it traverses the list to find the last node and appends the new node to it.

Next, is the contains method:

public boolean contains(T data) {
    // Check if the linked list is not empty.
    if (head != null) {
        // Start at the head of the list.
        Node current = head;

        // Traverse the list until the last node.
        while (current.next != null) {
            // Check if the current node's data is equal to the specified data.
            if (current.data.equals(data)) {
                // If a match is found, return true.
                return true;
            }

            // Move to the next node in the list.
            current = current.next;
        }
    }

    // If the specified data is not found in the list, return false.
    return false;
}

This contains method is designed to check whether a given piece of data is present in the singly linked list. It iterates through the list and returns true if it finds a node with data matching the specified data, and false otherwise.

Next, let's see the implementation of the remove method:

public void remove(T data) {
    // Check if the linked list is not empty.
    if (head != null) {
        // Check if the node to be removed is the head of the list.
        if (head.data.equals(data)) {
            // If the head contains the specified data, move the head to the next node.
            head = head.next;
            // Decrease the size of the list.
            size--;
        } else {
            // If the node to be removed is not the head, start traversal from the head.
            Node current = head;

            // Traverse the list until the last node.
            while (current.next != null) {
                // Check if the next node contains the specified data.
                if (current.next.data.equals(data)) {
                    // If a match is found, skip the next node by updating pointers.
                    current.next = current.next.next;
                    // Decrease the size of the list.
                    size--;
                    // Exit the method after removing the node.
                    return;
                }

                // Move to the next node in the list.
                current = current.next;
            }
        }
    }
}

This remove method is designed to remove the first occurrence of a specified piece of data from a singly linked list. It adjusts pointers to skip the node containing the specified data while updating the size of the list accordingly.

Finally, the displayItems and size methods:

public int size() {
    // Returns the size of the linked list.
    return size;
}

This size method is a simple getter that returns the current size of the linked list. The size represents the number of nodes in the list and is updated during various operations such as adding and removing nodes. It provides a convenient way to know the size of the linked list from outside the class.

public void displayItems() {
    // Initialize a string to build the output.
    String out = "";

    // Check if the linked list is not empty.
    if (head != null) {
        // Add the header for the display.
        out += "head -> ";

        // Start at the head of the list.
        Node current = head;

        // Traverse the list until the last node.
        while (current.next != null) {
            // Add the data of the current node to the output.
            out += current.data + " -> ";

            // Move to the next node in the list.
            current = current.next;
        }

        // Add the data of the last node and the end marker.
        out += current.data + " -> null.";
    } else {
        // If the list is empty, indicate that in the output.
        out += "The linked list is empty.";
    }

    // Print the final output.
    System.out.println(out);
}

This displayItems method is responsible for printing the contents of the linked list. It constructs a string (out) that represents the visual representation of the linked list and then prints it to the console.

Now we finish the most fun part of this application, our music playlist logic implementation. Over to the main function, write the following code:

package com.kiks;

public class Main {
    public static void main(String[] args) {
        // Create a new instance of the SinglyLinkedList class specialized for Music objects.
        SinglyLinkedList<Music> musicPlaylist = new SinglyLinkedList<>();

        // Add Music objects to the playlist.
        musicPlaylist.add(new Music("Perfect", "Ed Sheeran", 2017));
        musicPlaylist.add(new Music("Baby", "Justin Bieber", 2010));
        musicPlaylist.add(new Music("Despacito", "Luis Fonsi", 2017));
        musicPlaylist.add(new Music("Castle on the Hill", "Ed Sheeran", 2017));

        // Display the contents of the playlist.
        musicPlaylist.displayItems();

        // Print the size of the playlist.
        System.out.println("Playlist size: " + musicPlaylist.size());

        // Check if the playlist contains a specific song.
        System.out.println("Playlist contains \"Baby\": " + musicPlaylist.contains(new Music("Baby", "Justin Bieber", 2010)));

        // Remove a specific song from the playlist.
        musicPlaylist.remove(new Music("Baby", "Justin Bieber", 2010));

        // Check again if the playlist contains the removed song.
        System.out.println("Playlist contains \"Baby\": " + musicPlaylist.contains(new Music("Baby", "Justin Bieber", 2010)));
    }
}

This Main class provides a practical example of using a singly linked list to manage a playlist of music. It demonstrates basic operations such as adding, displaying, and removing songs from the playlist.

In conclusion, we've explored the fundamentals of singly linked lists and even applied our knowledge to create a simple music playlist in Java. Linked lists offer dynamic and memory-efficient solutions, but their lack of random access and potential traversal overhead are important considerations.

Remember, the implementation and usage of data structures depend on specific needs and scenarios. With this foundation, feel free to explore and adapt these concepts to your programming adventures!