Singly Linked List: Structure and Traversal

What is a Linked List?

At its core, a linked list is a linear data structure, but unlike an array, its elements are not stored in contiguous memory locations. Instead, elements are stored in objects called nodes. Each node contains two pieces of information:

1. The actual data or value.
2. A reference (or pointer) to the next node in the sequence.

The list is accessed through a single reference to the first node, called the head. The last node's next pointer points to None (or null), signaling the end of the list.

Let's watch a short video that visually explains this concept and contrasts it with the arrays we've just studied.

Implementing the Structure in Python

To build a linked list, we need to model its structure in code. This is typically done using two classes: a Node class to represent each element and a LinkedList class to manage the overall structure. Your experience with Object-Oriented Programming will be very helpful here.

1. The Node Class

The Node is the fundamental building block. It's a simple container for the value and the pointer to the next node.

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

2. The LinkedList Class

The LinkedList class acts as a wrapper for the entire sequence of nodes. For now, its only job is to hold a reference to the head of the list. An empty list is one where head is None.

class LinkedList:
    """
    An object for the linked list.
    Models one attribute: the head of the list.
    """
    def __init__(self):
        self.head = None # Initially, the list is empty

This structure is visualized well in the following image, which shows how individual Node objects are instantiated and then linked together by setting their next attributes.

The Core Algorithm: Traversal

How do we visit every element in a linked list? Since we can't use an index like in an array, we must perform a traversal. This is the most fundamental linked list operation, forming the basis for searching, printing, inserting, and deleting.

The algorithm is straightforward:

1. Create a temporary pointer, let's call it current, and initialize it with the head of the list.
2. Start a loop that continues as long as current is not None.
3. Inside the loop, "visit" the node (e.g., print its value).
4. Move to the next node by updating the pointer: current = current.next.

The following video provides an exceptionally detailed walkthrough of implementing traversal, both iteratively (with a loop) and recursively. Understanding both is crucial for interviews.

Putting it all Together

Now, let's integrate the iterative traversal logic into our LinkedList class as a print_list method. This makes our class more useful and provides a concrete example of traversal.

class LinkedList:
    def __init__(self):
        self.head = None

    # We will add insertion methods here in the next lesson
    
    def print_list(self):
        """
        Traverses the linked list and prints the values of the nodes.
        """
        current_node = self.head
        values = []
        while current_node:
            values.append(str(current_node.value))
            current_node = current_node.next
        
        if not values:
            print("List is empty")
        else:
            print(" -> ".join(values))

# Let's test it out
my_list = LinkedList()

# Manually create nodes and link them for now
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

my_list.head = node1
node1.next = node2
node2.next = node3

my_list.print_list()  # Expected output: 10 -> 20 -> 30

The time complexity of traversal is $O(n)$ because we must visit each of the $n$ nodes once. The space complexity is $O(1)$ for an iterative traversal since we only use a single extra pointer (current_node). For a recursive traversal, the space complexity becomes $O(n)$ due to the call stack depth.

class LinkedList:
    # ... __init__ and print_list from above ...

    def get_length(self):
        # Your implementation here
        pass

def get_length(self):
    """
    Traverses the linked list and returns its length.
    """
    count = 0
    current_node = self.head
    while current_node:
        count += 1
        current_node = current_node.next
    return count

# --- Test ---
# Using the same my_list from before
print(my_list.get_length()) # Expected output: 3

Conclusion

In this lesson, you've established the foundation for working with linked lists. You now understand their core structure and how they differ from arrays.

Key Takeaways:

• A singly linked list is composed of nodes, where each node contains a value and a next pointer to the subsequent node.
• The entire list is managed via a single head pointer. The end of the list is marked by a None pointer.
• Traversal is the fundamental operation for accessing nodes, which involves starting at the head and following the next pointers until you reach None. This is an $O(n)$ operation.

We've built the "scaffolding" of our linked list. In the next lesson, we will put it to use by implementing the very operations that make linked lists so powerful: insertion and deletion. You'll see how manipulating a few next pointers allows us to add and remove nodes efficiently.