文章目录前置知识指针结构体(struct)typedef内存分类Java视角栈内存Stack堆内存Heap静态区 / 方法区栈 vs 堆 核心区别面试必背线性表线性表的核心定义顺序表链表前置知识指针inta10;// 在内存中开辟一个空间数据值是10int*pa;// p存储的是a的地址#includestdio.hintmain(){inta10;int*pa;printf(a的值 %d\n,a);// 输出10printf(a的地址 %p\n,a);// 输出0x1000(示例)printf(p的值 %p\n,p);// 输出0x1000(和a一样)printf(*p的值 %d\n,*p);// 输出10(通过地址找值)*p20;// 通过指针修改a的值printf(修改后a %d\n,a);// 输出20return0;}// 指针的进阶操作// 指针算术运算用于数组遍历intarr[5]{1,2,3,4,5};int*parr;// p指向数组第一个元素p;// p向后移动一个int的位置4字节printf(%d,*p);// 输出2// 二级指针指向指针的指针inta10;int*pa;int**ppp;// pp存储的是p的地址printf(%d,**pp);// 输出10解引用两次结构体(struct)数据结构中的每个节点通常包含多个信息数据 指针需要用结构体打包。多个变量的集合// 定义结构体structStudent{intid;// 学号charname[20];// 姓名intscore;// 分数};structpoint{intx;inty;};structpointp;p.x5;p.y10;// 创建结构体变量structStudents1;s1.id1001;strcpy(s1.name,张三);s1.score90;// 通过指针访问结构体成员structStudent*ps1;printf(%d,p-id);// 输出1001推荐写法printf(%d,(*p).id);// 输出1001等价写法typedef是为已有的数据类型创建一个 “别名”也叫类型定义并不会创造新的类型只是给现有类型起了一个更简洁、更贴合场景的名字能提升代码的可读性和可维护性。// 使用场景#includestdio.h#includestring.h// 方式1先定义结构体再typedefstructStudent{charname[20];intage;};typedefstructStudentStu;// 给 struct Student 起别名 Stu// 方式2定义结构体的同时typedef更常用typedefstructTeacher{charname[20];floatsalary;}Tch;intmain(){// 等价于 struct Student s1;Stu s1;strcpy(s1.name,张三);s1.age18;printf(学生%s%d岁\n,s1.name,s1.age);// 等价于 struct Teacher t1;Tch t1;strcpy(t1.name,李老师);t1.salary5000.5;printf(老师%s薪资%.1f\n,t1.name,t1.salary);return0;}// Java字符串类型#includestdio.h// 给 char* 起别名 String模拟字符串类型typedefchar*String;intmain(){// 等价于 char* str Hello C;String strHello C;printf(%s\n,str);// 输出Hello Creturn0;}内存分类Java视角栈内存、堆内存、静态区 / 全局区程序运行时内存分成 4 块栈内存Stack堆内存Heap方法区 / 静态区Method Area程序计数器PC 寄存器简单了解栈内存Stack特点自动分配自动释放空间小速度快先进后出后进先出(可以想象成一个箱子先放进去的书后出)每个线程一个栈。存什么基本数据类型变量intlongfloatdoublebooleanchar对象的引用变量如 User user 里的 user方法调用的栈帧inta10;UserusernewUser();// a 存在栈// user 这个引用也存在栈堆内存Heap特点:手动创建、垃圾回收自动释放空间大、速度比栈慢所有线程共享一块堆存什么所有 new 出来的对象数组UserusernewUser();int[]arrnewint[10];// new User() 对象 → 堆// new int[10] 数组 → 堆静态区 / 方法区存什么类信息Classstatic 静态变量常量字符串常量池等staticintcount0;// count 存在静态区。栈 vs 堆 核心区别面试必背特点栈内存堆内存存放内容基本类型、引用变量对象、数组分配 / 释放自动GC 自动回收速度极快较慢空间小大线程线程私有线程共享数据结构栈先进后出无固定结构线性表由n(n)个数据特性相同的元素构成的有限序列称为线性表线性表是数据结构中最基础的线性结构核心特征数据元素有序、一对一相邻像排队一样每个元素只有一个前驱、一个后继。所有线性表的操作都围绕增、删、查、改展开不同实现数组 / 链表效率天差地别。线性表的核心定义本质特征有且仅有一个表头第一个元素无前驱有且仅有一个表尾最后一个元素无后继中间元素唯一前驱 唯一后继顺序排列。顺序表用连续的内存空间存储元素通过下标索引 直接定位元素是线性表的 “数组版实现”。也可以说是用一组连续的内存单元依次存储线性表的各个元素也就是说逻辑上相邻的元素实际的物理存储空间也是连续的。importjava.util.Arrays;// 顺序表动态数组实现publicclassArrayListDemo{// 底层数组存数据privateint[]data;// 当前元素个数privateintsize;// 初始容量privatestaticfinalintDEFAULT_CAPACITY10;// 构造方法初始化publicArrayListDemo(){datanewint[DEFAULT_CAPACITY];size0;}// 1. 新增元素尾部publicvoidadd(intval){// 扩容数组满了就扩容为原来的2倍if(sizedata.length){resize(2*data.length);}data[size]val;}// 2. 指定位置插入元素publicvoidadd(intindex,intval){// 边界校验if(index0||indexsize){thrownewIndexOutOfBoundsException(索引越界);}// 扩容检查if(sizedata.length){resize(2*data.length);}// 元素后移核心耗时点for(intisize;iindex;i--){data[i]data[i-1];}data[index]val;size;}// 3. 删除指定位置元素publicintremove(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException(索引越界);}intremovedValdata[index];// 元素前移核心耗时点for(intiindex;isize-1;i){data[i]data[i1];}size--;// 缩容元素个数 数组容量1/4 时缩容为1/2if(size0sizedata.length/4){resize(data.length/2);}returnremovedVal;}// 4. 查找元素按索引O(1)publicintget(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException(索引越界);}returndata[index];}// 扩容/缩容辅助方法privatevoidresize(intnewCapacity){int[]newDatanewint[newCapacity];// 复制原有元素for(inti0;isize;i){newData[i]data[i];}datanewData;}// 测试publicstaticvoidmain(String[]args){ArrayListDemolistnewArrayListDemo();list.add(1);list.add(2);list.add(1,3);// 在索引1插入3 → [1,3,2]System.out.println(list.get(1));// 输出3list.remove(1);// 删除索引1 → [1,2]System.out.println(Arrays.toString(Arrays.copyOf(list.data,list.size)));// 输出[1,2]}}核心分析优点get(index) 随机访问效率 O (1)直接通过下标定位缺点add(index)/remove(index) 需移动元素效率 O (n)数组容量固定需手动扩容 / 缩容。链表核心原理用非连续的节点存储元素每个节点包含数据 指向下一个节点的指针引用通过指针串联成线性结构。最基础的是单链表还有双向链表、循环链表基于单链表扩展。// 单链表节点类classListNode{intval;ListNodenext;ListNode(intval){this.valval;this.nextnull;}}// 单链表实现publicclassLinkedListDemo{// 头节点哨兵节点简化操作privateListNodedummyHead;// 元素个数privateintsize;// 构造方法publicLinkedListDemo(){dummyHeadnewListNode(0);// 虚拟头节点不用处理头节点为空的情况size0;}// 1. 新增元素尾部publicvoidadd(intval){add(size,val);}// 2. 指定位置插入元素核心不用移动元素publicvoidadd(intindex,intval){if(index0||indexsize){thrownewIndexOutOfBoundsException(索引越界);}// 找到前驱节点ListNodeprevdummyHead;for(inti0;iindex;i){prevprev.next;}// 插入新节点ListNodenewNodenewListNode(val);newNode.nextprev.next;prev.nextnewNode;size;}// 3. 删除指定位置元素publicintremove(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException(索引越界);}// 找到前驱节点ListNodeprevdummyHead;for(inti0;iindex;i){prevprev.next;}ListNoderemovedNodeprev.next;prev.nextremovedNode.next;removedNode.nextnull;// 断开引用方便GCsize--;returnremovedNode.val;}// 4. 查找元素按索引O(n)publicintget(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException(索引越界);}ListNodecurdummyHead.next;for(inti0;iindex;i){curcur.next;}returncur.val;}// 测试publicstaticvoidmain(String[]args){LinkedListDemolistnewLinkedListDemo();list.add(1);list.add(2);list.add(1,3);// 索引1插入3 → 1→3→2System.out.println(list.get(1));// 输出3list.remove(1);// 删除索引1 → 1→2System.out.println(list.get(1));// 输出2}}核心分析优点add(index)/remove(index) 只需修改指针无需移动元素效率 O (1)找前驱节点 O (n)但移动成本为 0容量动态无需扩容缺点get(index) 需从头遍历效率 O (n)额外存储指针占用更多内存。顺序表 vs 链表核心对比面试必背操作顺序表数组单链表随机访问getO (1) 极快O (n) 慢插入 / 删除O (n)移动元素O (1)改指针内存占用连续空间无冗余非连续指针占空间扩容需复制元素有性能损耗无需扩容适用场景读多写少写多读少总结线性表的核心是元素有序、一对一相邻分为顺序表数组和链表两种实现顺序表胜在随机访问快适合查询频繁的场景链表胜在增删快适合插入 / 删除频繁的场景两者的效率差异本质是连续内存下标定位 vs 非连续内存指针串联。