链表本质与实现

链表采用彻底的分离式存储结构，节点内存地址完全不连续，仅通过指针/地址串联。Python中通过节点对象的引用实现链接。

内存特点

• 每个节点独立存在于内存任意位置
• 节点间通过存储的地址建立联系
• 唯一入口是头指针head，丢失则无法访问后续节点

节点结构实现

节点是最小存储单元，包含两个核心部分：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val    # 数据域存储实际内容
        self.next = next  # 指针域存储下一节点引用

新创建节点时next默认为None，表示当前节点是链表的末端节点。

单向链表整体架构

典型单向链表结构示意：

head → 节点A → 节点B → 节点C → None

• head指针指向首节点
• 每个节点的next指向后续节点
• 末节点next为None标识链表结束

链表管理类

链表类负责维护整体结构：

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 初始空链表
        self.size = 0     # 节点计数器

核心操作方法

判空检查

def is_empty(self):
    return self.head is None

长度计算

def length(self):
    cur = self.head
    count = 0
    while cur:
        count += 1
        cur = cur.next
    return count

遍历输出

def traverse(self):
    result = []
    cur = self.head
    while cur:
        result.append(str(cur.val))
        cur = cur.next
    print(" -> ".join(result) + " -> NULL")

头部插入

def add(self, item):
    new_node = ListNode(item)
    new_node.next = self.head
    self.head = new_node

尾部追加

def append(self, val):
    new_node = ListNode(val)
    if not self.head:
        self.head = new_node
    else:
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node

内存存储特性

链表在内存中的实际形态：

• 每个节点占据独立内存块
• 节点地址随机分布无连续性
• 节点间仅通过指针关联

与传统数组对比：

• 数组需要连续内存空间
• 链表充分利用内存碎片
• 数组支持随机访问，链表必须顺序遍历

复杂度分析

时间复杂度

• 头部插入/删除：O(1)
• 按索引访问：O(n)
• 尾部操作：O(n)

空间特性

• 每个节点额外存储指针
• 无预分配内存机制
• 动态增长无容量限制

双向链表实现总结

双向链表节点类

class DoubleNode(object):
    def __init__(self, item):
        self.item = item    # 数据域
        self.prev = None    # 前驱指针，默认指空
        self.next = None    # 后继指针，默认指空

双向链表类

class DoubleLinkList(object):
    def __init__(self):
        self.head = None   # 头指针
        self.tail = None   # 尾指针（方便尾部操作）

    def is_empty(self):
        return self.head is None

    def length(self):
        cur = self.head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    def travel_front(self):
        cur = self.head
        while cur:
            print(cur.item, end=" <-> ")
            cur = cur.next
        print("NULL")

    def travel_back(self):
        cur = self.tail
        while cur:
            print(cur.item, end=" <-> ")
            cur = cur.prev
        print("NULL")

    def add(self, item):
        node = DoubleNode(item)
        if self.is_empty():
            self.head = node
            self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node

    def append(self, item):
        node = DoubleNode(item)
        if self.is_empty():
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node

    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            cur = self.head
            count = 0
            while count < pos:
                cur = cur.next
                count += 1
            node = DoubleNode(item)
            node.prev = cur.prev
            node.next = cur
            cur.prev.next = node
            cur.prev = node

    def remove(self, item):
        cur = self.head
        while cur:
            if cur.item == item:
                if cur == self.head:
                    self.head = cur.next
                    if self.head:
                        self.head.prev = None
                    else:
                        self.tail = None
                elif cur == self.tail:
                    self.tail = cur.prev
                    self.tail.next = None
                else:
                    cur.prev.next = cur.next
                    cur.next.prev = cur.prev
                return
            else:
                cur = cur.next

    def search(self, item):
        cur = self.head
        while cur:
            if cur.item == item:
                return True
            cur = cur.next
        return False

测试代码

if __name__ == '__main__':
    dll = DoubleLinkList()
    print("=== 空链表 ===")
    dll.travel_front()

    dll.add(10)
    dll.add(20)
    print("\n=== 头插 20,10 ===")
    dll.travel_front()

    dll.append(30)
    dll.append(40)
    print("\n=== 尾插 30,40 ===")
    dll.travel_front()
    print("\n=== 反向遍历 ===")
    dll.travel_back()

    dll.insert(2, 25)
    print("\n=== 在位置2插入25 ===")
    dll.travel_front()

    dll.remove(25)
    print("\n=== 删除25后 ===")
    dll.travel_front()
    print("\n查找 30:", dll.search(30))
    print("链表长度:", dll.length())

核心知识点

双向链表节点包含三个部分：数据域（item）、前驱指针（prev）和后继指针（next）。双向链表可以从头到尾或从尾到头遍历，插入和删除操作比单向链表更方便，因为可以直接访问前驱节点。

双向链表的内存占用比单向链表稍大，因为每个节点多了一个指针。插入操作需要修改四个指针：新节点的prev和next，以及前后节点的相应指针。删除操作只需要让前后节点互相指向，跳过被删除节点。

单向链表与双向链表对比

• 指针数量：单向链表有一个next指针，双向链表有prev和next两个指针
• 遍历方向：单向链表只能从头到尾，双向链表可以双向遍历
• 插入/删除效率：双向链表更高效
• 内存占用：双向链表稍大
• 实现难度：双向链表更复杂