1。裸递归写链表publicclassIntList{publicintfirst;公共IntList休息；publicIntList(intf,IntListr){first=f;休息=r；}...想象一下用上面的方式写一个链表节点，然后每次在publicstaticvoidmain();中调用时使用IntListL1=newIntList(5,null);当我们要在当前节点前插入一个新节点指向时，IntListL=newIntList(5,L);IntListL=newIntList(15,L);IntListL=newIntList(50,L);每次都需要这样写，IntList()的参数，第一个是数据项，第二个是节点的指针。使用上面的语句，当前新结点的指针每次都指向前一个结点，这样就完成了表头的插入。但是在可读性上，对Java新手来说很不友好。2、改进后的链表写法本质上是将一些重复的操作封装在类中，这样在main()中调用时更加清晰简洁。首先对节点类进行封装，这和上面的裸封装方式没有什么区别publicclassIntNode{publicintitem;接下来是公共IntNode；publicIntNode(intf,IntListr){item=f;下一个=r；}}然后构建一个SLList类，将一些方法封装在里面，比如构造函数：publicSLList(intx){first=newIntNode(x,null);}那么我们的传参就减少到只有一个x，也就是省去了每次都加null，在当前节点之前增加一个新节点：publicvoidaddFirst(intx){first=newIntNode(x,第一的）;}类比上面main()中添加新节点的方法，每次都是IntListL=newIntList(data,L)我们把每个下一个新节点的rest指针指向上一个节点的操作封装起来在类中，无需每次调用??时都编写操作。返回当前节点的数据：publicintgetFirst(){returnfirst.item;}完整代码：publicclassSLList{publicIntNodefirst;publicSLList(intx){first=newIntNode(x,null);}publicvoidaddFirst(intx){first=newIntNode(x,first);}publicintgetFirst(){returnfirst.item;}}奇妙的是，当我们在main()中调用时，不再凌乱易懂，比如构建链表的头节点，添加新的节点：SLListL=newSLList(15);L.addFirst(10);L.addFirst(5);一眼就可以看出，初始化第一个元素为15的节点后，又将10和5这两个节点相加3.Private声明假设有人有一个愚蠢的方法来写publicclassSLLTroubleMaker{publicstaticvoidmain(String[]args){SLListL=newSLList(15);L.addFirst(10);L.首先。next.next=L.first.next;当你使用L.first.next.next=L.first.next;这将导致节点指向自身，从而导致无限循环。为了防止外人调用第一个成员，我们可以将其设置为private，即先私有IntNode；private变量往往需要用户了解，比如对于一辆汽车，它的private引擎是如何燃烧汽油的等等不需要我们知道，我们只需要操作Public方向盘等即可。声明public时，意味着全世界都可以永久访问它4.嵌套类因为java主类的名字必须和.java文件名一样，否则无法编译。我们以前总是在两个.java文件中写两个类，然后调用它们。比如上面链表的创建，我们先在一个.java文件中写下publicclassIntNode，然后在另一个.java文件中的publicclassSLList中调用，显然比较麻烦，所以我们可以写classIntNode作为嵌套类进入SLList类publicclassSLList{publicclassIntNode{publicintitem;接下来是公共IntNode；publicIntNode(inti,IntNoden){item=i;下一个=n；}}privateIntNode首先；publicSLList(intx){first=newIntNode(x,null);}...结合我们上面提到的private，我们可以将类IntNode设置为private，禁止访问其内部成员static并将其声明为static意味着静态类中的方法不能访问封闭类的任何成员。这意味着IntNode将无法访问first，addFirst()或getFirst()。privatestaticclassIntNode使用static的前提是保证嵌套类根本不需要访问外部元素，添加static可以节省内存空间5.addLast()和size()接下来需要添加两个方法，这在链表的末尾添加一个新节点并计算链表的总长度。由于每个默认的新节点都是头插入，每个新节点都插入到当前节点之前，因此first始终是头节点。要在链表的末尾添加新节点，需要遍历链表，直到到达最后一个节点，然后添加。由于我们的主类是SLList，没有next指针，所以需要在IntNode中使用next。添加辅助方法publicvoidaddLast(intx){IntNodep=first;while(p.next!=null){p=p.next;}p.next=newIntNode(x,null);}/*查找链表Length/privatestaticintsize(IntNodep){if(p.next==null){return1;}return1+size(p.next);}这里是递归求长度的方法，和求二叉树深度很相似，return1+剩余链表的长度，1是当前的长度节点。同时，Java允许两个函数同名，只要两个函数的参数定义不同即可。这叫做函数重载，size()的长度可以这样计算写：publicintsize(){returnsize(first);}6.改进size()的方法——缓存我们的递归解size()，当数据量足够大时，时间复杂度为O(n)，当计算一个长度为100的链表需要两秒时，计算一个长度为的链表可能需要2000秒100,000。为此，我们需要改进，即增加一个size变量来记录当前链表的长度publicclassSLList{privateIntNodefirst;私有整数大小；publicSLList(intx){first=newIntNode(x,null);大小=1；}publicvoidaddFirst(intx){first=newIntNode(x,first);尺寸+=1；}publicintsize(){返回大小；}...}那么一开始只有一个头节点，size=1，每次增加操作后，size+1就足够了，所以时间复杂度会是O(1)级别7.空链表和哨兵节点假设我们要创建一个空链表publicSLList(){first=null;size=0;}然后我们调用前面的addLast()方法时，p=first;while(p.next!=null)这里p=first=null，我们调用p.next相当于调用null.next，显然会触发NullPointerException。简单的解决方案是添加一个特殊条件if(first==null){first=newIntNode(x,null);返回;但是当我们面对比较复杂的数据结构，比如树，图的时候，这种特殊的判断会很麻烦，所以为了统一，我们设置了一个哨兵节点，相当于头节点，它的数据字段不包含任何值（也可以随便赋值，无所谓），然后从头节点的下一项开始存储真正的数据项，这样空链表的判断条件就是head.next=null，不会触发空指针异常。添加所有哨兵节点后的代码为publicclassSLList{privatestaticclassIntNode{publicintitem;接下来是公共IntNode；publicIntNode(inti,IntNoden){item=i;下一个=n；}}公共IntNode哨兵；私有整数大小；publicSLList(){sentinel=newIntNode(??,null);大小=0；}publicSLList(intx){sentinel=newIntNode(??,null);sentinel.next=newIntNode(x,null);大小=1；}publicvoidaddFirst(intx){sentinel.next=newIntNode(x,sentinel.next);尺码++；}publicintgetFirst(){返回sentinel.next.item;}publicvoidaddLast(intx){IntNodep=sentinel;while(p.next!=null){p=p.next;}p.next=newIntNode(x,null);尺码++；}}8.Invariants（不变量）带有sentinel节点的SLList至少有以下不变量：sentinelreferencesalwayspointtothesentinelnode一个真正的节点（如果存在的话）总是位于sentinel.next.item。SSLList的大小变量始终是已添加的项目总数。
