thank u, next: an introduction to linked lists

In this post, we are going to be talking about the linked list data structure in the language of "thank u, next" by Ariana Grande. If you haven't watched the piece of art that is the music video for the song, please pause and do so before we begin.

Linked lists are linear collections of data that consist of nodes with data and pointers. We're going to be focusing on singly linked lists, which contain nodes that store the value of the node and a pointer to the next node. There are also other types of linked lists, like doubly linked lists and cyclical linked lists, but we'll focus on singly linked ones for now.

A couple quick definitions so we make sure we're on the same page:

• A pointer stores the address of a value in memory. These can also point to nothing. A reference is similar, though can't point to nothing.
• A Data Structure is a collection of data that can be implemented in any programming language.

We're going to be using the following linked list in this post:

In the above diagram, we see five different nodes, and each has a data value. The first four are in the order which she lists her exes:

Thought I'd end up with Sean
But he wasn't a match
Wrote some songs about Ricky
Now I listen and laugh
Even almost got married
And for Pete, I'm so thankful
Wish I could say, "Thank you" to Malcolm
'Cause he was an angel

The last one is Ari herself:

Plus, I met someone else
We havin' better discussions
I know they say I move on too fast
But this one gon' last
'Cause her name is Ari
And I'm so good with that (so good with that)

In addition to the data, each node stores a pointer to the next node. She always sings about her exes in the same order, and then herself last. When we iterate through a linked list, the same order will apply. We will start at the head node, which is the first one in the linked list, then move to the next one and so on. For the singly linked list, we won't move in reverse order or jump randomly from node to node, rather we'll go in the same order from head to the end.

We can create a super simple linked list by creating nodes and linking nodes in the following way:

class Node {
    constructor(data, next=null) {
        this.data = data
        this.next = next
    }
}

let ari = new Node('Ari')
let malcolm = new Node('Malcolm', ari)
let pete = new Node('Pete', malcolm)
let ricky = new Node('Ricky', pete)
let sean = new Node('Sean', ricky)

The final code for this post is also in Python here

If we print out what the Sean node looks like, we can see that it stores his name as the data attribute as well as a reference to the next node, which is Ricky. We can traverse all the nodes by using the next attribute!

Also, at the end of the linked list, there is a null pointer. In this case, since Ari is the queen, she's good by herself and doesn't need to move on to her next significant other. So, no thank u, next for her node.

Linked lists have some benefits compared to arrays, which are their main alternative in the world of linear data structures. Arrays are traditionally stored in a contiguous block in memory, which allows us to use the speedy indexing formula start_of_array_in_memory + space_allocated_for_each_array_item * index_of_item_we_want. While it's super efficient (O(1)) to get an item at an index, it's less efficient to insert or delete items from the array -- we would need to move everything to a different block in memory. It's not guaranteed that there's space before or after that array to insert the new item. If you insert or delete in the middle, the same logic applies -- you would have to move the items around in memory to fill holes or allocate more space.

Unlike arrays, linked lists do not need to be stored in one contiguous (or side to side 😉) block in memory which makes insertion and deletion at the beginning of the linked list easier. The pointers can point to any location in memory, so you don't have to move all the data around to add a new node.

That being said, if you are trying to search the linked list, insert to the middle, or delete from the middle of the linked list, the process will be much less efficient. We would need to traverse from the head to the node we are trying to access.

The other drawback with linked lists is that they use up a little more memory than arrays since they store the data and the pointer to the next node whereas arrays just store the data.

Let's look at the code we would use to implement some of these operations. We'll insert at the beginning of the linked list, and implement remove at index to show what needs to take place to do that:

class LinkedList {
  constructor() {
    // the head attribute stores a pointer to the first node in our linked list
    this.head = null
    this.length = 0
  }

  insert(data) {
    // inserts to the beginning of the linked list
    // what used to be  the head becomes the second element
    this.head = new Node(data, this.head) 
    this.length++
  }

  remove_value(value) {
    // remove any data value from the linked list

    // we need to store a pointer to a node and it's predecessor
    // so that when we remove the value we can just change the pointer!
    let prevNode = null
    let currentNode = this.head

    while (currentNode) {
      if (currentNode.data === value) {
        if (prevNode) {
          // Set the previous node's next value to the node we're deleting's next attribute
          // effectively removing it from our sequence
          prevNode.next = currentNode.next
        } else {
          this.head = currentNode.next
        }
        currentNode = null
        this.length--
        return true
      }
      // move to the next nodes
      prevNode = currentNode
      currentNode = currentNode.next
    }
  }
}

let thankUNext = new LinkedList()
thankUNext.insert('Ari')
thankUNext.insert('Malcolm')
thankUNext.insert('Pete')
thankUNext.insert('Ricky')
thankUNext.insert('Sean')

thankUNext.remove_value('Ricky')

Here's a visualization of what it would look like to remove Ricky from our linked list in case Ari became less effing grateful for him:

Everything in red gets deleted.

Two other helpful methods are search and iterate:

iterate() {
  let node = this.head
  while (node) {
    console.log(node.data)
    node = node.next
  }
}

search(data) {
  let idx = 0
  let node = this.head
  while (node) {
    if (node.data === data) return idx
    node = node.next
    idx += 1
  }
  return -1
}

So, we know that storing Ariana Grande's exes in a linked list is a great use of the data structure since we are always listing them in the same order when we sing along to "thank u, next", But what other data works well in a linked list? One use is a task queue. Printers, for example, can only print one thing out at a time, but we still want to load up future tasks and not have to press print for each page! When we create a list of tasks, we will always add the newest item to the end of the queue and then print out the one that's first in line! A back button implementation is similar! Or an undo hotkey! We will usually implement a stack or queue data structure on top of a linked list to implement these. I've also found them really helpful for a lot of code challenges.

Hopefully, this post taught you love instead of patience or pain.