顺序表这个词第一次听容易觉得高深但说白了它就是数组的“带壳版”。对于一个Java初学者来说理解顺序表是真正迈入数据结构大门的第一个人脚印。我在带新人时经常说网上搜“java顺序表代码”搜出来的实现思路基本都是同一个套路但真正能把插入、删除、扩容这些细节讲透、知道每一步为什么要这么写的文章却不多。这篇我就从一个实际手写代码的角度把顺序表从设计思路到Java实现、再到踩坑排查完整过一遍。适合刚学完Java基础、准备啃数据结构的人也适合想回头把ArrayList源码看明白的同学。1. 顺序表到底是什么先搞懂底层逻辑搭建知识框架1.1 数据结构与线性表顺序表在整个知识版图里的位置数据结构说白了就回答一个问题数据在内存里怎么组织才能让增删改查又快又方便。常见的分类方式有两种按逻辑结构分有线性表、树、图按物理存储方式分有顺序存储和链式存储。顺序表就是“线性表的顺序存储结构”它意味着数据元素之间是一对一的线性关系并且在物理内存里也是连续排列的。怎么理解“逻辑相邻、物理也相邻”这句话你想象一排连在一起的电影院座位观众从1号坐起中间不留空这就是顺序表。如果观众改成手拉手站成一圈每个人只记住前后是谁至于站哪儿无所谓那就是链表。顺序表的特点决定了它的查找极快因为知道起始地址和下标就能直接算出目标位置但中间插入或删除就得带动后面所有人挪位置代价不小。很多人学到这里会犯一个毛病把“顺序表”和“数组”画等号。这个下一节仔细说因为这是后续所有容器类学习的分水岭。搞懂了顺序表ArrayList、Vector、Stack这些Java集合类的底层逻辑对你来说基本就是透明的了学起来跟看自己写的代码一样亲切。1.2 顺序表和数组到底差在哪数组是编程语言提供的基础机制Java里声明int[] arr new int[10]系统就给你分配一块连续内存通过下标访问。但数组有个痛点它只有“容器”的能力没有“管理”的脑子。你往数组中间插一个元素得自己从后往前搬你删一个元素得自己往前挪数组满了还得自己new一个更大的数组再把旧数据拷过去。这些操作每写一次边界判断、循环起点终点、索引更新哪一步错都会出bug而且不是立刻爆出来是运行到特定场景才出事非常恶心。顺序表干的事情就是把这些重复劳动封装成add、remove、get这些接口让使用者只关心“我要往列表里放一个东西”不需要关心“数组现在够不够大、后面元素往哪挪”。换句话说数组是砖头水泥顺序表是用砖头水泥盖好的一间屋子。屋子提供门窗水电你住进去就行不用每次开门都自己砌墙。这个封装思维极其重要。我见过很多初学者学会了顺序表之后回头写代码遇到需要动态增删元素的场景还傻乎乎地自己管理数组问他为什么不用ArrayList他说“我不知道它底层干了啥怕出事”。这就是把工具当黑盒。自己写一遍顺序表就是拆开这个黑盒看一遍内部结构之后再使用任何现成容器心里都有底。1.3 为什么第一课一定是顺序表大多数数据结构教材线性表这一章都会先讲顺序表再讲链表。这个顺序安排有讲究。顺序表是你对“存储”二字建立直觉最便宜的路径因为它不用和指针、节点引用打交道先把“数组操作封装”这件事玩明白。等到了链表你需要盯住的不再是格子本身而是格子之间的连接关系那时如果还得同时纠结插入删除的边界条件脑子很容易过载。再者顺序表是后续所有“随机访问型”容器的鼻祖。Java的ArrayList、C的vector、Python的list底层都是同一套思路连续数组 动态扩容。你把这个模型吃透了以后不管换什么语言遇到“可动态增长的数组列表”你都知道它内部大概是什么结构性能瓶颈在哪儿。对面试来说手写顺序表也是高频题但面试官看方案的时候很少会答得完整。其实要求很简单“写出一个支持增删改查、能自动扩容的泛型容器”。这一步写好了后面聊ArrayList源码、聊fail-fast机制、聊为什么扩容选1.5倍而不是2倍都有得聊了。2. Java实现顺序表的核心设计类的骨架与关键变量2.1 先确定需求一个顺序表应该支持哪些操作动手写代码之前先列出这个类对外提供哪些能力。我习惯用“用户视角”倒推如果我把这个类交给别人用对方大概率需要以下操作添加尾插add(element)中间插add(index, element)删除按位置删remove(index)按值删removeByValue(element)修改set(index, newValue)改完返回旧值查找get(index)按下标取indexOf(element)查元素位置contains(element)判断是否存在辅助size()返回已存数量isEmpty()判空clear()清空toString()打印内容把方法签名先列出来再一个一个实现比起“打开IDE想到什么写什么”要清晰得多。这也是一种工程习惯数据结构就是“接口优先设计”的产物对外暴露什么内部怎么实现两者解耦。这个习惯养成了以后设计类、模块、微服务边界时都用得上。2.2 成员变量怎么定容量与已存长度的纠葛初写顺序表最容易绕晕的就是两个数data.length容量capacity和size实际存了几个元素。容量是数组这个物理容器最多能装多少size是当前有效元素的数量。两者关系永远是size capacity。public class SeqListT { private T[] data; // 存放元素的数组物理存储 private int size; // 当前实际元素个数 private static final int DEFAULT_CAPACITY 10; }这里注意要么不定义capacity变量直接用data.length表示容量要么定义capacity并保证和data.length一致。我见过有的同学写着写着容量和size就混了比如遍历时用data.length结果数组扩容后多出一堆null也一起打印出来。建议新手上路阶段别单独设capacity统一用data.length。等你熟练了再看那些以capacity为基准的写法才能一眼看出别人代码里哪里偷了懒、哪里容易出问题。2.3 泛型和Object怎么选从第一个版本就养成好习惯早期教科书写顺序表喜欢用Object数组因为它简单、不用管类型。但用Object有一个致命缺点取数据时得强转转错类型直接ClassCastException。到Java 5以后泛型已经是标准能力了自己写容器就该用泛型。public class SeqListT { private T[] data; private int size; SuppressWarnings(unchecked) public SeqList(int capacity) { data (T[]) new Object[capacity]; size 0; } }这里有个Java语法的大坑不能直接new T[capacity]因为泛型在运行时会被擦除JVM根本不知道T到底是谁。所以标准做法是创建一个Object数组然后强转为T[]。强转会有一个“Unchecked cast”警告这个警告可以忽略用SuppressWarnings(unchecked)压掉即可。这一步新手几乎必卡我给的解释是“编译器提醒你这里有个类型安全隐患但你用Object数组再转泛型这是Java语言自己都没法优雅处理的地方你这样做已经是常规操作了”。2.4 扩容策略为什么是翻倍而不是加固定长度数组一旦满了就得换一个更大的新数组把旧数据全部搬过去。这里就有个关键问题每次扩多少直觉可能觉得“每次加10个”挺好算一算就知道不行。假设从1扩到100加固定长度10的话会扩容10次每次都要把已有元素整体拷贝总搬运次数是102030...90约450次。但如果按翻倍策略扩容次数只有7次左右总搬运次数约2n量级从O(n²)降到了O(n)。这就是为什么ArrayList源码里扩容要用oldCapacity (oldCapacity 1)也就是每次增加原来的一半相当于1.5倍。翻倍比例1.5到2倍之间最常见因为这样“扩容搬运”的总成本均摊下来每次add操作是O(1)的摊还复杂度。既不会频繁扩容也不会一次扩太大浪费内存。private void grow() { int oldCapacity data.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity - 1 oldCapacity) { newCapacity oldCapacity 1; } data Arrays.copyOf(data, newCapacity); }实际代码里我用Arrays.copyOf一行搞定拷贝比手写for循环简洁。但在教学时我会特意用for循环演示一遍搬移到底发生了什么等你理解了再换成copyOf优化。我上面的写法里newCapacity那一行纯粹是防御性校验防止oldCapacity为1时右移成0导致数组越界初学者可以等上面两行跑通了再琢磨。3. 核心操作一步步实现插入、删除、查找的完整代码3.1 先把公共骨架搭起来构造方法、扩容、判空正式写操作之前先准备好三个辅助方法构造函数、扩容、判空。这个顺序别颠倒不然后面add方法里要调用ensureCapacity却发现还没有这个私有方法。public SeqList() { this(DEFAULT_CAPACITY); } public SeqList(int capacity) { if (capacity 0) { throw new IllegalArgumentException(容量不能为负数: capacity); } data (T[]) new Object[capacity]; size 0; } private void ensureCapacity() { if (size data.length) { grow(); } }无参构造把活儿委托给有参构造这是Java里很常见的构造器重载风格。容量参数为负直接抛异常比等到操作时再崩溃更合理这叫“快速失败”。3.2 尾部添加和指定位置插入为什么搬移必须倒着来尾部添加最简单先检查容量再把新元素放到size位置size加一。真正有技术含量的是中间插入add(index, element)。假设数组存的是[10, 20, 30, 40]要在下标1插入15最终应该是[10, 15, 20, 30, 40]。插入之后原本在下标1到3的元素都向后挪一位形成空位再放新值。这个搬移过程必须从后往前先拿40放到下标4再拿30放到下标3最后拿20放到下标2。如果从前往后搬先把下标1的20放到下标2那下标2的30就被覆盖了后面全乱套。这个“倒着搬”的直觉比背代码重要得多。public void add(int index, T element) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } ensureCapacity(); for (int i size; i index; i--) { data[i] data[i - 1]; } data[index] element; size; }注意边界插入的下标允许等于size因为这意味着在末尾追加相当于add(element)。但index大于size就不行了因为中间会留下空洞破坏“中间不留空”的顺序表特性。这里抛IndexOutOfBoundsException和Java内置ArrayList的行为保持一致。3.3 删除操作向前搬移与最后一个元素置空删除remove(index)是插入的镜像操作目标元素之后的所有元素向前挪一位把那个位置盖掉。比如数组[10, 20, 30, 40]删除下标1得到[10, 30, 40]过程就是30复制到下标140复制到下标2。这次是从前往后搬。public T remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } T removed data[index]; for (int i index; i size - 1; i) { data[i] data[i 1]; } size--; data[size] null; return removed; }这里有个初学者极容易忽略的细节搬移完成后最后一个位置还残留着被删元素的引用。如果这个顺序表里装的是对象这个残留引用会一直锁住那个对象让垃圾回收器没法回收它这就是所谓的内存泄漏。显式把data[size]置为null就是把这个引用断开。虽然对基本类型来说无所谓但对对象类型养成这个习惯非常重要。ArrayList源码里remove操作末尾也有一句data[--size] null就是这个道理。按值删除就更简单了先查位置再按位置删找不到就返回falsepublic boolean removeByValue(T element) { int index indexOf(element); if (index -1) { return false; } remove(index); return true; }3.4 查找与修改边界检查先行get和set这两个方法极其相似都是先校验下标合法性再操作数组。public T get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } return data[index]; } public T set(int index, T element) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } T oldValue data[index]; data[index] element; return oldValue; }边界检查有个坑get和set的合法索引是0到size-1特别注意remove和get不能取indexsize但add可以插到indexsize。很多bug就出在“取的时候把size当成合法值”上建议自己写一个统一的checkIndex方法每次调用前想清楚这次是“读”还是“写”。indexOf的写法要通盘考虑null值。如果传入的element是null直接调用element.equals(de[i])会空指针。标准写法是分情况判断public int indexOf(T element) { for (int i 0; i size; i) { if (element null ? data[i] null : element.equals(data[i])) { return i; } } return -1; }这种用三元表达式处理null的做法和Java源码里Objects.equals的思路一致。contains直接复用indexOf即可。3.5 重写toString别用capacity遍历最后重写toString方便调试输出。写的时候最容易犯的错是遍历范围写成data.length而不是size。数组扩容后data.length变大后面没存数据的格子都是null打印出来就是[10, 20, 30, null, null, null]。这种输出会误导你判断程序是否正常。Override public String toString() { StringBuilder sb new StringBuilder([); for (int i 0; i size; i) { sb.append(data[i]); if (i ! size - 1) { sb.append(, ); } } return sb.append(]).toString(); }用StringBuilder拼接而不是字符串用号是小习惯但体现工程意识。量小无所谓量大了字符串拼接会产生大量中间对象影响性能。4. 跑起来看效果测试代码与ArrayList源码对比4.1 写一个main方法跑完所有核心操作代码写完不跑等于白写。我测试时故意把初始容量设成2这样插入第3个元素时会触发扩容能直观看到扩容前后的变化。public class TestSeqList { public static void main(String[] args) { SeqListInteger list new SeqList(2); list.add(10); list.add(20); list.add(30); // 触发扩容容量从2变3 System.out.println(list); // [10, 20, 30] list.add(1, 15); System.out.println(list); // [10, 15, 20, 30] list.set(2, 25); System.out.println(list); // [10, 15, 25, 30] System.out.println(list.get(3)); // 30 System.out.println(list.indexOf(25)); // 2 System.out.println(list.contains(100)); // false System.out.println(list.remove(1)); // 15 System.out.println(list); // [10, 25, 30] list.removeByValue(30); System.out.println(list); // [10, 25] list.clear(); System.out.println(list.isEmpty()); // true } }我在IDE里跑这个测试时会在add(30)那一行打断点观察扩容前后data数组的内容变化。你会发现一个很有意思的过程扩容前data.length是2下标0、1分别为10、20size为2触发扩容后data指向一个全新的长度为3的数组前两位被拷贝进来第三位再存入30。看清楚了这一步你对“动态数组”的理解就不是“它自动变大了”而是“它换了个更大的房子把东西搬进去了”。4.2 和Java内置ArrayList对比它们是同一套思路把你写好的SeqList和JDK里的ArrayList对比一下会看见自己写的代码几乎就是简化版源码。ArrayList的默认初始容量是10扩容时机也是size elementData.length扩容公式是int newCapacity oldCapacity (oldCapacity 1)相当于1.5倍。它也有private void rangeCheckForAdd(int index)来校验越界也有remove方法最后的elementData[--size] null。区别在哪里ArrayList把elementData数组定义为transient并且在序列化时只序列化已存元素而不是整个数组这是一种节约空间的优化。它还实现了RandomAccess接口标明自己支持快速随机访问这也是为什么ArrayList遍历用for循环比用Iterator快。这些是顺带的目标不必一口气全学但每一条都值得在看完自己代码之后回头再看一眼。自己手写一遍再对照源码学习和直接啃源码是完全不同的体验。直接啃源码时“它为什么要这么写”你看不出痛点手写一遍之后你会想“我这个判断是不是漏了边界”“这里要不要加防御”再看源码就能瞬间理解那些看起来多余的代码都是为了堵你踩过或没踩过的坑。4.3 调试经验插入删除这类搬移操作怎么用断点看插入和删除这类搬移操作只看打印结果很难看出过程我建议用断点配合单步执行分三步观察第一步在for循环开始前打一个断点看当前数组内容和index值确认起始状态。第二步单步进入for循环每执行一次data[i] data[i - 1]就看一次数组变化重点观察有没有值被覆盖覆盖错位置。第三步循环结束后看data[index]是否成功赋值size是否正确增加。这个方法尤其推荐给“数组越界总是查不明白”的同学。搬移操作的核心是循环边界写错了最常见的症状就是某些值重复了、某些值丢了。用断点走一遍十分钟就能定位问题比你盯着代码干瞪眼一小时效率高得多。5. 常见问题速查与避坑心得5.1 高频异常清单索引越界、空指针、并发修改我整理了一份顺序表新手最容易踩的高频问题按出现频率排序你可以照着自查一遍。典型问题现象原因与对策IndexOutOfBoundsException添加、删除、查询时抛异常三类操作的合法下标范围不同。add允许0到sizeremove、get、set只允许0到size-1别搞混NullPointerException遍历时偶发空指针删除元素后没有把末尾位置置null或者indexOf里直接取element.equals导致空指针用三元表达式判断打印出一堆null输出[1, 2, null, null]toString遍历用了data.length而不是size遍历范围写错扩容后老数据丢失只显示新添加的元素手动扩容时for循环起始或范围写错推荐直接用Arrays.copyOf删除元素后size没错但值不对删除后少了一个元素或重复了一个元素搬移循环边界写错。删除时i从index到size-2而不是size-1最后再size--ConcurrentModificationException在foreach循环里调用remove使用迭代器遍历时修改结构这是修改和遍历并发的问题后面学迭代器时重点关注这些问题有个共同点边界判断加上循环范围两者你只要有一个犯迷糊整个结构就会出乱子。我的习惯是在写每一处循环前先用具体例子在草稿纸上画5个格子的数组模拟一遍搬移过程再落到代码。磨刀不误砍柴工画一遍比写代码快还能避免改半天。5.2 学习建议如何把顺序表练成顺手的基本功最后分享一点我带新人时常用的练习方法。写完基础版本后别急着去学下一个数据结构先给自己加三个任务第一把初始容量改成0试试看构造方法和add逻辑还能否正常跑。你会发现capacity为0时第一次add就需要扩容这时grow里的防御性判断就起作用了。这不仅帮你检测代码健壮性还让你理解为什么ArrayList源码里会有一行看起来多余的newCapacity判断。第二给SeqList加一个toArray方法返回一个精确大小的新数组而不是直接返回内部data。直接返回内部数组会让外部拿到引用后随意修改内部状态破坏封装。自己实现一遍toArray你对“返回副本”这种防御性编程的感受会很立体。第三拿自己写的代码跟ArrayList源码做逐行对比给每个方法找到对应实现。不要求全部看懂只看扩容、add、remove三个方法就够了。对比之后你会发现自己开始能理解“api设计”这个词的含义同样的功能不同语言、不同版本为什么会有这些细微差异。顺序表本身并不复杂复杂的是“在动手之前想清楚边界条件”这件事。把这件事练成本能后面学链表、栈、队列时你会轻松很多因为它们本质上都在处理同一个老问题如何在正确的边界条件下安全地操作数据。我个人在实际带人过程中发现凡是顺序表写得干净利落、测试用例覆盖到位的同学后续学二叉树、图这些复杂结构时明显更有章法因为他已经知道“学习一个数据结构的固定套路”先想接口再想存储最后写操作和边界。如果你也想把这份基本功练扎实就拿这个项目练手吧。