Unraveling the Mystery of Linked Lists

Part 3 of data structures series.

Let me guess 😜: you're here because someone whispered the words "Linked List" 🧏‍♂️ and you either ran away screaming 😱 or got super curious 🤔 about this mystical data structure. Either way, welcome! I’m here to break it all down for you in the most fun and beginner-friendly way possible. 🎉

Figure 1: Treasure chests

1. What the Heck is a Linked List, Anyway? 🤔

Imagine this 👇:

You have a chain of magical treasure chests (see Figure 1 above 👆). Each chest has:

1. Some treasure (data, like gold coins).

2. A map pointing to the next chest in the chain.

You can’t skip ahead and open the third chest until you've found the second one because the map to the next chest is always inside the current one! 🗺️

That’s a Linked List in a nutshell! It’s a data structure where each element (called a node) contains:

• Data (the stuff you care about).

• A pointer to the next node in the list (like a treasure map 🗺️).

2. Meet the Cast: Nodes and Pointers 🧑‍🤝‍🧑

Let’s break it down with a real-world example.

Imagine you have a Linked List of your favorite TV shows:

1. Node 1: Breaking Bad

   • Points to → Node 2: Stranger Things

2. Node 2: Stranger Things

   • Points to → Node 3: The Office

3. Node 3: The Office

   • Points to → NULL (the end of the list)

Fun fact: When a node points to NULL, it means “That’s all folks! No more TV shows (data) ahead!”

Each node only knows about the next one. There’s no going backward, like in a one-way street!

3. How Do You Create a Linked List? 🛠️

Enough talking—let's build one! I will be using Python 🐍 language this time (Don’t worry, I’ll hold your hand through this, you can use any of your favorite languages).

class Node:
    def __init__(self, data):
        self.data = data  # The treasure (data)
        self.next = None  # The map (pointer)

class LinkedList:
    def __init__(self):
        self.head = None  # The first treasure chest (node)
    
    # Method to add new nodes to the list
    def append(self, data):
        new_node = Node(data)
        if not self.head: #if the list is empty (head is None)
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Let's explain that a bit:

• We have a Node class that stores the data and a pointer to the next node.

• The LinkedList class helps us manage the whole chain of nodes.

4. Time to Add Some Data! 🎮

Let's add our TV shows into this list using the append() method.

# Creating the Linked List 
tv_shows = LinkedList() 

# Adding shows 
tv_shows.append('Breaking Bad') 
tv_shows.append('Stranger Things') 
tv_shows.append('The Office')

🎉 Ta-da! You’ve just built your first Linked List! Your favorite TV shows are now lined up in the list, waiting to be explored.

5. Traversing the List: How to Read the Data 🔍

But wait! You can’t just leave those shows hanging—you need a way to traverse the list, meaning, you want to go from the start to the end and peek inside each treasure chest. Let’s do that:

def print_list(linked_list):
    current = linked_list.head
    while current:
        print(current.data)
        current = current.next

Run that on your ”tv_shows” list, and you’ll see this:

Breaking Bad 
Stranger Things 
The Office

Simple, right? You start at the head and follow the treasure maps 🗺️ (pointers) until you hit the end (NULL).

6. Fun Twist: What Happens if We Remove a Node? 🧨

Uh-oh, let’s say Stranger Things suddenly got canceled (please, no!). How do we remove it from our Linked List?

def remove(linked_list, data_to_remove):
    current = linked_list.head

    # If the node to be removed is the head
    if current and current.data == data_to_remove:
        linked_list.head = current.next
        return
    
    # Otherwise, find the node to remove
    previous = None
    while current and current.data != data_to_remove:
        previous = current
        current = current.next
    
    if current:
        previous.next = current.next

You can now call:

remove(tv_shows, 'Stranger Things')
print_list(tv_shows)

Output:

Breaking Bad
The Office

Boom 🧨️! Stranger Things is gone, and the rest of your Linked List is still intact.

7. Linked List vs. Arrays: Why Use a Linked List? 🤷‍♂️

"Wait, why not just use an array/list? Isn’t that easier?" you might ask.

Good question! 💡

Arrays are like a row of lockers in a hallway. Every locker has a fixed position, and if you want to add a new one in the middle, you’ll have to shuffle things around (and maybe bump into a few people 😅).

Linked Lists, on the other hand, are like an open-ended string of pearls. You can easily add or remove a pearl (node) anywhere without disturbing the others. Plus, they grow and shrink dynamically.

However:

• Arrays are faster for random access O(1) (like instantly grabbing the 5th item).

• Linked Lists are better when you’re adding/removing items often and don’t need random access.

8. Variations of Linked Lists (Time to Level Up!) 🎮

Once you get the hang of the simple Singly Linked List, the land of data structures opens up with more advanced variations:

Singly Linked List

1. Doubly Linked List:

   • Each node points not only to the next node but also to the previous one.

   • Think of it like a two-way street, where you can go forward and backward.

     

     Doubly Linked List

2. Circular Linked List:

   • The last node points back to the first node, creating a circle! (No dead ends here. 🌐)

     

     Circular Linked List

3. Skip List:

   • Adds “express lanes” so you can jump ahead more quickly. 🚀

Skip List (advanced concept)

9. Time for a Linked List Adventure!

Here’s a challenge for you: 🌟

• Build your own Linked List of your top 5 songs!

• Write a function that prints out all the songs in reverse order (without using arrays or extra data structures!).

• Bonus: Add a feature to insert a new song anywhere in the list (not just at the end).

10. Knowledge check section!

11. Final Thoughts: You’re Ready for Linked List Mastery!

Congratulations! 🎉 You’ve just gone from "Linked List newbie" to "Linked List savvy" in a short time! And guess what? You’re now ready to tackle even more advanced data structures like trees, graphs, and beyond !

Always remember: a Linked List may sound scary at first, but once you’ve worked with it, you’ll realize it’s just a string of nodes holding hands—like a very organized, very determined conga line💃, LOL.

Happy coding 😃 ! And may your Linked Lists never point to NULL! 😎

In upcoming articles, we’ll uncover more data structures, so buckle up and stay tuned—this adventure’s just getting started! 🎢🎉

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!