顺序表（也称为动态数组或向量）是一种基础数据结构，用于在内存中存储元素的连续序列。与链表不同，顺序表在物理内存中是连续存储的。这使得顺序访问非常高效，但在插入和删除操作时可能需要移动大量数据。下面是顺序表的详细解析：

基本概念

1. 数组：顺序表底层依赖于数组，允许按索引快速访问元素。
2. 容量：数组的大小预先定义，如达到容量则需要扩展。
3. 大小：当前顺序表中实际存储的元素数量。
4. 扩容：当顺序表满时，新建更大容量的数组并复制旧数组的元素。

顺序表的操作

1. 初始化：

   List<Integer> list = new ArrayList<>();  // 使用Java内置的动态数组类  

2. 添加元素：

   • 在末尾添加（摊销时间复杂度 O(1)）：
     list.add(123); // 添加元素到列表的末尾
   • 在指定位置插入（时间复杂度 O(n)）：
     list.add(index, 456); // 在指定索引处插入元素

3. 访问元素（时间复杂度 O(1)）：

   int element = list.get(index); // 通过索引访问元素  

4. 更新元素（时间复杂度 O(1)）：

   list.set(index, 789); // 更新指定索引处的元素  

5. 删除元素：

   • 从末尾删除（时间复杂度 O(1)）：
     list.remove(list.size() - 1); // 移除最后一个元素
   • 删除指定位置（时间复杂度 O(n)）：
     list.remove(index); // 移除指定索引处的元素

6. 扩容机制：

   • 当添加元素导致超过当前容量时，顺序表会自动扩容。通常，新的容量为旧容量的1.5倍或2倍。扩容涉及到创建新的数组并复制旧数组的元素到新数组中。

特点与优点

• 快速随机访问：顺序表允许通过索引快速访问元素。
• 良好的缓存性能：由于顺序表中的元素是连续存储的，它在遍历时对CPU缓存友好。
• 支持动态扩展：可以自动调整容量以容纳更多元素。

缺点

• 插入和删除的效率低：在非末尾处执行插入和删除操作时，由于需要移动后续元素，从而增加了操作的复杂度。
• 可能浪费空间：为了简化扩容操作，通常会预留比实际需要更大的容量，可能导致空间浪费。

使用场景

• 当需要频繁进行随机访问操作时，顺序表表现优异。
• 多次添加元素（尤其是末尾添加）时使用。

示例代码

import java.util.ArrayList;  
import java.util.List;  
public class SequentialListExample {  
    public static void main(String[] args) {  
        List<String> names = new ArrayList<>();  
        // 添加元素  
        names.add("Alice");  
        names.add("Bob");  
        names.add("Charlie");  
        // 访问元素  
        System.out.println("Second name: " + names.get(1));  
        // 更新元素  
        names.set(1, "Beatrice");  
        System.out.println("Updated name: " + names.get(1));  
        // 删除元素  
        names.remove(2);  
        // 遍历顺序表  
        for (String name : names) {  
            System.out.println(name);  
        }  
    }  
}  

理解顺序表的工作机制和应用场景有助于在开发过程中作出更明智的数据结构选择。