数据结构入门——线性表：顺序表与链表

数据结构是计算机专业的核心基础课，也是 408 考研的第一门专业课。这一篇从最基础的线性表开始，把顺序表和链表讲透。

一、什么是线性表

线性表（Linear List）是最基本、最常用的数据结构。简单说就是一组数据排成一条线：

元素1 → 元素2 → 元素3 → ... → 元素N

每个元素都有唯一的前驱（前一个元素）和唯一的后继（后一个元素），第一个元素没有前驱，最后一个没有后继。

生活中的例子：

• 排队买奶茶的队伍 → 线性表
• 高中座位表 → 线性表
• 手机通讯录 → 线性表

线性表的两种存储方式：

• 顺序表：用连续的内存空间存储（类似数组）
• 链表：用不连续的内存空间存储，靠指针连接

二、顺序表（数组）

1. 什么是顺序表

顺序表就是把元素按顺序存放在连续的内存空间中。在 Java 中就是ArrayList，在 C 中就是数组。

内存地址： 100 101 102 103 104 105 106 ┌────┬────┬────┬────┬────┬────┬────┐ 数据： │ 10 │ 20 │ 30 │ 40 │ 50 │ │ │ └────┴────┴────┴────┴────┴────┴────┘ 下标： 0 1 2 3 4 5 6

顺序表的三个核心属性：

publicclassArrayList<E>{privateObject[]data;// 存储数据的数组privateintsize;// 当前元素个数privateintcapacity;// 数组总容量（= data.length）}

2. 顺序表的基本操作

查找（随机访问）——O(1)

// 按下标访问，直接通过地址偏移计算publicEget(intindex){if(index<0||index>=size){thrownewIndexOutOfBoundsException();}return(E)data[index];}

为什么是 O(1)？数组在内存中是连续存储的，data[i]的地址 = 起始地址 + i × 每个元素大小。一步就能定位。

插入——O(n)

// 在指定位置插入元素publicvoidadd(intindex,Eelement){// 1. 检查下标范围if(index<0||index>size)thrownewIndexOutOfBoundsException();// 2. 检查容量是否够，不够就扩容if(size==data.length){grow();// 扩容为原来的 1.5 倍}// 3. 将 index 及以后的元素后移一位（这是最耗时的）for(inti=size;i>index;i--){data[i]=data[i-1];}// 4. 插入新元素data[index]=element;size++;}

初始： [10, 20, 30, 40, _] ↑ 空位 在下标 1 处插入 15： 第一步：元素后移 [10, 20, 30, 40, _] → [10, 20, 30, _, 40] [10, 20, 30, _, 40] → [10, 20, _, 30, 40] [10, 20, _, 30, 40] → [10, _, 20, 30, 40] 第二步：插入 15 [10, 15, 20, 30, 40]

最坏情况：在头部插入，所有元素都要后移 → O(n)

删除——O(n)

publicEremove(intindex){if(index<0||index>=size)thrownewIndexOutOfBoundsException();EoldValue=(E)data[index];// 将 index 后面的元素前移for(inti=index;i<size-1;i++){data[i]=data[i+1];}data[size-1]=null;// 清空引用，帮助 GCsize--;returnoldValue;}

最坏情况：删除头部元素，所有元素前移 → O(n)

三、链表

1. 什么是链表

链表的元素不连续存储，每个元素是一个节点（Node），节点之间通过指针连接。

classNode{intdata;// 数据域Nodenext;// 指针域：指向下一个节点}

内存中不连续的位置： [10 | 地址A] → [20 | 地址B] → [30 | 地址C] → [40 | null] ↑ ↑ 头指针 head 最后一个节点指向 null

链表只需要记住头节点（head）的位置，就能找到所有节点。

2. 单向链表基本操作

查找——O(n)

publicNodeget(intindex){Nodecurrent=head;for(inti=0;i<index;i++){if(current==null)thrownewIndexOutOfBoundsException();current=current.next;}returncurrent;}

为什么是 O(n)？链表不是连续的，不能直接算地址，必须从头节点一个一个往后找。

插入——O(1)（已知位置）

// 在 node 节点后面插入一个新节点publicvoidinsertAfter(Nodenode,intdata){NodenewNode=newNode(data);newNode.next=node.next;// 新节点指向 node 的后继node.next=newNode;// node 指向新节点}

插入前： A → B → C ↑ 在A后面插入 插入步骤： 1. newNode.next = A.next → new指向B 2. A.next = newNode → A指向new 结果： A → new → B → C

关键：如果已经有了要插入位置的前驱节点，插入操作本身只需要改两次指针，和表长无关 →O(1)

删除——O(1)（已知前驱）

publicvoiddeleteAfter(Nodenode){if(node.next!=null){node.next=node.next.next;// 跳过要删除的节点}}

四、顺序表 vs 链表的对比

选型建议

频繁按下标访问（查多） → 顺序表（ArrayList） 频繁头尾增删（改多） → 链表（LinkedList） 实际开发中：ArrayList 用得更普遍，因为查询的需求远多于插入删除。

五、408 考研常见考题

题1：顺序表插入的平均移动次数

在长度为 n 的顺序表中插入一个元素，平均需要移动多少个元素？ 在位置 0 插入 → 移动 n 个 在位置 1 插入 → 移动 n-1 个 ... 在位置 n 插入 → 移动 0 个 平均移动次数 = (0 + 1 + 2 + ... + n) / (n+1) = n/2

答案：平均移动n/2个元素。

题2：链表插入的时间复杂度

在单链表的第 i 个位置插入一个节点，时间复杂度是多少？ 注意：插入操作本身是 O(1)，但找到第 i 个位置需要 O(n) 所以总的时间复杂度是 O(n)

题3：手写链表反转

publicNodereverse(Nodehead){Nodeprev=null;Nodecurrent=head;while(current!=null){Nodenext=current.next;// 先存下一个节点current.next=prev;// 指向前一个prev=current;// prev 后移current=next;// current 后移}returnprev;// prev 是新的头节点}

过程图解：

初始： 1 → 2 → 3 → 4 → null 第1步： null ← 1 2 → 3 → 4 → null prev current 第2步： null ← 1 ← 2 3 → 4 → null prev current 第3步： null ← 1 ← 2 ← 3 4 → null prev current 第4步： null ← 1 ← 2 ← 3 ← 4 prev current→null 结果： 4 → 3 → 2 → 1 → null

这道题面试和考研都很经典，建议能手写出来。

六、Java 中对应的集合类

// 顺序表（基于数组）List<String>arrayList=newArrayList<>();arrayList.add("A");// 尾部添加 O(1)arrayList.get(0);// 按下标查 O(1)arrayList.add(0,"B");// 头部插入 O(n)// 链表（基于双向链表）List<String>linkedList=newLinkedList<>();linkedList.add("A");// 尾部添加 O(1)linkedList.get(0);// 按下标查 O(n)linkedList.add(0,"B");// 头部插入 O(1)

总结：

线性表 = 排成一排的数据 顺序表 = 连续存放（数组），查得快，改得慢 链表 = 节点通过指针连接，改得快，查得慢

考研重点：顺序表的插入/删除平均移动次数、链表反转、顺序表和链表的复杂度对比。

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！每周更新 Java/Python/爬虫/数据结构 实战干货，不让你白来。