我现在有点明白了。面试过程中，面试官有时会让我们手写代码。其实主要是考大家的基本功，也是通过大众熟悉的领域来考核的。大家的系统思考和应对思路。而数据结构是编程领域最基础的知识，因为在编程的世界里必须要解决的问题：存储。接下来，笔者将从自己的角度重新开始学习数据结构，将所学的内容与大家共同探讨、交流、共同进步。温馨提示：本文主要以单链表为例，因为单链表的反转和检测是常见的面试题。1、什么是链表？它的基本特点是什么？面试官让我们手写一个链表，那我们就快速梳理一下链表的基本特征吧。我特意从百度百科上搜索了链表的定义：链表是物理存储单元上的一种无序无序的存储结构，数据元素的逻辑顺序是通过链表中指针链接的顺序来实现的列表。链表由一系列节点组成（链表中的每个元素称为一个节点），节点可以在运行时动态生成。每个节点由两部分组成：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。基本特点如下：物理存储是非连续的，逻辑上通过指针实现顺序。示例图如下：数据结构分为指针域和数据域。面向对象编程，类不仅需要定义属性，还需要抽象行为（方法），思路如下：注意面试过程中，基本上只需要增删改查即可。2.图解及代码链表的类图如下：链表的存储结构如下图所示：下面从代码的角度来实现一个简单的链表。2.1基本代码链表的基本数据如下：publicclassLinkedList{/**pointerfield*///headnodeprivateDataNodeheader;//slavenodeprivateDataNodetail;privateintsize;/***dataNode*@param*/privateclassDataNode{publicTvalue;publicDataNodenext;publicDataNode(Tvalue){this.value=value;}}}2.2指定插入节点的下标上面是主要是定义基本的数据结构，接下来我们看在链表中间插入新的数据。在指定的下标处插入一个节点。该节点作为新节点的前驱节点，暂存其next指针，防止指针丢失。说明如下：代码如下=get(index);DataNodetmp=prev.next;//@1prev.next=node;//@2node.next=tmp;//@3}链表的插入先找到前驱节点，暂存它的下一个指针，注意指针会丢失。说明如下图所示：上面三行代码的说明如下：@1:先创建一个临时节点，用来临时存放前驱节点的next@2:前驱节点的next指针指向到要再次插入的节点@3：新节点的next指针指向原前驱节点的next指针优化点：其实我们发现前驱节点是要暂存的，但是是否真的有必要开一个临时节点，其实没必要，直接赋值给新节点的next即可。优化代码如下：node.next=prev.next;prev.next=node;2.3移除指定下标处的节点移除指定下标处的节点示例图：如上图所示，下标为被删除的是2个节点，也就是图中的第三个节点，核心关键点还是要找到要删除的节点的前驱节点，然后前驱节点的next等于该节点的next删除，所以实现代码如下：publicTremove(intindex){if(index>=size){thrownewArrayIndexOutOfBoundsException();}DataNodepre=get(index-1);DataNodecur=pre.next;pre.next=cur.next;//helpGCcur.next=null;size--;returncur.value;}2.4单链表倒序所谓单链表倒序就是将结果倒序输出原始链表。next指针指向前驱节点。但是由于单向链表只有next指针，在从头节点开始遍历的过程中，当遍历指针前进到当前节点时，需要能够方便的访问到该节点的前一个驱动程序。还有一个核心点就是在遍历过程中，当对当前节点的next指针进行操作（赋值给前驱节点）时，必须暂存该节点的next指针，否则next指针丢失，本次结束不能遍历链表。基于以上思路，链表反转的具体操作流程如下图所示：基于以上思路，代码如下：publicvoidreverse(){//遍历DataNodecur=headerfromtheheadnode;//记录当前节点到prev前驱节点DataNodecur_prev=null;//存储当前节点到next指针DataNodecur_next=null;//从当前节点遍历到末尾直接while(cur!=null){//反转前，暂存相关节点cur_next=cur.next;cur.next=cur_prev;cur_prev=cur;//继续遍历下一个节点cur=cur_next;}//反向头，tailDataNodetmp=header;header=tail;tail=tmp;}链表其他方法的实现基本相同。从代码的编写过程中不难看出，链表的操作主要是对各个节点的指针进行操作。3.面试常见问题3.1链表和数组的区别链表和数组的区别可以从以下几个方面展开：内存布局插入性能搜索性能3.1.1内存布局数组必须申请连续内存，即物理上连续，比如当前的jvm虚拟机当前还剩150M内存，但是如果此时你尝试去创建100M内存，你可能无法分配内存并触发垃圾回收，而链表在逻辑上是连续的，不是物理上连续，因为它是通过指针定位的。3.1.2插入性能链表在头尾节点的插入性能非常好。如果需要在链表的任意位置插入数据，需要先从头结点开始遍历，先找到要插入的相关结点的前驱结点。后续的插入操作只需要涉及到指针赋值就具有良好的性能，而数组插入涉及到数据的复制和移动，导致性能损失较大。3.1.3搜索性能数组最大的优势是随机搜索能力，其时间复杂度为O(1)，即数组可以根据下表快速定位到需要查询的数据。链表只能从头节点或尾节点开始遍历。本文转载自微信公众号“中间件兴趣圈”，可通过以下二维码关注。转载本文请联系感兴趣的中间件圈公众号。
