linked blocks with arrows pointing in one direction

In a previous post on arrays, I wrote about arrays and how you can listen to them by storing sound. Linked lists are an extension of arrays that instead of just storing elements, they store pointers. Linked lists point to the next node which allow for dynamic memory allocation instead of contiguous memory allocation.

For example, a list of six elements would look like this: 1 -> 2 -> 3 -> 4 -> 5 -> 6.

Thanks for reading Learning Data Structures and Algorithms with Music! Subscribe for free to receive new posts and support my work.

In order to build a linked list data structure, you need a class. In my previous posts on arrays, I was able to create scripts without using a class, but for more complicated data structures that have unique attributes, you need a Python class.

Let’s briefly review what Python classes are and why we need them.

Python classes are the basis of object-oriented programming. In Python, a class is like a blueprint for creating objects to define attributes to store data and methods to perform actions. Classes make your code modular and easier to manage. Here’s the basic structure:

class ClassName:

    def __init__(self, parameter1, parameter2):

        self.attribute1 = parameter1

        self.attribute2 = parameter2

We need a class to create a linked list because we need to define an object that stores a pointer to the next node (we’ll call it “next”) as well the data itself that is stored in the node. This will be the “LinkedList” class:

class ListNode: 
    def __init__(self, val, next): 
        self.value = val 
        

self.next = next

The ListNode class has two attributes:

1. val (or value) - the data stored in this node

2. next - a reference to the next node (or None if it’s the last node)

Cool! So linked lists are data structures that are similar to arrays in that they are an ordered collection of elements, but the main difference is they make use of pointers and they are also used to implement other data structures. Note that I am discussing a singly linked list, which are linked lists with a unidirectional pointers.

Songs are sequential and can be represented as a linked list. Every note can point to the next note in a song. Songs can be represented as linked lists using MIDI notes. You could create a linked list where each node contains a MIDI note and a pointer to the next note. In my next post, I’ll show you how to generate a linked list using MIDI notes.

Thanks for reading Learning Data Structures and Algorithms with Music! Subscribe for free to receive new posts and support my work.