阿芬发现，人们在说起链表的时候，往往会说到另一个概念：数组。由于数组和链表经常被放在一起比较。那么今天就来说说数组和链表吧。数组和链表数组最大的特点之一就是需要一块连续的内存空间。假设内存空间还剩余1MB，但不是连续的。这时候如果申请一个大小为1MB的数组，它会告诉你申请失败，因为内存空间不连续。链表最大的特点之一就是不需要连续的内存空间。还是上面的例子，如果申请的不是1MB大小的数组，而是链表，申请成功。如果你只懂这一层，你觉得我以后就只能用链表这种数据结构了吗？不不不，数组也有自己的优势。在查找相关资料时，阿芬发现数组很好用，而且由于使用了连续的内存空间，可以借助CPU的缓存机制提前读取数组中的数据，所以访问效率是更高，所以当插入，删除操作少，查询多的时候，用数组更有优势。链表在内存中不是连续存储的，对CPU缓存机制不够友好，没办法进行有效的预读。所以，链表适合在插入和删除操作比较多的时候使用。链表分为单链表、循环链表和双向链表。对于单向链表，它的第一个节点是记录链表基地址的头节点，最后一个节点是指向空地址NULL的尾节点。循环链表也可以理解为一种特殊的单链表。只是尾节点从指向空地址NULL变成了指向头节点。单链表是这样的：循环链表是这样的：但是在实际开发中，比较常用的链表结构是：双向链表。它的结构是这样的：我们可以看出它的特点是：占用内存大，支持双向遍历。因为它有两个指针，所以一条数据会比单链表占用更多的内存。既然占用内存大，为什么在实际开发中还是普遍使用呢？里面有个思路，具体说一下。我们知道删除单链表和双链表时，时间复杂度是O(1)，但是在实际开发中，它的时间复杂度不是这样的。为什么？这样想，一般在做数据删除的时候，你的操作是什么？先在节点中查找值等于给定值的节点，找到后删除，对不对？也就是说，在删除之前，你需要做查找工作。单向链表和双向链表在查找时的时间复杂度都是O(n)，因为需要遍历所有元素才能找到要删除的元素。梳理以上过程，查找时间复杂度为O(n)，删除时间复杂度为O(1)，总时间复杂度为O(n)。上面的过程在双链表中是什么样子的？因为双链表支持双向遍历，所以查找这个操作的时间复杂度是O(1)，因为是双向遍历，所以在查找元素的时候，不需要使用所有元素遍历，删除的时间复杂度为O(1)，总时间复杂度为O(1)。因为双向链表的时间复杂度是O(1)，所以在开发中比较流行。其中体现的最重要的思想之一是：空间换时间。当内存空间相对于时间来说已经不是那么重要的时候，我们是否可以忽略次要因素而专注于解决主要矛盾呢？光说不做不符合阿凡的作风。阿芬今天实现了一个比较常见的单链表操作---单链表反向单链表反向代码实现data=data;this.next=next;}publicintgetData(){returndata;}}publicstaticvoidmain(String[]args){//初始化单链表Nodenode5=newNode(5,null);Nodenode4=newNode(4,node5);Nodenode3=newNode(3,node4);Nodenode2=newNode(2,node3);Nodenode1=newNode(1,node2);//调用反向方法Nodereverse=reverse(node1);System.out.println(reverse);}/***单链表反转*@paramlist为传入的单链表*/publicstaticNodereverse(Nodelist){Nodecurrent=list,//定义current为当前链表afterReverse=null;//定义afterReverse为新链表转换后的链表，初始为null//当前链表不为空，进行反向操作while(current!=null){//1.保存当前节点的next指针指向的链表Nodeext=current.next;//2.改变当前节点next指针指向反转后的新链表current.next=afterReverse;//3.将当前链表状态保存到新链表afterReverse=current;//4.将当前节点指针向后移动一位，进行下一次循环current=next;}returnafterReverse;}}接下来我们断点调试看看每一个结果：初始状态：第一个循环结束，第二个循环结束，第三个循环结束，第四次循环结束，第五次循环结束写这篇文章的时候，尤其是反转单链表的那篇，想了很久，借鉴了网上的思路做出来的。有些想法真的很巧妙。在阿芬的一步步断点调试+手写代码下，终于拿下了单链表的逆向。你掌握了吗？参考《极客时间》算法面试通关40讲
