1.赤裸的递归写链表
public class IntList { public int first; public IntList rest; public IntList(int f, IntList r) { first = f; rest = r; }...构想一下以下面的形式写一个链表结点，那么每次在public static void main()中调用，时
应用IntList L1 = new IntList(5, null);
当咱们要在以后结点前插入一个新的结点时，
IntList L = new IntList(5, L);IntList L = new IntList(15, L);IntList L = new IntList(50, L);每次都须要这样写，IntList()的参数，第一个是数据项，第二个是结点的指针指向，应用以上语句，以后新结点的指针每次都指向上一个结点，从而实现头插。然而以可读性来说，对于Java老手十分不敌对。
2.改良的链表写法
实质上是把一些反复的操作封装在类外面，从而在main()中调用时更加清晰简洁
首先对结点类进行封装，与上文赤裸的封装形式别无他样
public class IntNode{ public int item; public IntNode next; public IntNode(int f,IntList r){ item = f; next = r; }}之后构建一个SLList class 在外面封装一些办法，比方构造函数：
public SLList(int x){ first = new IntNode(x,null); }则咱们的传参缩小为只有一个x，也就是省去了每次都须要本人加null，
在以后结点前增加新的结点：
public void addFirst(int x){ first = new IntNode(x,first); }类比上文中在main()外面增加新结点的办法，每次都是IntList L = new IntList(data,L)
咱们把每次新结点的rest指针指向上一个结点的操作封装在类内，省去每次调用都要写一遍的操作
返回以后结点的数据：
public int getFirst(){ return first.item; }残缺代码：
public class SLList{ public IntNode first; public SLList(int x){ first = new IntNode(x,null); } public void addFirst(int x){ first = new IntNode(x,first); } public int getFirst(){ return first.item; }}精彩的是，当咱们在main()外面调用时，不再显得横七竖八，更加便于了解，比方构建链表头结点与新增结点操作：
SLList L = new SLList(15);L.addFirst(10);L.addFirst(5);一眼就能看进去是增加了10，5这两个结点。
3.Private申明
假如某人有一个愚昧的做法，这样写
public class SLLTroubleMaker { public static void main(String[] args) { SLList L = new SLList(15); L.addFirst(10); L.first.next.next = L.first.next; }}当你应用L.first.next.next = L.first.next;
这会导致结点指向本身，从而造成有限循环，为了防止外人调用first成员，咱们能够将其设为公有的，即private IntNode first;
公有变量往往是须要用户理解的，就比方对一辆汽车而言，其发动机引擎如何将汽油焚烧等等不须要咱们晓得，咱们只须要操作public的方向盘等等，
当你申明public时，示意全世界都有永恒拜访它的权限
4.嵌套类
因为java主类的名字必须与.java的文件名雷同，否则无奈编译，以前咱们总是把两个class写在两个.java文件中，而后调用它们，比方上文中的链表创立，咱们先在一个.java文件中写下public class IntNode,再在另一个.java文件中public class SLList中调用
显然这是比拟麻烦的，因而咱们能够把class IntNode写进class SLList中，作为嵌套类
public class SLList { public class IntNode { public int item; public IntNode next; public IntNode(int i, IntNode n) { item = i; next = n; } } private IntNode first; public SLList(int x) { first = new IntNode(x, null); } ...分割上文咱们所说的private,咱们能够把class IntNode设置为private，禁止拜访其外部成员private class IntNode
static
当嵌套类齐全不须要应用外部类的任何办法和成员时，能够加上static,申明为static意味着动态类中的办法不能拜访关闭类的任何成员。在这种状况下，这意味着 IntNode 将无法访问first，addFirst()或getFirst()。private static class IntNode
应用static的前提是确保嵌套类齐全不须要拜访内部元素，加上static能够节俭内存空间
5.addLast()与size()
接下来须要增加两个办法，作用别离是在链表开端增加一个新的结点和计算链表的总长度，
因为每次默认的新增结点都是头插，每次新增结点都是插入到以后结点之前，因而first总是头结点，要做到在链表开端增加一个新的结点，须要先遍历链表直到达到最初一个结点，再作增加操作
public void addLast(int x) { IntNode p = first; while (p.next != null) { p = p.next; } p.next = new IntNode(x, null);}因为咱们的主类是SLList，并没有next指针，所以须要应用IntNode外面的next，增加辅助办法
private static int size(IntNode p) { if (p.next == null) { return 1; } return 1 + size(p.next);}这是递归的办法求长度，十分相似于求二叉树的深度，返回1+残余链表的长度，1即以后结点长度，如josh hug所说，这是神的语言，咱们将其转换为凡人的语言
public int size() { return size(first);}Java容许两个函数同名，只有两个函数的参数定义不同即可，这叫做函数重载
6.改良size()的办法--caching
咱们的递归求解size()，当数据量足够宏大时，工夫复杂度是O(n),当计算100长度的链表须要两秒时，计算100000长度的链表可能须要2000秒，对于此，咱们须要进行改良，也就是新增一个size变量，记录以后链表的长度
public class SLList { private IntNode first; private int size; public SLList(int x) { first = new IntNode(x, null); size = 1; } public void addFirst(int x) { first = new IntNode(x, first); size += 1; } public int size() { return size; } ...}那么初始时只有一个头结点，size=1,尔后每次进行减少操作，size+1即可，这样的工夫复杂度将 是O(1)级别。
7.空链表与哨兵结点
假如咱们想创立一个空的链表
public SLList() { first = null; size = 0;}那么当咱们在调用之前的addLast()办法时，其中的
p=first;while(p.next!=null)这里p=first=null,咱们调用p.next相当于调用null.next，显然会触发NullPointerException,简略的解决办法是在addLast()加一个特判条件
if (first == null) { first = new IntNode(x, null); return; }然而当咱们之后面对更为简单的数据结构，诸如树，图之时，这种特判会十分麻烦，因而为了对立，咱们设定一个哨兵结点，也就是相当于头结点，其数据域不放任何值（也能够轻易赋值，don't care），而后真正的数据项从头结点的下一项开始寄存，这样空链表的判断条件则是head.next=null即可，不会触发空指针异样
全副都增加哨兵结点之后的代码为
public class SLList{ private static class IntNode{ public int item; public IntNode next; public IntNode(int i,IntList n){ item = i; next = n; }} public IntNode sentinel; private int size; public SLList(){ sentinel = new IntNode(??,null); size = 0; } public SLList(int x){ sentinel = new IntNode(??,null); sentinel.next = new IntNode(x,null); size = 1; } public void addFirst(int x){ sentinel.next = new IntNode(x,sentinel.next); size++; } public int getFirst(){ return sentinel.next.item; } public void addLast(int x){ IntNode p = sentinel; while(p.next!=null){ p = p.next; } p.next = new IntNode(x,null); size++; }}8.Invariants
带有哨兵结点的SLList至多具备以下invariants：
- sentinel援用总是指向哨兵结点。
- 第一个真正的结点（如果存在）始终位于sentinel.next.item。
- SSList的size变量始终是已增加的我的项目总数。