In the last blog, Linked List, we made a simple music playlist using a Linked List. What if we want a better solution that does not require traveling through the nodes to play the next or previous song? Also, seriously, the code was not that good. It did not follow the coding principles and was not very readable. In this blog, I will modify the old code and make it a lot better. The answer is a doubly linked list. The user can play the next or previous songs. So I had to use a data structure that can support both forward and backward traversal.

What is a Doubly Linked List

The doubly linked list is a data structure that is similar to a linked list, but it has two pointers. One pointer refers to the previous element, and the other one refers to the next element in the list. Like a linked list, it has a head, which is the first element, but the previous pointer in the head node is always null. The main advantage of a doubly linked list is two-way traversal.

Some Basic Concepts

1. Node: The element of the Linked List that stores the data and pointer(s)

2. Head: The first element in the Linked List

3. Tail: The last element in the Linked List

4. Data: The value that a node contains

5. Pointer: Node’s attribute that points to either another Node or is null.

6. If there is only one node in the Linked List, then all the pointers have a null reference

Doubly Linked List Code

To implement a doubly linked list, you need a Node class and a LinkedList class. We will use dependency injection to add nodes to the linked list. This will make the Node and LinkedList classes loosely coupled.

class Node:
    def __init__(self, data: int):
        self.prev = None
        self.data = data
        self.next = None 

class DoublyLinkedList:
    def __init__(self):
        self.head: Node | None = None
        self.tail: Node | None = None

    def add_node(self, node: Node):
        if not self.head:
            self.head = self.tail = node
            return

        node.prev = self.tail
        self.tail.next = node
        self.tail = self.tail.next

    def backward(self):
        current = self.tail
        while current:
            print(current.data)
            current = current.prev

    def forward(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

Test Code:

dl = DoublyLinkedList()

for i in range(5):
    node = Node(data=i)
    dl.add_node(node)

print('Print data in backward')
dl.backward()
print('Print data in forward')
dl.forward()

Doubly Linked List for Music Playlist

Changing the singly linked list to doubly linked list has made the code significantly better. It is more readable and efficient. In order to change music, there is no need to travel through the node. Also, a new attribute is added to the Linked List class, current.

models.py

from pydantic import BaseModel
from typing import Self

class Music(BaseModel):
    """Music class represent individual music object in songs.json"""
    id: int
    name: str


class Node(BaseModel):
    """Node used to implement DoublyLinkedList"""
    prev: Self | None = None
    music: Music
    next: Self | None = None


class MusicId(BaseModel):
    """Payload for add_to_playlist and play_music views"""
    music_id: int

linkedlist.py

from models import Node, Music
from fastapi import HTTPException
from typing import List

class DoublyLinkedList:
    """DoublyLinkedlist stores music playlist"""
    def __init__(self):
        self.head: Node | None = None
        self.tail: Node | None = None
        self.current: Node | None = None


    def music_in_playlist(self, id: int) -> bool:
        """Check if music id exists in playlist"""
        current = self.head
        while current is not None:
            if current.music.id == id:
                return current
            current = current.next  
        return False


    def play_music(self, id: int):
        if not self.head:
            raise HTTPException(status_code=400, detail='No music in playlist')

        if not (node := self.music_in_playlist(id)):
            raise HTTPException(status_code=400, detail='Music is not in playlist')

        self.current = node

    def get_playlist(self) -> List[Music]:
        """Returns a list of music objects generated by traversing playlist"""
        music_list: List[Music] = []

        current = self.head
        while current:
            music_list.append(current.music)  
            current = current.next  
        return music_list


    def add_music(self, node: Node) -> List[Music]:
        """Adds a music object in playlist"""
        if self.music_in_playlist(node.music.id):
            raise HTTPException(status_code=400, detail="Music already in playlist")

        if self.head is None:
            self.head = self.tail = self.current = node
            return self.get_playlist()

        self.tail.next = node
        node.prev = self.tail
        self.tail = self.tail.next
        return self.get_playlist()

    def play_next(self):
        """Play music stored in next node"""
        if not self.current:
            raise HTTPException(status_code=400, detail='No music is playing')

        if not self.head:
            raise HTTPException(status_code=400, detail='No music in playlist')

        if not self.head.next:
            raise HTTPException(status_code=400, detail='Only one music in playlist')

        if self.current.next:
            self.current = self.current.next      


    def play_previous(self):
        """Play music stored in previous node"""
        if not self.current:
            raise HTTPException(status_code=400, detail='No music is playing')

        if not self.head:
            raise HTTPException(status_code=400, detail='No music in playlist')

        if not self.head.next:
            raise HTTPException(status_code=400, detail='Only one music in playlist')

        if self.current.prev: 
            self.current = self.current.prev

playlist: DoublyLinkedList = DoublyLinkedList()

router.py

Instead of managing the currently playing song through a global variable, it is managed within the playlist object. This made the code a lot more clutter-free.

from fastapi import APIRouter, Depends
from models import Node, Music, MusicId
from typing import Annotated, List
from db import music_db
from linkedlist import playlist


music_router = APIRouter()


@music_router.get('/music-list')
def music_list(db: Annotated[List[Music], Depends(music_db)]):
    return db


@music_router.post('/add-to-playlist')
def add_to_playlist(body: MusicId, db: Annotated[List[Music], Depends(music_db)]):
    music_id: int = body.music_id
    music: Music = Music(**list(filter(lambda x: x["id"] == music_id, db))[0])
    node: Node = Node(music=music)
    return {
        'playlist': playlist.add_music(node),
        'current': playlist.current.music
    }


@music_router.post('/play-music')
def play_music(body: MusicId, db: Annotated[List[Music], Depends(music_db)]):
    playlist.play_music(body.music_id)
    return {
        'playlist': playlist.get_playlist(),
        'current': playlist.current.music
    }


@music_router.get('/current-music-playing')
def current_music_playing():
    return {
        'current': playlist.current.music
    }


@music_router.get('/play-next')
def play_next():
    playlist.play_next()
    return {
        'current': playlist.current.music
    }


@music_router.get('/play-previous')
def play_previous():
    playlist.play_previous()
    return {
        'current': playlist.current.music
    }


@music_router.get('/playlist')
def get_current_playlist():
    return playlist.get_playlist()

Git Hub Link

https://github.com/ritwikmath/music-stream-backend-linkedlist-demo