Episode 2: Linked List – Simple Array vs. List Comparison

Array vs. Linked List

Arrays are likened to a row of fixed lockers: each position is immutable, and removing a locker forces all subsequent ones to shift, which is cumbersome. Linked lists are compared to a string of pearls, where each pearl (node) stores its own data and a reference to the next pearl, allowing flexible insertion and deletion without moving other elements.

Core Principle (Beginner Version)

A linked‑list node contains two fields: a data field that holds the actual value (e.g., a name or score) and a pointer field that records the address of the next node. The final node’s pointer is None, indicating the end of the list.

The main advantage is that linked lists do not require contiguous memory and can add or remove elements without shifting the whole structure. The sole drawback is the inability to perform random access; traversal must start from the head node.

Real‑world Use Cases

Social media feeds such as WeChat Moments or TikTok infinite scroll lists

Music player previous/next track navigation

Operating‑system dynamic memory allocation

Underlying structures of hash tables, stacks, and queues

Runnable Code Example

# 定义链表节点类
class Node:
    def __init__(self, data):
        self.data = data  # 存储数据
        self.next = None  # 存储下一个节点地址，默认空

# 定义链表类
class LinkedList:
    def __init__(self):
        self.head = None  # 初始化头节点为空

    # 1. 尾部添加节点
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node

    # 2. 指定位置插入节点
    def insert(self, index, data):
        new_node = Node(data)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return
        cur = self.head
        count = 0
        while cur and count < index - 1:
            cur = cur.next
            count += 1
        new_node.next = cur.next
        cur.next = new_node

    # 3. 删除指定数据节点
    def delete(self, data):
        cur = self.head
        if cur and cur.data == data:
            self.head = cur.next
            return
        while cur.next and cur.next.data != data:
            cur = cur.next
        if cur.next:
            cur.next = cur.next.next

    # 4. 遍历打印链表所有数据
    def show(self):
        res = []
        cur = self.head
        while cur:
            res.append(str(cur.data))
            cur = cur.next
        print("链表数据：" + " -> ".join(res))

# ========== 小白直接测试运行 ==========
if __name__ == "__main__":
    link = LinkedList()
    link.append(10)
    link.append(20)
    link.append(30)
    link.show()  # 输出：10 -> 20 -> 30
    link.insert(1, 15)
    link.show()  # 输出：10 -> 15 -> 20 -> 30
    link.delete(20)
    link.show()  # 输出：10 -> 15 -> 30

Execution Results

Linked list data: 10 -> 20 -> 30

Linked list data: 10 -> 15 -> 20 -> 30

Linked list data: 10 -> 15 -> 30

Common Pitfalls for Beginners

1. Linked lists have no index; traversal must start from the head node.

2. When inserting or deleting, connect the new node before breaking the old link; the order cannot be reversed.

3. Ensure the last node’s next is None to avoid infinite loops.

Selection Cheat Sheet

✅ Frequent queries with static data → use arrays.

✅ Frequent insertions/deletions with dynamic data → use linked lists.