Linked Lists

Part 1: Extending the Singly-Linked List

Adding to the end of a linked list shouldn’t feel like hiking to the tail with a headlamp. So, I gave my singly-linked list an extra sense — a tail pointer. With it, add_last() became sleek and snappy, running in constant time, O(1).

To support this, I modified the __init__() method to include a self.tail attribute:

def __init__(self):
    self.head = None
    self.tail = None
    self.size = 0

Then I defined add_last() like this:

def add_last(self, data):
    new_node = self.Node(data)
    if not self.head:
        self.head = new_node
    else:
        self.tail.next = new_node
    self.tail = new_node
    self.size += 1

Part 2: Creating a Doubly-Linked List

With two pointers — prev and next — each node in a doubly-linked list becomes a better conversationalist: it remembers where it came from and knows where it’s going. Building it wasn’t just about reverse traversal, but about respecting the symmetry of movement in both directions.

class Node:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next

def add_last(self, data):
    new_node = self.Node(data, self.tail, None)
    if not self.head:
        self.head = new_node
    else:
        self.tail.next = new_node
    self.tail = new_node
    self.size += 1

Part 3: Reflection

Understanding Linked Lists

Arrays are like elevators — fast access to any floor, but resizing or rearranging is a pain. Linked lists are more like staircases — you climb node by node, but inserting or removing a step is smooth. Singly-linked lists give you the basics; doubly-linked ones offer more control but charge a memory toll.

Linked lists are commonly used in music playlists, browser history navigation, and undo-redo functionality — all areas where flexible insertion or deletion is prioritized over fast random access.

Challenges and Insights

Refactoring the singly-linked list made me realize just how much power a tail pointer brings — and how little effort it takes to significantly impact performance.

Building the doubly-linked list required more careful pointer choreography. Every node was a balancing act between forward and backward references — and if one step was off, the whole dance broke.

Personal Takeaways

This was not just a coding exercise but a reminder that elegant structure comes from intentional relationships. Nodes don't exist in isolation. They connect, support, and adapt like good ideas, systems, or even people.

How I Would Explain Linked Lists

Think of a linked list like a trail of breadcrumbs. You follow the crumbs forward in a singly-linked list but can't retrace your steps. In a doubly-linked list, you leave marks in both directions — like footprints in the snow. You know where you're going and how to get back.