数据结构是计算机专业的核心基础课也是 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顺序表的三个核心属性publicclassArrayListE{privateObject[]data;// 存储数据的数组privateintsize;// 当前元素个数privateintcapacity;// 数组总容量 data.length}2. 顺序表的基本操作查找随机访问——O(1)// 按下标访问直接通过地址偏移计算publicEget(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException();}return(E)data[index];}为什么是 O(1)数组在内存中是连续存储的data[i]的地址 起始地址 i × 每个元素大小。一步就能定位。插入——O(n)// 在指定位置插入元素publicvoidadd(intindex,Eelement){// 1. 检查下标范围if(index0||indexsize)thrownewIndexOutOfBoundsException();// 2. 检查容量是否够不够就扩容if(sizedata.length){grow();// 扩容为原来的 1.5 倍}// 3. 将 index 及以后的元素后移一位这是最耗时的for(intisize;iindex;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(index0||indexsize)thrownewIndexOutOfBoundsException();EoldValue(E)data[index];// 将 index 后面的元素前移for(intiindex;isize-1;i){data[i]data[i1];}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){Nodecurrenthead;for(inti0;iindex;i){if(currentnull)thrownewIndexOutOfBoundsException();currentcurrent.next;}returncurrent;}为什么是 O(n)链表不是连续的不能直接算地址必须从头节点一个一个往后找。插入——O(1)已知位置// 在 node 节点后面插入一个新节点publicvoidinsertAfter(Nodenode,intdata){NodenewNodenewNode(data);newNode.nextnode.next;// 新节点指向 node 的后继node.nextnewNode;// 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.nextnode.next.next;// 跳过要删除的节点}}四、顺序表 vs 链表的对比操作顺序表ArrayList链表LinkedList按下标访问O(1) 直接算地址O(n) 从头遍历头部插入O(n) 所有元素后移O(1) 改头指针尾部插入O(1)不需要扩容时O(n) 找到尾部再插中间插入O(n) 移动元素O(1)已知前驱时头部删除O(n) 所有元素前移O(1) 改头指针尾部删除O(1) 直接删O(1) 双向链表 / O(n) 单向内存占用连续空间省内存每个节点多存一个指针内存分配一次性分配动态分配按需创建选型建议频繁按下标访问查多 → 顺序表ArrayList 频繁头尾增删改多 → 链表LinkedList 实际开发中ArrayList 用得更普遍因为查询的需求远多于插入删除。五、408 考研常见考题题1顺序表插入的平均移动次数在长度为 n 的顺序表中插入一个元素平均需要移动多少个元素 在位置 0 插入 → 移动 n 个 在位置 1 插入 → 移动 n-1 个 ... 在位置 n 插入 → 移动 0 个 平均移动次数 (0 1 2 ... n) / (n1) n/2答案平均移动n/2个元素。题2链表插入的时间复杂度在单链表的第 i 个位置插入一个节点时间复杂度是多少 注意插入操作本身是 O(1)但找到第 i 个位置需要 O(n) 所以总的时间复杂度是 O(n)题3手写链表反转publicNodereverse(Nodehead){Nodeprevnull;Nodecurrenthead;while(current!null){Nodenextcurrent.next;// 先存下一个节点current.nextprev;// 指向前一个prevcurrent;// prev 后移currentnext;// 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 中对应的集合类// 顺序表基于数组ListStringarrayListnewArrayList();arrayList.add(A);// 尾部添加 O(1)arrayList.get(0);// 按下标查 O(1)arrayList.add(0,B);// 头部插入 O(n)// 链表基于双向链表ListStringlinkedListnewLinkedList();linkedList.add(A);// 尾部添加 O(1)linkedList.get(0);// 按下标查 O(n)linkedList.add(0,B);// 头部插入 O(1)总结线性表 排成一排的数据 顺序表 连续存放数组查得快改得慢 链表 节点通过指针连接改得快查得慢考研重点顺序表的插入/删除平均移动次数、链表反转、顺序表和链表的复杂度对比。 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫/数据结构 实战干货不让你白来。
