数据结构与算法：顺序表详解

一、认识顺序表

1. 基本结构

顺序表是一种线性表，它用一段地址连续的存储单元依次存储线性表的数据元素。

比喻：将顺序表想象成电影院里一排连续的座位。

• 连续存储：这些座位是紧挨着的，一个接一个，这就是'顺序'的含义。数据在物理内存中是连续存储的。
• 快速按号找座：如果想找第 5 个座位上坐的是谁，可以计算出来并直接访问。
• 插入与删除麻烦：
  • 插入：如果这排座位已经坐满了，想在中间加一个人，那么从这个位置开始以后的所有人都需要向后移动一个位置，才能空出一个新的座位。
  • 删除：同理，如果中间有一个人离开了，那么他后面的所有人都需要向前移动一个位置来填补空位，以保持座位的连续性。

2. 手动实现

接口定义

package structure;

public interface IList {
    // 新增元素，默认在数组最后插入
    void add(int data);
    // 在 pos 位置插入新增元素
    void add(int pos, int data);
    // 判定是否包含某个元素
    boolean contains(int toFind);
    
     ;
    
     ;
    
     ;
    
     ;
    
     ;
    
     ;
    
     ;
    
     ;
     ;
}