基于双向链表实现由(row,column,value)元组列表构建电子表格

基础类定义 #

先明确给定的基础类结构（以Python为例）：

class Cell:
    def __init__(self, row, col, value):
        self.row = row
        self.col = col
        self.value = value

class Node:
    def __init__(self, data=None):
        self.data = data  # 列节点存Cell实例，行节点存对应行的列链表头节点
        self.prev = None
        self.next = None

class LinkedListSpreadsheet:
    def __init__(self):
        self.head = None  # 行双向链表的头节点

buildSpreadsheet 方法实现 #

核心思路是先按行分组单元格，再为每行构建列双向链表，最后把所有行节点链接成行双向链表：

from collections import defaultdict

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

    def buildSpreadsheet(self, cell_list):
        # 1. 按行号分组单元格，同一行内按列号升序排序
        row_groups = defaultdict(list)
        for cell in cell_list:
            row_groups[cell.row].append(cell)
        # 对每个行的单元格列表按列号排序，保证列链表顺序正确
        for row_num in row_groups:
            row_groups[row_num].sort(key=lambda c: c.col)
        
        # 2. 构建行双向链表，同时为每行构建列双向链表
        prev_row_node = None
        # 按行号升序遍历所有行，保证行链表顺序正确
        for row_num in sorted(row_groups.keys()):
            current_row_cells = row_groups[row_num]
            # 构建当前行的列双向链表
            col_head = None
            prev_col_node = None
            for cell in current_row_cells:
                new_col_node = Node(cell)
                if not col_head:
                    col_head = new_col_node
                else:
                    # 链接双向节点
                    prev_col_node.next = new_col_node
                    new_col_node.prev = prev_col_node
                prev_col_node = new_col_node
            # 创建当前行的节点，存储列链表的头节点
            row_node = Node(col_head)
            # 链接到行双向链表中
            if not self.head:
                self.head = row_node
            else:
                prev_row_node.next = row_node
                row_node.prev = prev_row_node
            prev_row_node = row_node

关键逻辑说明 #

• 分组与排序：用字典按行号聚合单元格，再对每行的单元格按列号排序，确保列链表的节点顺序和列号一致。
• 双向链表构建：无论是行链表还是列链表，都严格维护prev和next指针，保证双向遍历的能力。
• 节点层级：行链表的每个节点存储对应行的列链表头节点，形成「链表的链表」结构，通过行链表可以定位到任意行，再通过该行的列链表遍历所有有值的单元格。

示例测试 #

针对输入 lCell = [[9,9,20],[2,5,7],[3,1,6],[8,5,-6.7],[1,1,3]]，先转换为Cell实例列表：

cell_list = [
    Cell(9, 9, 20),
    Cell(2, 5, 7),
    Cell(3, 1, 6),
    Cell(8, 5, -6.7),
    Cell(1, 1, 3)
]

# 构建电子表格
spreadsheet = LinkedListSpreadsheet()
spreadsheet.buildSpreadsheet(cell_list)

构建完成后：

• 行链表的头节点对应第1行，其data指向的列链表头节点存储Cell(1,1,3)；
• 第3行的列链表头节点存储Cell(3,1,6)；
• 第9行的列链表头节点存储Cell(9,9,20)，完全符合预期。

内容的提问来源于stack exchange，提问作者newToCode