Node Class and Singly Linked List Implementation

1. The Core Concept of a Linked List

Imagine a scavenger hunt. Each clue you find doesn't just give you a piece of the puzzle; it also tells you where to find the next clue. A linked list works in a very similar way. It's a sequence of elements called nodes. Each node contains two things:

1. The actual data (like a number, a string, etc.).
2. A reference (or "pointer") to the next node in the sequence.

This chain has to start somewhere, so we always keep track of the very first node, which we call the head. The chain also has to end; the last node's "next" pointer simply points to None.

This structure is fundamentally different from a Python list, which is implemented as a dynamic array. In an array, all elements are stored side-by-side in a continuous block of memory. In a linked list, the nodes can be located anywhere in memory, linked together only by their pointers.

2. The Building Block: The Node Class

To build a linked list, we must first define a blueprint for a single node. In Python, we do this by creating a class. Since you're familiar with classes from Module 3, this should be a straightforward step.

This first video will show you how to define the Node class.

As you saw, the Node class is simple. It only needs a constructor (__init__) to set its initial state. Here is a clean implementation. Note that the video called the next attribute next_node to avoid a conflict with a Python keyword, which is good practice. We'll use next for simplicity, as it's a common convention and doesn't cause issues in this context.

class Node:
    """
    An object for storing a single node of a linked list.
    Models two attributes: data and the link to the next node.
    """
    def __init__(self, data):
        self.data = data  # The data stored in the node (e.g., a number, string, etc.)
        self.next = None  # The reference to the next node in the list

When we create a Node, we pass it some data. Its next attribute is automatically set to None. This is because a newly created node doesn't point to anything yet; it's an isolated element until we explicitly link it to another node.

3. Creating a Basic Linked List

Now that we have our Node blueprint, we can create instances of it and link them together to form a chain. The following segment of the video demonstrates how to do this manually.

This manual process is key to understanding how linked lists work. Let's write the code for it ourselves:

1. Create individual nodes: We'll instantiate our Node class for each element we want in our list.
2. Link the nodes: We'll connect them by setting the .next attribute of each node.
3. Traverse the list: We'll start at the head and follow the .next pointers until we reach None.

# 1. Create individual nodes
node1 = Node(3)
node2 = Node(7)
node3 = Node(10)




# At this point, we have three separate Node objects.
# node1.next is None
# node2.next is None
# node3.next is None




# 2. Link the nodes together
print("Linking nodes...")
node1.next = node2  # The node containing 3 now points to the node containing 7
node2.next = node3  # The node containing 7 now points to the node containing 10



# node3.next remains None, marking the end of the list.




# The first node, node1, is now the head of our list.
head = node1




# 3. Traverse and print the list
print("Traversing the list:")
current_node = head
while current_node is not None:
    print(current_node.data, end=" -> ")
    current_node = current_node.next # Move to the next node
print("None")

Running this code will produce the output:
3 -> 7 -> 10 -> None

This confirms we have successfully created a basic linked list!

4. Encapsulating Logic with a LinkedList Class

While creating nodes and linking them manually is great for learning, it's not a practical way to manage a list. A much better approach is to create a LinkedList class that encapsulates the logic. This "manager" class will hold a reference to the head of the list and will eventually contain methods for adding, removing, and finding nodes.

For this lesson, we will create a LinkedList class that only does two things:

1. Initializes an empty list (meaning its head is None).
2. Provides a method to print all the elements in the list.

This approach aligns with the object-oriented principles you've learned, hiding the internal details from the user.

Building on that, here is the combined code for both our Node and LinkedList classes.

class Node:
    """An object for storing a single node of a linked list."""
    def __init__(self, data):
        self.data = data
        self.next = None
    
    def __repr__(self):



        # A helpful representation for printing a node
        return f"Node({self.data})"

class LinkedList:
    """Manages the linked list, starting with the head."""
    def __init__(self):
        self.head = None  # An empty list has no head

    def print_list(self):
        """Traverses the list and prints the data of each node."""
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

The __repr__ method in the Node class is a special method that provides a developer-friendly string representation of the object, which can be useful for debugging.

5. Your Turn: Practice Building a List

Now, let's use our new LinkedList class. Your task is to re-create the 3 -> 7 -> 10 list, but this time using the LinkedList class to manage it.

Instructions:

1. Create an instance of the LinkedList class.
2. Create three Node instances with data 3, 7, and 10.
3. Manually link the nodes together as we did before.
4. Set the head of your LinkedList instance to be the first node.
5. Call the print_list() method on your LinkedList instance to display the result.

You can write your code below to test your understanding.

# Your code here




# 1. Create a LinkedList instance
my_list = LinkedList()




# 2. Create the nodes
node_a = Node(3)
node_b = Node(7)
node_c = Node(10)




# 3. Link the nodes
node_a.next = node_b
node_b.next = node_c




# 4. Set the head of the list
my_list.head = node_a




# 5. Print the list
print("My linked list:")
my_list.print_list()




# Expected output:
# My linked list:
# 3 -> 7 -> 10 -> None

This exercise demonstrates the relationship between the container (LinkedList) and its contents (Node objects).

Conclusion

Well done! You have successfully built a singly linked list from scratch, starting with its most basic component. This is a significant step in your journey to mastering data structures.

Key Takeaways:

• A linked list is a linear data structure made of nodes connected by pointers.
• A Node has two primary attributes: data and a next pointer to the subsequent node.
• The start of the list is marked by the head, and the end is marked by a node whose next pointer is None.
• We can encapsulate the list's logic within a LinkedList class, which holds a reference to the head node.
• Traversal is the process of visiting each node by following the next pointers, starting from the head.

Preview of the Next Lesson:

Manually linking nodes is insightful, but not practical for real applications. In our next lesson, we will make our LinkedList class much more powerful. You will learn to implement insertion and deletion operations, allowing you to add and remove nodes from the list programmatically.