如何在数组0th index插入元素且无需逐个移位？求更优实现方案

核心思路：用逻辑偏移量替代物理元素移位 #

常规头部插入需要逐个后移元素，时间复杂度O(n)。我们可以通过维护逻辑起始偏移量，循环利用物理数组空间，彻底避免每次插入的移位操作：

• 用offset变量标记数组逻辑上的起始位置，逻辑索引i对应物理数组的索引为(offset + i) % capacity
• 插入头部元素时，只需将offset向前偏移一位（对数组容量取模），再把新元素放到物理数组的offset位置即可
• 仅当数组满时触发扩容，扩容时一次性将所有元素按逻辑顺序复制到新数组，而非每次插入都移位

代码实现（Python） #

class ShiftFreeArray:
    def __init__(self, initial_capacity=8):
        self.capacity = initial_capacity
        self.size = 0
        self.offset = 0
        self.array = [None] * self.capacity

    def insert_at_head(self, value):
        # 数组满时扩容，一次性整理元素
        if self.size == self.capacity:
            new_capacity = self.capacity * 2
            new_array = [None] * new_capacity
            # 按逻辑顺序把现有元素复制到新数组的前半段
            for i in range(self.size):
                new_array[i] = self.array[(self.offset + i) % self.capacity]
            self.array = new_array
            self.capacity = new_capacity
            self.offset = 0  # 扩容后逻辑起始点重置为0
        
        # 调整偏移量，插入新元素到逻辑头部
        self.offset = (self.offset - 1) % self.capacity
        self.array[self.offset] = value
        self.size += 1

    # 获取逻辑索引对应的元素
    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of range")
        return self.array[(self.offset + index) % self.capacity]

    # 按逻辑顺序输出数组
    def __repr__(self):
        return str([self.get(i) for i in range(self.size)])

性能优势 #

• 头部插入操作均摊时间复杂度为O(1)：仅扩容时需要O(n)时间，但扩容频率随数组容量增长而降低，整体性能远优于常规移位实现
• 避免了频繁的内存拷贝操作，减少CPU开销
• 物理数组空间循环利用，无需每次插入都调整元素位置

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