线性表的常见操作

学习目标

本节系统整理线性表的常见操作。

线性表不是只用来“存一排数据”。它的价值体现在围绕这排数据可以进行哪些操作，以及这些操作在不同实现方式下成本如何变化。理解这些操作，是后续比较顺序表和链表的基础。

按位置访问

按位置访问指的是获取第 $i$ 个元素。

在顺序表中，按下标访问通常非常高效：

int getValue(const vector<int>& numbers, int index) {
    return numbers[index];
}

int getValue(int[] numbers, int index) {
    return numbers[index];
}

def get_value(numbers, index):
    return numbers[index]

int GetValue(int[] numbers, int index)
{
    return numbers[index];
}

顺序表可以直接根据下标定位，因此通常是 $O(1)$ 。

但在链表中，如果想访问第 $i$ 个节点，一般需要从头节点开始走 $i$ 步，因此通常是 $O(n)$ 。

按值查找

按值查找指的是找到某个目标元素是否存在，或者找到它的位置。

int findIndex(const vector<int>& numbers, int target) {
    for (int i = 0; i < numbers.size(); i++) {
        if (numbers[i] == target) {
            return i;
        }
    }

    return -1;
}

int findIndex(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        if (numbers[i] == target) {
            return i;
        }
    }

    return -1;
}

def find_index(numbers, target):
    for index, number in enumerate(numbers):
        if number == target:
            return index

    return -1

int FindIndex(int[] numbers, int target)
{
    for (int i = 0; i < numbers.Length; i++)
    {
        if (numbers[i] == target)
        {
            return i;
        }
    }

    return -1;
}

如果线性表没有额外索引，也没有排序信息，按值查找通常需要逐个检查元素，时间复杂度是 $O(n)$ 。

插入操作

插入操作是在指定位置加入一个新元素。

在顺序表中，如果在中间插入，后面的元素往往需要向后移动。最坏情况下，在开头插入需要移动 $n$ 个元素，因此是 $O(n)$ 。

在链表中，如果已经知道插入位置的前一个节点，只需要调整引用关系，插入本身是 $O(1)$ 。但如果要先查找这个位置，整体仍可能是 $O(n)$ 。

这说明分析操作复杂度时，要明确前提：是“已经知道位置”，还是“需要先查找位置”。

删除操作

删除操作是从线性表中移除某个元素。

在顺序表中，删除中间元素后，后面的元素通常需要向前移动，所以最坏时间复杂度是 $O(n)$ 。

在链表中，如果已经知道待删除节点的前一个节点，可以通过改变引用关系删除节点，操作本身是 $O(1)$ 。但如果要先找到这个节点或它的前一个节点，整体通常是 $O(n)$ 。

遍历操作

遍历指的是依次访问线性表中的所有元素。

无论是顺序表还是链表，只要需要访问所有元素，通常都需要 $O(n)$ 时间。

void visitAll(const vector<int>& numbers) {
    for (int number : numbers) {
        cout << number << endl;
    }
}

void visitAll(int[] numbers) {
    for (int number : numbers) {
        System.out.println(number);
    }
}

def visit_all(numbers):
    for number in numbers:
        print(number)

void VisitAll(int[] numbers)
{
    foreach (int number in numbers)
    {
        Console.WriteLine(number);
    }
}

遍历的重点在于“每个元素都要处理一次”。因此，只要元素数量是 $n$ ，遍历通常就是线性复杂度。

操作成本总结

下面是一个简化对比：

操作             顺序表                 链表
按位置访问        O(1)                  O(n)
按值查找          O(n)                  O(n)
已知位置插入      O(n)                  O(1)
已知位置删除      O(n)                  O(1)
遍历              O(n)                  O(n)

这个表格是理解线性表的重要基础。后续学习栈、队列、哈希表、树等结构时，也会不断比较不同操作的成本。

本节小结

线性表常见操作包括访问、查找、插入、删除和遍历。

顺序表适合按位置快速访问，但中间插入删除可能需要移动元素。链表不擅长按下标访问，但在已知节点位置时插入删除更灵活。选择哪一种实现，取决于具体场景中最频繁、最关键的操作是什么。