文章目录一、链表LinkedList 的底层1.1 链表的概念与结构特点1.2 链表的常见结构二、LinkedList 的模拟实现1. 接口设计IList2. 自定义异常IndexException3. MySingleList类3.1 基础结构定义3.2 增操作头插、尾插、任意位置插1头插法addFirst2尾插法addLast3任意位置插入addIndex3.3 查操作包含判断与长度统计1包含判断contains2长度统计size3.4 删操作删除单个节点与删除所有节点1删除第一次出现的keyremove2删除所有值为key的节点removeAllKey3.5 其他工具方法1遍历打印display2清空链表clear三、LinkedList 详解3.1 LinkedList 的特性3.2 LinkedList 的构造方法3.3 LinkedList 的常用方法3.4 LinkedList 的遍历方式四、ArrayList 与 LinkedList 的区别一、链表LinkedList 的底层1.1 链表的概念与结构特点链表是一种物理存储结构非连续但逻辑顺序通过节点间引用链接实现的线性数据结构。物理非连续链表的节点在内存中不一定连续每个节点包含数据域和引用域指向其他节点。逻辑连续通过引用域节点之间形成链式关系保证了数据在逻辑上的连续。节点来源现实中链表的节点一般从堆内存中申请两次申请的空间可能连续也可能不连续。1.2 链表的常见结构链表的结构多样通过以下三个维度组合可形成 8 种不同的链表结构单向 / 双向单向链表节点只有一个引用域指向后继节点双向链表节点有两个引用域分别指向前驱和后继节点。带头 / 不带头带头链表有一个头节点不存储实际数据用于简化操作不带头链表直接从存储数据的节点开始。循环 / 非循环循环链表的尾节点引用指向头节点或头节点相关节点形成闭环非循环链表的尾节点引用为 null。在实际应用中我们重点掌握两种结构无头单向非循环链表结构简单一般不单独用于存储数据常作为其他数据结构如哈希桶、图的邻接表的子结构也是笔试面试中的高频考点。无头双向循环链表Java 中 LinkedList 的底层实现就是这种结构能兼顾插入、删除和查询操作的性能。二、LinkedList 的模拟实现LinkedList 基于无头双向循环链表实现以下是其核心操作的模拟实现框架1. 接口设计IListpublicinterfaceIList{// 初始化链表创建预设节点voidcreateList();// 头插法在链表头部插入数据voidaddFirst(intdata);// 尾插法在链表尾部插入数据voidaddLast(intdata);// 任意位置插入第一个节点为0号下标voidaddIndex(intindex,intdata);// 查找判断关键字key是否存在booleancontains(intkey);// 删除移除第一次出现的key节点voidremove(intkey);// 删除移除所有值为key的节点voidremoveAllKey(intkey);// 统计获取链表长度intsize();// 清空释放链表所有节点voidclear();// 遍历打印链表所有元素voiddisplay();}2. 自定义异常IndexException针对「任意位置插入」时的非法下标负数、超出链表长度自定义运行时异常增强错误提示的可读性。publicclassIndexExceptionextendsRuntimeException{publicIndexException(Stringmessage){super(message);}}3. MySingleList类3.1 基础结构定义内部静态类ListNode封装节点的结构避免对外暴露实现细节成员变量head作为链表的头节点引用。publicclassMySingleListimplementsIList{// 内部静态类链表节点staticclassListNode{publicintval;// 数据域publicListNodenext;// 指针域下一个节点引用// 节点构造器初始化数据域publicListNode(intval){this.valval;}}ListNodehead;// 头节点链表的入口}3.2 增操作头插、尾插、任意位置插插入是单链表的核心操作需重点处理「空链表」「头节点插入」等边界情况。1头插法addFirst逻辑新节点的next指向原头节点再将head更新为新节点无论链表是否为空均适用。时间复杂度O(1)无需遍历。OverridepublicvoidaddFirst(intdata){ListNodenewNodenewListNode(data);newNode.nexthead;headnewNode;}2尾插法addLast逻辑先遍历到链表的最后一个节点next null的节点再将其next指向新节点。注意若链表为空head null直接将head指向新节点避免cur.next空指针异常。OverridepublicvoidaddLast(intdata){ListNodenewNodenewListNode(data);// 边界链表为空时直接让head指向新节点if(headnull){headnewNode;return;}// 遍历找到最后一个节点cur.next nullListNodecurhead;while(cur.next!null){curcur.next;}cur.nextnewNode;// 最后一个节点指向新节点}3任意位置插入addIndex核心步骤校验下标合法性index 0或index 链表长度均非法特殊位置复用已有方法index0复用addFirstindex长度复用addLast中间位置先找到index-1处的前驱节点再插入新节点避免断链。OverridepublicvoidaddIndex(intindex,intdata){intlensize();if(index0||indexlen){thrownewIndexException(下标不合法);}// 头插if(index0){addFirst(data);return;}// 尾插if(indexlen){addLast(data);return;}// 中间位置找到index-1的前驱节点ListNodecurhead;for(inti0;iindex-1;i){curcur.next;}// 插入新节点先连后再让前驱连新节点顺序不可反ListNodenewNodenewListNode(data);newNode.nextcur.next;cur.nextnewNode;}关键注意插入顺序必须是「新节点先指向后一个节点」再「前驱节点指向新节点」。若顺序颠倒会导致后一个节点的引用丢失造成链表断链。3.3 查操作包含判断与长度统计1包含判断contains逻辑从head开始遍历所有节点若找到值为key的节点则返回true遍历结束未找到则返回false。时间复杂度O(n)最坏需遍历整个链表。Overridepublicbooleancontains(intkey){ListNodecurhead;while(cur!null){// 遍历终止条件cur为null已到链表末尾if(cur.valkey){returntrue;}curcur.next;}returnfalse;}2长度统计size逻辑遍历链表用计数器累计节点数量。时间复杂度O(n)。Overridepublicintsize(){intcnt0;ListNodecurhead;while(cur!null){cnt;curcur.next;}returncnt;}3.4 删操作删除单个节点与删除所有节点删除操作的核心是「找到待删节点的前驱节点」通过修改前驱节点的next引用跳过待删节点实现节点移除。1删除第一次出现的keyremove核心步骤边界1链表为空直接返回边界2头节点就是待删节点直接将head指向head.next常规情况通过辅助方法findListNode找到待删节点的前驱修改前驱的next引用。// 辅助方法找到值为key的节点的前驱若未找到返回nullListNodefindListNode(intkey){ListNodecurhead;// 遍历判断cur的下一个节点是否为待删节点while(cur.next!null){if(cur.next.valkey){returncur;}curcur.next;}returnnull;}Overridepublicvoidremove(intkey){// 链表为空if(headnull){return;}// 头节点为待删节点if(head.valkey){headhead.next;return;}// 找到前驱节点ListNodecurfindListNode(key);if(curnull){// 未找到待删节点return;}// 前驱节点跳过待删节点ListNodedelcur.next;cur.nextdel.next;}2删除所有值为key的节点removeAllKey优化思路用「双指针遍历」一次完成所有删除避免多次遍历效率更高prev指向当前节点的前驱初始为headcur指向当前遍历的节点初始为head.next。逻辑先处理非头节点的待删节点通过双指针跳过所有valkey的节点最后处理头节点若头节点valkey更新head。OverridepublicvoidremoveAllKey(intkey){// 边界链表为空if(headnull){return;}ListNodeprevhead;ListNodecurhead.next;// 处理非头节点的待删节点while(cur!null){if(cur.valkey){// 待删节点prev跳过curcur后移prev.nextcur.next;curcur.next;}else{// 非待删节点双指针同时后移prevcur;curcur.next;}}// 处理头节点若头节点值为keyif(head.valkey){headhead.next;}}3.5 其他工具方法1遍历打印display从head开始遍历打印每个节点的值直观展示链表内容。Overridepublicvoiddisplay(){ListNodecurhead;while(cur!null){System.out.print(cur.val );curcur.next;}System.out.println( );}2清空链表clear逻辑逐个断开节点的next引用避免内存泄漏最后将head置为null。注意若直接将head null未断开的节点引用可能导致JVM无法回收内存。Overridepublicvoidclear(){// 边界链表为空if(headnull){return;}ListNodecurhead.next;ListNodecurNext;// 逐个断开节点的next引用while(cur!null){curNextcur.next;// 先保存下一个节点cur.nextnull;// 断开当前节点的引用curcurNext;// 移到下一个节点}headnull;// 头节点置空链表彻底为空}三、LinkedList 详解3.1 LinkedList 的特性底层基于无头双向循环链表实现节点间通过引用关联无需连续存储空间。实现了 List 接口支持 List 接口的所有操作。未实现 RandomAccess 接口不支持随机访问即不能通过下标快速定位元素需从头或尾遍历。任意位置插入和删除元素时只需修改节点引用时间复杂度为O(1)找到目标位置需 O(n)但修改操作本身是 O(1)。无“容量”概念无需像 ArrayList 那样进行扩容。3.2 LinkedList 的构造方法LinkedList 提供两种常用构造方法方法解释LinkedList()无参构造创建一个空的 LinkedListLinkedList(Collection? extends E c)使用其他集合如 ArrayList中的元素构造 LinkedList使用示例publicstaticvoidmain(String[]args){// 构造空的 LinkedListListIntegerlist1newLinkedList();// 先创建 ArrayList 并添加元素ListStringlist2newArrayList();list2.add(JavaSE);list2.add(JavaWeb);list2.add(JavaEE);// 使用 ArrayList 构造 LinkedListListStringlist3newLinkedList(list2);}3.3 LinkedList 的常用方法LinkedList 提供了丰富的方法用于操作元素以下是核心方法方法解释boolean add(E e)尾插元素 evoid add(int index, E element)在 index 位置插入元素 elementboolean addAll(Collection? extends E c)尾插集合 c 中的所有元素E remove(int index)删除 index 位置的元素返回被删除的元素boolean remove(Object o)删除遇到的第一个元素 o返回是否删除成功E get(int index)获取 index 位置的元素E set(int index, E element)将 index 位置的元素设为 element返回原元素void clear()清空链表boolean contains(Object o)判断元素 o 是否在链表中int indexOf(Object o)返回第一个元素 o 的下标若不存在返回 -1int lastIndexOf(Object o)返回最后一个元素 o 的下标若不存在返回 -1ListE subList(int fromIndex, int toIndex)截取 [fromIndex, toIndex) 区间的元素返回新的 List使用示例publicstaticvoidmain(String[]args){LinkedListIntegerlistnewLinkedList();// 尾插元素list.add(1);list.add(2);list.add(3);System.out.println(初始链表list);// 输出[1, 2, 3]System.out.println(链表长度list.size());// 输出3// 在 index0 位置插入元素 0list.add(0,0);System.out.println(插入后链表list);// 输出[0, 1, 2, 3]// 删除操作list.remove();// 默认删除第一个元素调用 removeFirst()list.removeLast();// 删除最后一个元素System.out.println(删除后链表list);// 输出[1, 2]// 判断元素是否存在if(!list.contains(0)){list.add(0,0);}System.out.println(添加后链表list);// 输出[0, 1, 2]// 查找元素下标System.out.println(第一个 0 的下标list.indexOf(0));// 输出0// 修改元素list.set(0,100);System.out.println(修改后链表list);// 输出[100, 1, 2]// 截取子链表ListIntegersubListlist.subList(0,2);System.out.println(子链表subList);// 输出[100, 1]// 清空链表list.clear();System.out.println(清空后链表长度list.size());// 输出0}3.4 LinkedList 的遍历方式LinkedList 支持三种常见的遍历方式foreach 遍历简洁直观适用于无需修改元素的场景。迭代器遍历支持正向和反向遍历且在遍历过程中可安全修改元素通过迭代器的remove()方法。普通 for 循环遍历由于 LinkedList 不支持随机访问通过下标获取元素会从头/尾遍历效率较低不推荐。遍历示例publicstaticvoidmain(String[]args){LinkedListIntegerlistnewLinkedList();list.add(1);list.add(2);list.add(3);list.add(4);// 1. foreach 遍历for(inte:list){System.out.print(e );}System.out.println();// 1 2 3 4// 2. 迭代器正向遍历ListIteratorIntegeritlist.listIterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();// 1 2 3 4// 3. 迭代器反向遍历ListIteratorIntegerritlist.listIterator(list.size());while(rit.hasPrevious()){System.out.print(rit.previous() );}System.out.println();// 4 3 2 1}四、ArrayList 与 LinkedList 的区别对比维度ArrayListLinkedList存储空间物理上一定连续基于数组逻辑上连续物理上不一定连续基于链表随机访问支持时间复杂度O(1)通过数组下标直接访问不支持时间复杂度O(n)需从头/尾遍历头插操作需搬移所有元素时间复杂度O(n)只需修改节点引用时间复杂度O(1)插入操作空间不足时需扩容默认扩容为原容量的 1.5 倍可能浪费内存无容量概念无需扩容插入时直接创建节点尾插操作若无需扩容时间复杂度O(1)若需扩容时间复杂度O(n)时间复杂度O(1)直接找到尾节点修改引用删除操作需搬移后续元素时间复杂度O(n)找到目标节点后修改引用即可时间复杂度O(1)查找过程 O(n)内存占用可能存在内存浪费扩容后未使用的空间每个节点需额外存储前驱/后继引用内存开销略大应用场景元素存储稳定频繁进行查询操作元素频繁进行任意位置插入/删除操作