自定义LinkList

单链表 LinkList 实现原理与深度解析一、链表简介在Java中除了常用的 ArrayList 动态数组外 LinkedList 链表也是使用非常频繁的数据结构。链表和数组各有优劣掌握链表的实现原理对于深入理解数据结构和算法至关重要。二、设计思路总览2.1 链表的核心结构[头节点root] → [节点1] → [节点2] → [节点3] → ... → [尾节点last] → null核心概念节点Node 链表的基本单元包含数据域和指针域头节点root 哨兵节点不存储数据简化边界操作尾节点last 记录链表尾部支持O(1)的尾部添加size 记录链表元素个数无需遍历计数2.2 类结构设计publicclassLinkListE{// 内部节点类classNode{Edata;// 数据域Nodenext;// 指针域指向下一个节点Node(Edata){this.datadata;}Node(){}}privateNoderoot;// 头节点哨兵privateNodelast;// 尾节点privateintsize0;// 元素个数}三、核心功能实现解析3.1 构造函数 - 初始化publicLinkList(){rootnewNode();// 创建哨兵头节点}设计思路 使用哨兵头节点不存储数据的好处避免空指针异常root永远不为null统一头部和中间插入的逻辑代码更简洁边界条件更少3.2 添加元素 - add(E data)publicvoidadd(Edata){NodenodenewNode(data);Nodeheadroot.next;if(headnull){// 链表为空时root.nextnode;lastnode;}else{// 链表非空时在尾部添加last.nextnode;lastnode;}size;}时间复杂度 O(1)实现原理 创建新节点判断链表是否为空空链表root.next直接指向新节点非空链表last.next指向新节点更新lastsize关键优化 使用 last 指针记录尾部避免每次添加都遍历到末尾3.3 插入元素 - inset(int index, E data)publicvoidinset(intindex,Edata){// 1. 边界检查if(index0||indexsize){System.out.println(index越界);return;}NodenewdatanewNode(data);Nodecurroot.next;// 2. 头部插入if(index0){newdata.nextcur;root.nextnewdata;size;return;}// 3. 找到插入位置的前一个节点for(inti0;iindex-1;i){curcur.next;}// 4. 执行插入Nodeprecur;curcur.next;pre.nextnewdata;newdata.nextcur;size;}时间复杂度 O(n)插入示意图 插入前: [A] → [B] → [C] 插入位置: index1在B之前插入X Step 1: 找到前一个节点A Step 2: X.next B Step 3: A.next X 插入后: [A] → [X] → [B] → [C]3.4 按索引删除 - remove(int index)publicEremove(intindex){// 1. 边界检查if(index0||indexsize){System.out.println(index越界);}Nodecurroot.next;// 2. 找到删除位置的前一个节点for(inti0;iindex-1;i){curcur.next;}// 3. 执行删除Nodeprecur;curcur.next;pre.nextcur.next;// 跳过要删除的节点size--;return(E)cur.data;}时间复杂度 O(n)删除示意图 删除前: [A] → [X] → [B] → [C] 删除位置: index1删除X Step 1: 找到前一个节点A Step 2: A.next B 删除后: [A] → [B] → [C] X 被断开等待GC回收3.5 按值删除第一个 - removes(E data)publicbooleanremoves(Edata){Nodecurroot.next;// 1. 检查是否是第一个节点if(cur.data.equals(data)){root.nextcur.next;size--;returntrue;}// 2. 遍历查找for(inti0;isize-1;i){if(cur.next.data.equals(data)){Nodeprecur;curcur.next;pre.nextcur.next;size--;returntrue;}curcur.next;}returnfalse;}时间复杂度 O(n)3.6 删除所有匹配值 - removeAll(E data)publicbooleanremoveAll(Edata){// 1. 处理头部连续匹配Nodecurroot.next;if(cur.data.equals(data)){root.nextcur.next;size--;}// 2. 遍历处理中间和尾部Nodepreroot;while(pre.next!null){if(pre.next.data.equals(data)){curpre.next;pre.nextcur.next;size--;}else{prepre.next;}}returntrue;}实现技巧 使用pre指针从root开始遍历避免处理头部的特殊逻辑3.7 获取元素 - get(int index)publicEget(intindex){Nodecurroot.next;for(inti0;iindex;i){curcur.next;}return(E)cur.data;}时间复杂度 O(n)与ArrayList对比 ArrayList通过索引直接计算内存地址get时间复杂度为O(1)链表需要从头遍历四、完整实现代码publicclassLinkListE{classNode{Edata;Nodenext;publicNode(Edata){this.datadata;}publicNode(){}}privateNoderoot;privateNodelast;privateintsize0;publicLinkList(){rootnewNode();}publicvoidadd(Edata){NodenodenewNode(data);Nodeheadroot.next;if(headnull){root.nextnode;lastnode;}else{last.nextnode;lastnode;}size;}publicvoidinset(intindex,Edata){if(index0||indexsize){System.out.println(index越界);return;}NodenewdatanewNode(data);Nodecurroot.next;if(index0){newdata.nextcur;root.nextnewdata;size;return;}for(inti0;iindex-1;i){curcur.next;}Nodeprecur;curcur.next;pre.nextnewdata;newdata.nextcur;size;}publicEremove(intindex){if(index0||indexsize){System.out.println(index越界);}Nodecurroot.next;for(inti0;iindex-1;i){curcur.next;}Nodeprecur;curcur.next;pre.nextcur.next;size--;return(E)cur.data;}publicbooleanremoves(Edata){Nodecurroot.next;if(cur.data.equals(data)){root.nextcur.next;size--;returntrue;}for(inti0;isize-1;i){if(cur.next.data.equals(data)){Nodeprecur;curcur.next;pre.nextcur.next;size--;returntrue;}curcur.next;}returnfalse;}publicbooleanremoveAll(Edata){Nodecurroot.next;if(cur.data.equals(data)){root.nextcur.next;size--;}Nodepreroot;while(pre.next!null){if(pre.next.data.equals(data)){curpre.next;pre.nextcur.next;size--;}else{prepre.next;}}returntrue;}publicEget(intindex){Nodecurroot.next;for(inti0;iindex;i){curcur.next;}return(E)cur.data;}publicintsize(){returnsize;}}}五、应用场景5.1 链表适用场景需要频繁在 头部或尾部 插入/删除元素实现 栈 或 队列 LinkedList天然支持LRU缓存 等需要频繁调整顺序的场景元素数量 不确定 且需要动态增长5.2 链表不适用场景需要频繁 随机访问 ArrayList更优内存空间 紧张 链表每个节点有额外指针开销元素数量 固定 数组更合适5.3 实际应用示例// 场景1实现栈LinkListIntegerstacknewLinkList();stack.add(1);// 入栈 O(1)stack.remove(stack.size()-1);// 出栈 O(n) - 可以优化为O(1)// 场景2实现队列LinkListIntegerqueuenewLinkList();queue.add(1);// 入队 O(1)queue.remove(0);// 出队 O(n) - 可以优化为O(1)六、常见问题与注意事项6.1 空指针异常NPE问题 在空链表上调用remove/removeAll/get可能抛出NPE解决方案 添加空链表检查publicEremove(intindex){if(size0){thrownewIllegalStateException(链表为空);}// ...}6.2 内存泄漏问题 删除节点后节点引用仍可能被持有解决方案 Java有垃圾回收GC删除后没有引用会自动回收无需手动处理七、总结通过实现这个 LinkList 单链表我们深入理解了链表的核心原理节点结构 数据域 指针域哨兵头节点 简化边界操作尾指针优化 O(1)的尾部添加指针操作 插入删除只修改指针不移动数据性能权衡 随机访问慢但插入删除快链表和数组是数据结构的两大基石掌握它们的实现原理和性能特点能够帮助我们在实际开发中选择更合适的数据结构。