loading...
Cover image for thank u, next: an introduction to linked lists

thank u, next: an introduction to linked lists

aspittel profile image Ali Spittel ・1 min read

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:
linked list

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.

Posted on Dec 5 '18 by:

aspittel profile

Ali Spittel

@aspittel

Passionate about education, Python, JavaScript, and code art.

Discussion

markdown guide
 
 
 

Everybody's getting into the spirit

 

That's a good introduction to linked lists.

Still I believe that linked lists are one of the most overrated data structures and that in practice there are very few use cases where they really perform better than dynamic arrays.

The main reason is that modern hardware has very efficient caches and that caching doesn't really work for linked lists.

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.

True, but caches are extremely good at moving blocks of memory around.

For a long time I believed myself that linked lists have huge advantages when inserting or deleting items and that this makes up for their difficult handling. But after doing some performance testing I did not find any practical case where they actually make sense.

At least I found that to be the case for C++ and Java. It might be different for certain interpreted languages where caching behaves differently.

 

Agreed, especially since dynamic languages pre-allocate space so insertion and deletion is more efficient. They come in most handy for implementing stacks and queues IMO.

 

The main reason I use linked lists are for queue structures where you frequently need to add to the end or pop the beginning, it's very bad if either of these operations are O(n). Instead you can use a simple singly-linked list.

When using a language like Java though, the LinkedList class isn't that good. The entire point of using a LinkedList over an ArrayList is that you can control certain things to make sure that the list operates as efficiently as possible, but Java's implementation doesn't allow for this.

 

One thing that people forget so often is that "linked list" as data structure doesn't have to mean the exact in-memory representation. When you use a LinkedList class, you don't care for its implementation details: it could actually be storing elements sequentially like a traditional array, but exposing only the methods so you see it like a linked list.

When talking about data structures, it's all about the public interface.

 

When you use a LinkedList class, you don't care for its implementation details

But linked list is the name of a specific implementation of a list. When a class is named LinkedList, I expect it to be implemented this way.

If you don't care about the implementation, it would be better to declare and use an interface named List that is implemented by classes named LinkedList or ArrayList.

Indeed, I should've used the term Abstract Data Type (ADT), not data structure.

Still, I don't think that LinkedList refers to the way it's implemented. For example, it's not uncommon for a tree to be implemented as two arrays: one to hold the index of the parent and the other to store the actual data. Such data structure could still expose all public methods as a tree, and you wouldn't have to know how it's implemented.

 

One case where they do make sense, is sharing the same (potentially very long) tail among various heads. This is useful when you want to trace something that splits up a lot.

In certain edge-cases a combination of both may also be useful; that is, a linked list of arrays. I haven't come across any use case where this really makes sense though.

 

We do not insert nor delete elements in lists in FP.

 

If only there was an "I'm so effing grateful for my ex" 😄

 
 

Oooh I should think of a place to put that!

 

This is awesome - learnt a lot and enjoyed the references along the way 😀

One question I have - in the remove_value() function because it changes the this.head value does that mean iterating it would start from the removal point?

How would you get it back to the start after removing a value of that is the case?

 

Thanks!! It only changes this.head if we are trying to remove the first value. Otherwise, only the node variables will change!

 

Ah I see, I read it wrong. Thanks for clarifying!

 

Whooa! This is an excellent article with a lot of "aris". I loved it.

I want to ask you if it is okay to translate your article in Korean and share it with my Korean dev community? I often translate awesome English articles into Korean. I really like to share yours too.

Thanks for the article anyways 🎉

 

I dont work as a programmer so forgive me if I might sounds dumb. Automating excel stuff with vba I only used arrays and few times dictionaries(which from what I Got to know is a synonymous for hashmap/hashtable). I tought that linked lists,stacks and queues where totally different data strutture with no correlation beside strong vakues in some way. I Got myself misleaded when you said you can implement stacks and queues on top od linked list. What do you mean by that? Maybe Next article i ll get it. But then what its seems to me that linked list are not that usefull at all.

 

I Got myself misleaded when you said you can implement stacks and queues on top od linked list. What do you mean by that?

Super quick, a stack is a stack of books. You can only put books on top and remove them from the top. So the first book you put is always the last to come in, because after a few books are added it will be at the bottom. To get to that you need to get each and every book sitting on top.

A linked list is a collection of nodes with data in which every node points to something, except the first one that points to nothing.

If you see the example Ali made:

to get to Ariana Grande (the book at the bottom in our stack example) you need to go through all the ex boyfriends. You would have to implement the two operations push and pop instead of remove_value which removes an arbitrary node (forbidden in a stack) but I hope you can see how you can map a stack on top of a linked list.

A queue is a similar concept. The difference between a stack and a queue is that a stack is last-in-first-out (the last boyfriend you add to the structure is the first one to go), a queue is first-in-first-out (the last boyfriend you add to the structure is the last one to go, in this case it's more similar to real-life).

I hope it's a bit clearer

 

It is a good article, but it seems to me that it is not relevant to JS Arrays. In JS array is a simple object, but specific a little bit. So no performance profit from the creation of linked list as a data structure in JavaScript.

data can be stored at non-contiguous locations in the array (c) MDN

Please fix me if I am wrong.

Links:

 

There are definite advantages in certain situations to create a linked list over an array in JavaScript (whether they are common I can't say).

If your array is very large, deleting or adding elements near the beginning of the array can be expensive as all elements after the deleted or added element must be re-indexed. In a linked list, removing a node only affects one other node.

The trade off is the expense of traversing the linked list.

An example of the expense of adding or removing elements at the beginning of an array is comparing the performance of push vs unshift in javascript. I wrote a small function that pushes the value true to the end of an array some number of times and reports the time it took to perform that action, then it takes a new array and unshifts the value true to the beginning of the array the same number of times and reports the time taken for that action. Push with 100,000 elements took 1.8ms, unshift took 4.4 seconds, and I've written this entire paragraph while waiting for the 1,000,000 element unshift to finish. The 1,000,000 element push took 22ms. Now that it finished, the unshift took 12 MINUTES.

If you don't have to traverse very far on the list, the performance gain for adding and removing items near the beginning of the structure can be very significant, finishing in milliseconds instead of minutes.

 

That is awesome example! And thanks for perf tests you did!! I really forgot about that stuff, shame on me :)

 

Funny because I just started a thread on help.gnu.emacs because I was not aware that when you assign a list to a variable, you are really only assigning the fist cell (what you call the pointer) and so when you change a cell in one list you change it in the other list too... I was really confused by that behavior in some piece of code and that gave me the opportunity to brush up my "cons" skills... :)

lists.gnu.org/archive/html/help-gn...

 

omg i love this so much... i hope everyone who reads this can now make linked "lists and laugh" ;)

 

THIS IS PERFECT Now I expect all ways of learning to do so with pop culture. I'm a new learner, and this is one of the few things that just makes sense. Thank you!

 

aw, that's so good to hear! I'm gonna do more like this!

 

hahaha I loved it! Saying it's a unique way to talk about data structures is an understatement :D

 

This intersection of pop culture with tech it is so refreshing! This is a great post!

 
 

Hi Ali. Thanks for share your knowledge about this topic.😊😊
I have a doubt, When your insert data, you put Ari first, then Malcom and then more exes and the last is Sean. But I think, the first element should be insert is Sean because He was the first ex.
When I implemented Linked List, the idea is I don't know what's next element, any element could be insert, so I think the implementation should allow the first data to be inserted should be Sean and not Ari.
That's is no clear for me. Can you explain this situation, please?

 

Shouldn't there be a method to remove a given index?

 

It’s incredibly similar to the remove value!

 
remove_value(value) {
    while (this.head && this.head === value) { // Special-casing the head
        this.head = this.head.next
    }

    for (let node = this.head; node.next; node = node.next) {
        while (node.next === value) {
            node.next = node.next.next
        }
    }
}

remove(i) {
    if (i === 0) { // Still special-casing the head. If only JS had pointers...
        this.head = null
        return
    }

    let node = this.head

    for (var j = 0; j++; j < i - 1) { // Go just *before* the node we need
        node = node.next
    }

    node.next = null
    this.length--
}
 

Thank you the tutorial. It is not boring at all.

 

Great way of explaining linked lists!

I wish this could give birth to a new series on dev.to:

Analogies to specific programming paradigms/concepts using songs

 

I think I might actually do that with pop culture references! Think it's super fun!

Thank you!

 

Tank you very much. Always love when I find an article talking precisely about something I have to do in a project.

 
 

Ali, thanks for the article. I found it very helpful and well explained. How would you approach sorting of the linked lists?

 

Awesome! You could use any normal sorting algorithm that you would use for an array -- I think merge sort is usually preferred for them though. The implementation is uglier than for an array though!

 

Awesome! I'm going to have to check this pattern out, and see how Generators can be extended/written to create linked lists 🤔

 
 

I've only just seen this post today as someone shared it on Twitter. I'm not sure I want to learn other concepts if they won't be framed into an Ariana Grande song. Pure awesome, thanks!