本文整理 Java 集合框架中LinkedList 与链表的核心内容ArrayList 在任意位置增删的缺陷、链表的八种结构组合、无头单向/双向链表的实现骨架、十道经典链表 OJ 题含快慢指针判环与入环点结论、LinkedList 的常用方法与三种遍历方式,以及它和 ArrayList 的选型对比。本节目标ArrayList 的缺陷链表链表相关 OJLinkedList 的模拟实现LinkedList 的使用ArrayList 和 LinkedList 的区别一、ArrayList 的缺陷上节课已经熟悉了 ArrayList 的使用,并且进行了简单模拟实现。通过源码知道,ArrayList 底层使用数组来存储元素。由于其底层是一段连续空间,当在 ArrayList 任意位置插入或者删除元素时,就需要将后续元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低。因此 ArrayList 不适合做任意位置插入和删除比较多的场景。所以 Java 集合中又引入了 LinkedList,即链表结构。二、链表2.1 链表的概念及结构链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。实际中链表的结构非常多样,以下情况组合起来就有8 种链表结构:单向或者双向带头或者不带头循环或者非循环虽然有这么多的链表结构,但是我们重点掌握两种:无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。无头双向链表:在 Java 的集合框架库中,LinkedList 底层实现就是无头双向循环链表。2.2 链表的实现下面是无头单向非循环链表的接口骨架,方法体留空,适合作为自己动手实现链表的练习:// 1、无头单向非循环链表实现publicclassSingleLinkedList{// 头插法publicvoidaddFirst(intdata){}// 尾插法publicvoidaddLast(intdata){}// 任意位置插入,第一个数据节点为 0 号下标publicvoidaddIndex(intindex,intdata){}// 查找是否包含关键字 key 是否在单链表当中publicbooleancontains(intkey){returnfalse;}// 删除第一次出现关键字为 key 的节点publicvoidremove(intkey){}// 删除所有值为 key 的节点publicvoidremoveAllKey(intkey){}// 得到单链表的长度publicintsize(){return-1;}publicvoidclear(){}publicvoiddisplay(){}}三、链表面试题以下是经典的链表 OJ 题清单,建议在牛客网和力扣上依次做一遍:删除链表中等于给定值 val 的所有节点反转一个单链表给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点输入一个链表,输出该链表中倒数第 k 个结点将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的编写代码,以给定值 x 为基准将链表分割成两部分,所有小于 x 的结点排在大于或等于 x 的结点之前链表的回文结构输入两个链表,找出它们的第一个公共结点给定一个链表,判断链表中是否有环给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 NULL3.1 判断链表是否有环:快慢指针【思路】快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行。如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。【扩展问题一】为什么快指针每次走两步,慢指针走一步可以?假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了;最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况。因此:在慢指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。【扩展问题二】快指针一次走 3 步、走 4 步…… 走 n 步行吗?提示:关键看快慢指针的相对速度能否整除环长。快指针走 3 步时,两者每轮距离缩小 2 步,如果环长是偶数就可能出现每次都恰好跨过的情况,无法保证相遇。这也是为什么标准解法选走两步。3.2 返回入环的第一个节点【结论】让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。直观理解:设头结点到入环点距离为a,入环点到相遇点距离为b,相遇点绕回入环点距离为c。相遇时快指针走了a b n(b c),慢指针走了a b,由快指针路程是慢指针两倍可推出a c (n-1)(bc),即从头和从相遇点同步出发,必在入环点相遇。四、LinkedList 的模拟实现下面是无头双向链表的接口骨架:// 2、无头双向链表实现publicclassMyLinkedList{// 头插法publicvoidaddFirst(intdata){}// 尾插法publicvoidaddLast(intdata){}// 任意位置插入,第一个数据节点为 0 号下标publicvoidaddIndex(intindex,intdata){}// 查找是否包含关键字 key 是否在单链表当中publicbooleancontains(intkey){}// 删除第一次出现关键字为 key 的节点publicvoidremove(intkey){}// 删除所有值为 key 的节点publicvoidremoveAllKey(intkey){}// 得到单链表的长度publicintsize(){}publicvoiddisplay(){}publicvoidclear(){}}五、LinkedList 的使用5.1 什么是 LinkedListLinkedList 的底层是双向链表结构。由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。在集合框架中,LinkedList 也实现了 List 接口。【说明】LinkedList 实现了 List 接口LinkedList 的底层使用了双向链表LinkedList没有实现 RandomAccess 接口,因此 LinkedList不支持随机访问LinkedList 的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)LinkedList 比较适合任意位置插入的场景5.2 LinkedList 的使用1. LinkedList 的构造publicstaticvoidmain(String[]args){// 构造一个空的 LinkedListListIntegerlist1newLinkedList();ListStringlist2newjava.util.ArrayList();list2.add(JavaSE);list2.add(JavaWeb);list2.add(JavaEE);// 使用 ArrayList 构造 LinkedListListStringlist3newLinkedList(list2);}2. LinkedList 的其他常用方法介绍publicstaticvoidmain(String[]args){LinkedListIntegerlistnewLinkedList();list.add(1);// add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入 0list.add(0,0);// add(index, elem): 在 index 位置插入元素 elemSystem.out.println(list);list.remove();// remove(): 删除第一个元素,内部调用的是 removeFirst()list.removeFirst();// removeFirst(): 删除第一个元素list.removeLast();// removeLast(): 删除最后一个元素list.remove(1);// remove(index): 删除 index 位置的元素System.out.println(list);// contains(elem): 检测 elem 元素是否存在,如果存在返回 true,否则返回 falseif(!list.contains(1)){list.add(0,1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1));// indexOf(elem): 从前往后找到第一个 elem 的位置System.out.println(list.lastIndexOf(1));// lastIndexOf(elem): 从后往前找第一个 1 的位置intelemlist.get(0);// get(index): 获取指定位置元素list.set(0,100);// set(index, elem): 将 index 位置的元素设置为 elemSystem.out.println(list);// subList(from, to): 用 list 中 [from, to) 之间的元素构造一个新的 LinkedList 返回ListIntegercopylist.subList(0,3);System.out.println(list);System.out.println(copy);list.clear();// 将 list 中元素清空System.out.println(list.size());}⚠️ 一个高频踩坑点:上面list.remove(1)删除的是下标 1的元素,不是值为 1 的元素。因为LinkedListInteger同时存在remove(int index)和remove(Object o)两个重载,传入的1是int字面量,会优先匹配remove(int index)。想删除值为 1 的元素必须显式装箱:list.remove(Integer.valueOf(1))。3. LinkedList 的遍历publicstaticvoidmain(String[]args){LinkedListIntegerlistnewLinkedList();list.add(1);// add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());// foreach 遍历for(inte:list){System.out.print(e );}System.out.println();// 使用迭代器遍历 --- 正向遍历ListIteratorIntegeritlist.listIterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();// 使用反向迭代器 --- 反向遍历ListIteratorIntegerritlist.listIterator(list.size());while(rit.hasPrevious()){System.out.print(rit.previous() );}System.out.println();}六、ArrayList 和 LinkedList 的区别讲义在本节只给出了标题,下面的对比表为补充整理。维度ArrayListLinkedList底层结构动态数组,一段连续空间双向链表,节点之间靠引用连接随机访问支持,实现 RandomAccess,get(i)为 O(1)不支持,get(i)需要遍历,为 O(n)头插 / 任意位置插入需要搬移元素,平均 O(n)只需改动引用,为 O(1)尾插均摊 O(1),扩容时需拷贝O(1)删除元素需要搬移元素,平均 O(n)找到节点后为 O(1),但按下标找仍是 O(n)内存开销有扩容冗余空间,可能浪费每个节点多存前后引用,空间开销更大适用场景频繁随机访问、尾部增删频繁在任意位置插入删除选型口诀:查多改少用 ArrayList,增删频繁(尤其头尾之外)用 LinkedList。七、小结ArrayList 的缺陷:底层是连续数组,任意位置增删要搬移元素,时间复杂度 O(n)。链表:物理上非连续,靠引用连接;组合起来共 8 种结构,重点是无头单向非循环和无头双向。LinkedList 的底层:无头双向循环链表,实现了 List,但没有实现 RandomAccess,不支持随机访问。判环:快慢指针,慢指针走 1 步、快指针走 2 步,带环必定相遇。入环点:一个指针从头出发,另一个从相遇点出发,同步每次走一步,必在入环点相遇。易错点:list.remove(1)删的是下标 1,不是值为 1 的元素。本文整理自课程讲义《6. LinkedList 与链表》,代码已重新排版并做了少量勘误与补充说明,仅供个人学习记录使用。
本文整理 Java 集合框架中LinkedList 与链表的核心内容ArrayList 在任意位置增删的缺陷、链表的八种结构组合、无头单向/双向链表的实现骨架、十道经典链表 OJ 题含快慢指针判环与入环点结论、LinkedList 的常用方法与三种遍历方式,以及它和 ArrayList 的选型对比。本节目标ArrayList 的缺陷链表链表相关 OJLinkedList 的模拟实现LinkedList 的使用ArrayList 和 LinkedList 的区别一、ArrayList 的缺陷上节课已经熟悉了 ArrayList 的使用,并且进行了简单模拟实现。通过源码知道,ArrayList 底层使用数组来存储元素。由于其底层是一段连续空间,当在 ArrayList 任意位置插入或者删除元素时,就需要将后续元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低。因此 ArrayList 不适合做任意位置插入和删除比较多的场景。所以 Java 集合中又引入了 LinkedList,即链表结构。二、链表2.1 链表的概念及结构链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。实际中链表的结构非常多样,以下情况组合起来就有8 种链表结构:单向或者双向带头或者不带头循环或者非循环虽然有这么多的链表结构,但是我们重点掌握两种:无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。无头双向链表:在 Java 的集合框架库中,LinkedList 底层实现就是无头双向循环链表。2.2 链表的实现下面是无头单向非循环链表的接口骨架,方法体留空,适合作为自己动手实现链表的练习:// 1、无头单向非循环链表实现publicclassSingleLinkedList{// 头插法publicvoidaddFirst(intdata){}// 尾插法publicvoidaddLast(intdata){}// 任意位置插入,第一个数据节点为 0 号下标publicvoidaddIndex(intindex,intdata){}// 查找是否包含关键字 key 是否在单链表当中publicbooleancontains(intkey){returnfalse;}// 删除第一次出现关键字为 key 的节点publicvoidremove(intkey){}// 删除所有值为 key 的节点publicvoidremoveAllKey(intkey){}// 得到单链表的长度publicintsize(){return-1;}publicvoidclear(){}publicvoiddisplay(){}}三、链表面试题以下是经典的链表 OJ 题清单,建议在牛客网和力扣上依次做一遍:删除链表中等于给定值 val 的所有节点反转一个单链表给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点输入一个链表,输出该链表中倒数第 k 个结点将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的编写代码,以给定值 x 为基准将链表分割成两部分,所有小于 x 的结点排在大于或等于 x 的结点之前链表的回文结构输入两个链表,找出它们的第一个公共结点给定一个链表,判断链表中是否有环给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 NULL3.1 判断链表是否有环:快慢指针【思路】快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行。如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。【扩展问题一】为什么快指针每次走两步,慢指针走一步可以?假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了;最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况。因此:在慢指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。【扩展问题二】快指针一次走 3 步、走 4 步…… 走 n 步行吗?提示:关键看快慢指针的相对速度能否整除环长。快指针走 3 步时,两者每轮距离缩小 2 步,如果环长是偶数就可能出现每次都恰好跨过的情况,无法保证相遇。这也是为什么标准解法选走两步。3.2 返回入环的第一个节点【结论】让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。直观理解:设头结点到入环点距离为a,入环点到相遇点距离为b,相遇点绕回入环点距离为c。相遇时快指针走了a b n(b c),慢指针走了a b,由快指针路程是慢指针两倍可推出a c (n-1)(bc),即从头和从相遇点同步出发,必在入环点相遇。四、LinkedList 的模拟实现下面是无头双向链表的接口骨架:// 2、无头双向链表实现publicclassMyLinkedList{// 头插法publicvoidaddFirst(intdata){}// 尾插法publicvoidaddLast(intdata){}// 任意位置插入,第一个数据节点为 0 号下标publicvoidaddIndex(intindex,intdata){}// 查找是否包含关键字 key 是否在单链表当中publicbooleancontains(intkey){}// 删除第一次出现关键字为 key 的节点publicvoidremove(intkey){}// 删除所有值为 key 的节点publicvoidremoveAllKey(intkey){}// 得到单链表的长度publicintsize(){}publicvoiddisplay(){}publicvoidclear(){}}五、LinkedList 的使用5.1 什么是 LinkedListLinkedList 的底层是双向链表结构。由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。在集合框架中,LinkedList 也实现了 List 接口。【说明】LinkedList 实现了 List 接口LinkedList 的底层使用了双向链表LinkedList没有实现 RandomAccess 接口,因此 LinkedList不支持随机访问LinkedList 的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)LinkedList 比较适合任意位置插入的场景5.2 LinkedList 的使用1. LinkedList 的构造publicstaticvoidmain(String[]args){// 构造一个空的 LinkedListListIntegerlist1newLinkedList();ListStringlist2newjava.util.ArrayList();list2.add(JavaSE);list2.add(JavaWeb);list2.add(JavaEE);// 使用 ArrayList 构造 LinkedListListStringlist3newLinkedList(list2);}2. LinkedList 的其他常用方法介绍publicstaticvoidmain(String[]args){LinkedListIntegerlistnewLinkedList();list.add(1);// add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入 0list.add(0,0);// add(index, elem): 在 index 位置插入元素 elemSystem.out.println(list);list.remove();// remove(): 删除第一个元素,内部调用的是 removeFirst()list.removeFirst();// removeFirst(): 删除第一个元素list.removeLast();// removeLast(): 删除最后一个元素list.remove(1);// remove(index): 删除 index 位置的元素System.out.println(list);// contains(elem): 检测 elem 元素是否存在,如果存在返回 true,否则返回 falseif(!list.contains(1)){list.add(0,1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1));// indexOf(elem): 从前往后找到第一个 elem 的位置System.out.println(list.lastIndexOf(1));// lastIndexOf(elem): 从后往前找第一个 1 的位置intelemlist.get(0);// get(index): 获取指定位置元素list.set(0,100);// set(index, elem): 将 index 位置的元素设置为 elemSystem.out.println(list);// subList(from, to): 用 list 中 [from, to) 之间的元素构造一个新的 LinkedList 返回ListIntegercopylist.subList(0,3);System.out.println(list);System.out.println(copy);list.clear();// 将 list 中元素清空System.out.println(list.size());}⚠️ 一个高频踩坑点:上面list.remove(1)删除的是下标 1的元素,不是值为 1 的元素。因为LinkedListInteger同时存在remove(int index)和remove(Object o)两个重载,传入的1是int字面量,会优先匹配remove(int index)。想删除值为 1 的元素必须显式装箱:list.remove(Integer.valueOf(1))。3. LinkedList 的遍历publicstaticvoidmain(String[]args){LinkedListIntegerlistnewLinkedList();list.add(1);// add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());// foreach 遍历for(inte:list){System.out.print(e );}System.out.println();// 使用迭代器遍历 --- 正向遍历ListIteratorIntegeritlist.listIterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();// 使用反向迭代器 --- 反向遍历ListIteratorIntegerritlist.listIterator(list.size());while(rit.hasPrevious()){System.out.print(rit.previous() );}System.out.println();}六、ArrayList 和 LinkedList 的区别讲义在本节只给出了标题,下面的对比表为补充整理。维度ArrayListLinkedList底层结构动态数组,一段连续空间双向链表,节点之间靠引用连接随机访问支持,实现 RandomAccess,get(i)为 O(1)不支持,get(i)需要遍历,为 O(n)头插 / 任意位置插入需要搬移元素,平均 O(n)只需改动引用,为 O(1)尾插均摊 O(1),扩容时需拷贝O(1)删除元素需要搬移元素,平均 O(n)找到节点后为 O(1),但按下标找仍是 O(n)内存开销有扩容冗余空间,可能浪费每个节点多存前后引用,空间开销更大适用场景频繁随机访问、尾部增删频繁在任意位置插入删除选型口诀:查多改少用 ArrayList,增删频繁(尤其头尾之外)用 LinkedList。七、小结ArrayList 的缺陷:底层是连续数组,任意位置增删要搬移元素,时间复杂度 O(n)。链表:物理上非连续,靠引用连接;组合起来共 8 种结构,重点是无头单向非循环和无头双向。LinkedList 的底层:无头双向循环链表,实现了 List,但没有实现 RandomAccess,不支持随机访问。判环:快慢指针,慢指针走 1 步、快指针走 2 步,带环必定相遇。入环点:一个指针从头出发,另一个从相遇点出发,同步每次走一步,必在入环点相遇。易错点:list.remove(1)删的是下标 1,不是值为 1 的元素。本文整理自课程讲义《6. LinkedList 与链表》,代码已重新排版并做了少量勘误与补充说明,仅供个人学习记录使用。
